Data structures
In a recent conversation, I realised that some of the more basic data structures have some non-intuitive behaviour. This is, of course, an excellent excuse to waffle on about the guarantees that a well-implemented data structure gives you, as well what it DOESN'T give you. The time complexity is estimated for a data structure with n elements.I am noting down time complexity in so-called "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).
Linked list
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) |
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)
Double-linked list
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 order-preserving (that is, you can trust it to be in the same order unless you've explicitly re-ordered it).
Variants on single- and double-linked lists
Both kinds of lists can have an associated "list header" node that contains pointers to the first and last elements of the list it concerns. With this in place, adding or changing an element in the "tail" position is O(1) and for a double-linked list it is also O(1) to remove an element in a tail position.Vector/one-dimensional array
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 vector is order-preserving (that is, you can trust it to stay in the same order unless you explicitly re-order it).
Hash table
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 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 (this MAY be different in garbage-collecting languages, if memory location is used as the thing to be hashed, as each access after GC would require a re-hash).
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.
"Simple" string
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) |
"Complex" string
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) |
Heap
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 |
It does not make (much) sense changing heap-stored elements, so I have marked that as "not applicable".
Balanced binary tree
Operation | Time complexity |
---|---|
Adding an element at head | O(lg n) |
Adding an internal element | O(lg n) |
Changing an element at head | O(lg n) |
Changing an internal element | O(lg n) |
Removing an element at head | O(lg n) |
Removing an internal element | O(lg n) |
Retrieving the Nth element | O(lg n) |
Data structure
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() |
0 comments:
Post a Comment