I am noting down time complexity in so-caleld "Big O" notation. This, approximately, describe how the time to do a given task grows with the size of the input. Roughly speaking, O(1) is "constant time", O(n) is "linear time" (where doubling the size of the input means it takes double the time), O(n^2) is "quadratic time" (doubling the size of input will require quadruple time) and O(2^n) is "exponential time" (where adding one item to process will require double the time).
I am also choosing to only consider "time complexity", rather than "space complexity" (another possible complexity measure), mostly because time complexity is usually the more interesting complexity (especially with the size of storage these days).
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(1) |
| Adding an internal element | O(n) |
| Changing an element at head | O(1) |
| Changing an internal element | O(1) |
| Removing an element at head | O(1) |
| Removing an internal element | O(n) |
| Retrieving the Nth element | O(n) |
This is your average single-linked list, a humble, simple data structure composed of nodes containing one item of data and one pointer to the next node in the list. It can be used to build more complex data structures. Note that a linked list can trivially be used as a stack by adding and removing elements at the list head, where doing so is cheap.
The cost for changing an internal element is based on already having a pointer to it, if you need to find the element first, the cost for retrieving the element is also taken.
To remove an internal element, you need to scan the list to find the preceeding element, to change its tail pointer. Similarly for adding an internal element (in some situations, you can amortise this cost by keeping track of the preceeding element as you follow the tail pointers, then you can get away with inserting the new element at O(1)).
The single-linked list is order-preserving (that is, you can rely on the list being in the same order when you scan through it, unless you've explicitly re-ordered it)
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(1) |
| Adding an internal element | O(1) |
| Changing an element at head | O(1) |
| Changing an internal element | O(1) |
| Removing an element at head | O(1) |
| Removing an internal element | O(1) |
| Retrieving the Nth element | O(n) |
The double-linked list is a bit more complex than the sigle-linked list. It keeps a value and pointers to preceeding and following nodes. This means that some operations is faster than with a single-linked list, but there's a constant overhead, both in storage and in time, whenever a list modification happens.
The double-linked list is order-preserving (that is, you can trust it to be in the same order unles syou've explicitly re-ordered it).
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(n) |
| Adding an internal element | O(n) |
| Changing an element at head | O(1) |
| Changing an internal element | O(1) |
| Removing an element at head | O(n) |
| Removing an internal element | O(n) |
| Retrieving the Nth element | O(1) |
The array is a contigous area of memory, with the mth element placed m*size octets from the start of the array. This means that any addition or removal of elements require memory copies, making size-changing operations expensive. In a scenario where elements are occasionally added to the array, in the "tail" position, the cost of doing so can be amortised by doubling the size of the array allocation and manually keeping track of where the end is supposed to be, turning the O(n) cost of adding an element into an amortised O(1).
The vector is order-preserving (that is, you can trust it to stay in the same order unless you explicitly re-order it).
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(1) |
| Adding an internal element | O(1) |
| Changing an element at head | O(1) |
| Changing an internal element | O(1) |
| Removing an element at head | O(1) |
| Removing an internal element | O(1) |
| Retrieving the Nth element | O(1) |
The hash table is not (really) O(1), it's just amortised O(1), any specific operation can take longer, but on average, adding, removing and changing elements is O(1).
The hash table is not order-preserving, there is no guarantee that two traversals of all elements will return them in the same order. However, it is (usually) the case that two traversals with no added, removed or changed elements will have the same order.
I have taken the liberty to interpret "head position" as "key that would be sorted lower than any other key", but since hash tables are not order-preserving, it doesn't make much sense.
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(n) |
| Adding an internal element | O(n) |
| Changing an element at head | O(1) |
| Changing an internal element | O(1) |
| Removing an element at head | O(n) |
| Removing an internal element | O(n) |
| Retrieving the Nth element | O(1) |
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(n) |
| Adding an internal element | O(n) |
| Changing an element at head | O(n) |
| Changing an internal element | O(n) |
| Removing an element at head | O(n) |
| Removing an internal element | O(n) |
| Retrieving the Nth element | O(n) |
| Operation | Time complexity |
|---|---|
| Adding an element at head | O(log n) |
| Adding an internal element | O(log n) |
| Changing an element at head | n/a |
| Changing an internal element | n/a |
| Removing an element at head | O(log n) |
| Removing an internal element | n/a |
| Retrieving the Nth element | n/a |
The only way to retrieve the Nth element would be to remove the N first elements, remember the value of the Nth and then put them all back together.
It does not make sense changing heap-stored elements, so I have marked that as "not applicable".
| Operation | Time complexity |
|---|---|
| Adding an element at head | O() |
| Adding an internal element | O() |
| Changing an element at head | O() |
| Changing an internal element | O() |
| Removing an element at head | O() |
| Removing an internal element | O() |
| Retrieving the Nth element | O() |
This is one of Ingvar's essays
By: Kajari
2009-10-25 17:00
After searching online for hours I found this incredible site. You have done a great job in comparing the different data structures! Looking forward to more articles from you.
By: pankaj
2010-01-20 09:57
i am thankful u to provide such comparative data in terms of complexity.could you please provide complexity of tree algorithms,graph algorithms searching and sorting algorithms of different data structures.i will be thankful to you
By: Bruce
2010-03-30 09:31
one note regarding the heap: generally when people say heap they mean max-heap, where the root is greater than the children. if it's smaller, it's min-heap, and is generally specified. You might want to add it to the description. Regards, Bruce