loading...

Linked Lists

jjb profile image JB 惻Updated on 惻2 min read

Resources

  1. Linked list overview and implementation
  2. Linked list overview
  3. Detailed overview and implementation

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.

Discussion

pic
Editor guide