Efficiently adjustable size

If we want to add in a new node, we only need to modify the pointer of the previous node and the next node, which takes constant time. Since nodes are connected via pointers, they can be located anywhere in Main Memory. This allows us to add more nodes as long as there is free memory space sufficient for a single node.

Cache Miss!!!

Since the connection between 2 nodes are via Pointer, the nodes are scattered around the Main Memory. This means we can’t make use of Cache Locality and this results in a very high rate Cache Miss.

Memory Leak

For languages like C which doesn’t come with a Garbage Collector, we need to manually release deleted node from the Heap Segment to prevent Memory leak.

Linked list node implemented with Java

public class Node {
	int val;
    Node next;
    Node(int val) this.val = val;

Print Out Linked List

public void printLinkedList(ListNode node) {
	ListNode a = node;
	while (node!=null) {
		System.out.printf("%d ", node.val);
		node = node.next;

Draw It Out

When unsure about the relationship, draw out the nodes & pointers. It really makes the visualization of the manipulation easy!

Virtual Node

  • to access either the head node or the tail node, this makes handling edge cases & reverting linked list easier.

Time Complexity

Insert, Delete

, we only need the node’s previous node and next node, make the corresponding pointer changes.


We need to index the node before we can perform insertion and deletion. And it takes for indexing. So generally, insertion and deletion in linked list results in . Unless the operation is performed at the head node or tail node of the linked list. It is recommended to use Array by default unless there are reasons and measurements that show using Linked List is better, refer to Are lists evil? — Bjarne Stroustrup : Standard C++ for more details.

Space Complexity

Single Linked List

Double Linked List

  • Implement Advanced Data Structure, like Red Black Tree where we need to know the parent node of a given node
  • Implement Eviction Policy like LRU
  • Implement Browser History Navigation. When we at a page, knowing what is the previous page (parent node) & what is the next page(child node). This makes the browsing experience more smooth

Node Implementation

public class Node {
  int val;
  Node prev;
  Node next;
  Node() {}
  Node(int key, int val) this.val = val;

In an LRU cache implementation, we need to include an additional piece of information, the key. This is necessary to remove an invalidated cache entry from the Hash Map in constant time O(1).

Circular Linked List