Resources
Takeaways:
- 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.
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.
Oldest comments (0)