Linked Lists - 4 (Summary)
Time Complexity
For a list with $n$ elements the following operations have the following time complexity:
- Traversing: $O(n)$
- Searching:
- Unsorted: $O(n)$
- Sorted: $O(n)$
- Insertion/Deletion:
- Head/Tail: $O(1)$
- Middle: $O(n)$
- Finding the location may take $O(n)$ time.
Memory Management
- Memory needs to be allocated for a new node.
- We should free any object that is no longer used (after we delete a node).
- In some systems, a garbage collector is responsible for storage management.
Arrays v.s. Lists
- Arrays
- Easy to access, one can access any element in a single access by its index.
- Size needs to be predetermined, may waste space.
- If we want to insert an element in the middle, needs to shift the rest.
- Linked Lists
- Needs to traverse the list to access elements in the middle.
- Does not need to predefine size, it’s flexible to add elements.
- Once we find the location to insert, we can insert without moving the rest, only need to alter a few pointers.