Adjustable size with minimal impact

If we want to add in a new node, we just need to modify the pointer of the previous node & the pointer of the next node - in constant time. Since the connection between the 2 nodes are via Pointer, we can have nodes all around the Main Memory. This means we can add more nodes as long as there is free memory size that can fit 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 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.

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

Circular Linked List