CS Level Up Series (29 Part Series)
- Insertions and deletions are O(1) (constant time).
- Searching for an element is O(n) (linear), and not cache friendly*
- Space is O(n). But it's important to note that the effective memory is double that of a regular array. This is because each node contains value/data and a reference/pointer to the next node. This means Linked Lists use an extra 4 bytes of memory for each element.
- There are 3 common types of Linked Lists: singly linked, doubly linked, and circularly linked.
- Each node in a Singly Linked List has a pointer to the next node. This means traversal can only happen in one direction.
- Doubly Linked Lists have two pointers per node, one for the next node and one for the previous node. Traversal can be in both directions.
- In Circular Linked Lists the tail (last node) has a pointer to the head node (first node).
- Although it is common for Linked List implementations to only maintain a reference to the head node, some implementations also keep track of the tail node.
*Linked Lists, unlike Dynamic Arrays, aren't required to be stored in continuous blocks of memory. This means each node in a Linked List does not have to be stored next to other nodes belonging to the same Linked List. For this reason, the CPU cannot effectively cache the contents of a Linked List as well as it can an array.
Linked Lists are a slightly harder, and bigger, topic to grasp than Dynamic Arrays, but still relatively straightforward. Here's the finished implementation of a Singly Linked List with test code:
As always, please let me know if you noticed an error with anything in this post.
The software industry moves fast. But if you keep up, you can have an incredible career.