Linked Lists
Loading
Loading
Linked Lists
What you give up by abandoning contiguity, and what you get back.
By the end of this chapter
An array's elements are adjacent, which is what makes indexing arithmetic. A linked list gives that up: each node holds a value and a reference to the next one, and they can be anywhere in memory.
| Operation | Array | Linked list |
|---|---|---|
| Read by index | O(1) | O(n) |
| Insert at front | O(n) | O(1) |
| Insert after a known node | O(n) | O(1) |
| Delete a known node | O(n) | O(1) with the previous node |
| Memory per element | value only | value plus a reference |
def length(head): count = 0 node = head while node is not None: # the null check IS the loop condition count += 1 node = node.next return countSign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for: