Search data structure: Difference between revisions

Revision as of 03:11, 14 January 2010

Revision as of 12:37, 14 January 2010

Line 37:

|-

| [[Array data structure|Array]]

| [[ConstantLinear time|O(1n)]]

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

| [[Linear time|O(n)]] or [[Constant time|O(1)]]<ref>if indexed by value - see [[control table]],"trivial hash function" example</ref>

| [[Linear time|O(n)]] or [[Constant time|O(1)]]<ref>if indexed by value - see [[control table]],"trivial hash function" example</ref>

| O(n)

|-

| Sorted Array

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

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

| O(log n)

| [[Constant time|O(1)]]

| O(n)

|-

| [[Linked list]]

| [[Constant time|O(1)]]

| [[Constant time|O(1)]]

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

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

| O(n)

|-

| Sorted linked list

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

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

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

| [[Constant time|O(1)]]

| O(n)

|-

| Self-balancing binary tree

| [[Logarithm|O(log n)]]

| [[Logarithm|O(log n)]]

| [[Logarithm|O(log n)]]

| [[Logarithm|O(log n)]]

| O(n)

|-

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

| [[Logarithm|O(log n)]]

| O(log n)<ref>Can only delete the max (or min in a min heap)</ref>

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

| [[Constant time|O(1)]]

| O(n)

|-

| [[Hash table]]

| [[Constant time|O(1)]]

| [[Constant time|O(1)]])

| [[Constant time|O(1)]]

| [[Linear time|O(n)]] or [[O(1)]]<ref>if "trivial hash function" possible</ref>

| O(n)

|}