Search data structure: Difference between revisions

Revision as of 18:43, 5 October 2013

Revision as of 12:56, 23 June 2014

Line 34:

! Insert

! Delete

! Balance

! Get at index

! Search

! Find maximum/minimum

! Find maximum

! Space usage

|-

Line 42 ⟶ 44:

| [[Linear time|O(''n'')]]

| O(''n'')

| O(1)N/A

| N/A

| O(''n'')

| O(''n'')

| O(''n'')

Line 48 ⟶ 52:

|-

| [[Sorted array]]

| O(''n'')

| O(''n'')

| O(''n'')

| O(1)

| O(log ''n'')

| O(1)

| O(1)

| O(''n'')

|-

| Unsorted [[linked list]]

| O(1)^{*
| O(1)}

| N/A

| O(1)^*

| O(''n'')

| O(''n'')

| O(''n'')

Line 64 ⟶ 72:

|-

| Sorted linked list

| O(1)^*

| O(1)^*

| O(''n'')

| O(''n'')

| O(''n'')

| O(1)

| O(''n'')

| O(''n'')

|-

| [[Self-balancing binary tree]]

| O(log ''n'')

| O(log ''n'')

| O(log ''n'')

| N/A

| O(log ''n'')

| O(log ''n'')

| O(log ''n'')

Line 81 ⟶ 93:

| [[Heap (data structure)|Heap]]

| O(log ''n'')

| O(log ''n'')^**

| O(log ''n'')

| N/A

| O(''n'')

| O(1)

| O(''n'')

| O(''n'')

|-

Line 90 ⟶ 104:

| O(1)

| O(1)

| O(''n'')

| N/A

| O(1)

| O(''n'')

| O(''n'')

| O(''n'')

|}

<small>&nbsp;* If you have a reference to the ___location of insertion/deletion (e.g., a pointer to a node in the list), then the cost is O(1). If you don't, then you need to traverse the list until you get to the ___location of insertion/deletion, which costs O(''n'').</small>

<small>&nbsp;** The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>

This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.