00:00

Singly Linked List Vs Doubly Linked List

Last updated:

Singly and doubly linked lists store the same kind of data in the same kind of chain of nodes. The only structural difference is one extra reference per node, but that reference changes the memory cost, the direction you can walk, and the speed of several operations.

This page describes each list on its own and then compares them, so you can decide which one fits a given problem.

What is Singly Linked List?

In a singly linked list, each node holds a value and a next reference to the node after it. The head reference points to the first node (it is null for an empty list), and the last node's next is null.

Singly linked list: head points to the first node, each node points to the next, and the last node points to null

Since a node only knows its successor, the list can be walked forward only.

Advantages of Singly Linked List

  • Smallest node: one reference per value, so it uses less memory than a doubly linked list.
  • Simple code: inserting or deleting changes only next references.
  • O(1) insertion and deletion at the head, which makes it a natural stack.
  • Grows and shrinks one node at a time, with no fixed capacity.

Disadvantages of Singly Linked List

  • No backward traversal; printing in reverse needs recursion or a stack.
  • Deleting the last node, or a node you hold a reference to, is O(n) because its predecessor must be found.
  • No random access: reaching position k takes O(k).
  • Still uses more memory per element than an array.

What is Doubly Linked List in Data Structure?

A doubly linked list adds a prev reference to every node, so each node knows both its neighbours. The first node's prev and the last node's next are null, and implementations usually keep both a head and a tail reference.

Doubly linked list with prev and next links between neighbouring nodes

Each node has three parts:

  1. First Part: the reference to the previous node.
  2. Second Part: the value stored in the node.
  3. Third Part: the reference to the next node.

Advantages of Doubly Linked List

  • Can be walked in both directions, from the head or from the tail.
  • A node you already hold can be removed in O(1), because its predecessor is available through prev.
  • With a tail reference, insertion and deletion at both ends are O(1), so it works well as a deque.
  • Inserting before a given node is O(1), which a singly linked list cannot do directly.

Disadvantages of Doubly Linked List

  • Each node needs an extra reference, so the list uses more memory.
  • Every insert and delete must update both next and prev links; forgetting one corrupts the list.
  • Each change does a few more reference updates, so it is slightly slower per operation, although the order of growth is the same.

Difference between Singly Linked List and Doubly Linked List

The table compares the two lists feature by feature. Complexities assume n nodes and, where stated, a tail reference.

CharacteristicSingly Linked ListDoubly Linked List
Node structureTwo fields: data and a next reference.Three fields: prev reference, data and next reference.
Memory usageLess: one reference per node.More: two references per node.
Direction of traversalForward only.Forward and backward.
Implementation complexitySimpler: each insert or delete updates one link per neighbour.More involved: both next and prev must be kept consistent.
Delete the last nodeO(n): the second-last node must be found by walking from the head.O(1) with a tail reference: the second-last node is tail.prev.
Delete a node you already holdO(n): its predecessor must be found first.O(1): its predecessor is node.prev.
Insert or delete at the headO(1)O(1)
Insert at the tail (with a tail reference)O(1)O(1)
Search for a valueO(n)O(n)
Typical usesStacks, hash-table chaining, graph adjacency lists.LRU caches, browser back/forward history, deques such as java.util.LinkedList.