Singly vs Doubly Linked List, step by step.

A singly linked list gives each node one link, next, to the node after it. A doubly linked list adds prev, to the node before it, so it can walk backward and delete a node you already have a link to in O(1), not O(n). Use a singly linked list for stacks and queues, a doubly linked one to go back or to delete such nodes.

Below, both lists delete their last node, E: the singly linked list walks from the head to find the node before it, and the doubly linked list, which keeps tail, a link to its last node, steps back once.

Singly vs doubly linked list: what differs

The same deletion in both

Take five nodes, A to E, as a singly linked list and as a doubly linked list, and delete the last one, E. The singly linked list knows only head, a link to its first node. The doubly linked list also keeps tail, a link to its last node, and each of its nodes has prev as well as next. In both, the node that has to change is D, the one before E: its next must stop referring to E. How does each list get to D?

Singly linked list: delete the last node

All steps as text
  1. The list is A → B → C → D → E, and head refers to A. Step forward to delete E.
  2. The X marks E, the last node. Only D's next refers to E, so the list has to reach D first, starting from head.
  3. Two variables, shown as markers, walk the list together: pred (short for predecessor) starts at A, and cur (short for current) at B. Both move right until cur refers to the last node, whose next is null: it refers to no node.
  4. Both markers move one node right. C's next is not null, so C is not the last node, and the walk goes on.
  5. Both move again. D's next is not null either.
  6. cur refers to E, whose next is null: E is the last node, and pred refers to D, the node before it.
  7. D's next is set to null, and D is the last node of the list.
  8. No node refers to E any more, so E is no longer part of the list.
  9. The list reads A → B → C → D. Reaching D took a walk from the head, O(n); changing one link took O(1).
Singly vs Doubly Linked List — Singly linked list: delete the last node. Last step: The list reads A → B → C → D. Reaching D took a walk from the head, O(n); changing one link took O(1).

A singly linked list can only go forward from head, so the walk is the only way to D: three moves here, almost a million in a list of a million nodes. A tail would not help: it refers to E, and nothing in E leads back to D. That is why a singly linked list with a tail, the app's double-ended list, still walks.

Note

In C and C++ a link is a pointer; in Java and Python it is a reference.

Doubly linked list with a tail: the same deletion

All steps as text
  1. The list is A ⇄ B ⇄ C ⇄ D ⇄ E; head refers to A and tail to E. Step forward to delete E.
  2. The X marks E, the last node. As in the singly linked list, D's next has to stop referring to E, so the list has to reach D first.
  3. tail moves to the node that E's prev refers to: D. One link followed, with no walk from head.
  4. D's next is set to null, and D is the last node of the list.
  5. No node refers to E any more, so E is no longer part of the list.
  6. The list reads A ⇄ B ⇄ C ⇄ D, and tail refers to D. E's prev led straight to D, so no walk was needed: deletion at the end with a tail takes O(1).
Singly vs Doubly Linked List — Doubly linked list with a tail: the same deletion. Last step: The list reads A ⇄ B ⇄ C ⇄ D, and tail refers to D. E's prev led straight to D, so no walk was needed: deletion at the end with a tail takes O(1).

It takes both the tail and prev: without a tail, the doubly linked list would first walk from head to E, and the deletion would be O(n) again.

  • Walking backward. From the tail to the head, following prev.
  • Deleting a node you hold. Given a link to C, for example from a hash table that maps keys to nodes, a doubly linked list links C's two neighbors to each other and C is out: O(1). A singly linked list must first walk from the head to find the node before C: O(n). The doubly linked list page shows why.
  • Inserting before a node you hold. The same: the node before it is one prev away, or a walk away.
  • Deleting at the end with a tail. As above: O(1) against O(n).

Some operations cost the same in both. Inserting or deleting at the front changes at most three links at the head: O(1). Inserting at the end is O(1) in both once the list keeps a tail. Searching for a value is a walk in both, O(n). So is reaching the node at an index; a doubly linked list that keeps a tail and its length can start from the nearer end and walk at most half the list, which is still O(n).

Memory. One more link in every node, typically 8 bytes on a 64-bit machine. For small values, such as one number per node, the two links take more memory than the value itself.

More links to update. Inserting a node in the middle changes two links in a singly linked list and four in a doubly linked list; deleting one changes one against two, as deleting C shows on the linked list and doubly linked list pages. Every operation has to keep next and prev in step: a prev left referring to a deleted node breaks the walk backward without breaking the walk forward.

Singly vs doubly linked list at a glance

Singly linked listDoubly linked list
Links per nodeOne: nextTwo: next and prev
WalkForward onlyForward and backward
Insert or delete at the frontO(1)O(1)
Insert at the end, with a tailO(1)O(1)
Delete at the end, with a tailO(n)O(1)
Delete a node you hold, or insert before itO(n)O(1)
Search, access by indexO(n)O(n)
Links changed by an insert in the middle24
Links changed by a delete in the middle12
Typical usesStacks, queues, hash table chainsDeques, LRU caches, back and forward history

When to use a singly and when a doubly linked list

Use a singly linked list when the list is walked forward and loses nodes only at its head or during a walk: a stack pushes and pops at the head, a queue adds at the tail and removes at the head, and a hash table deletes a key from its bucket's chain during the same walk that finds it, keeping the node before it as it goes. None of them ever has to go back, so prev would be memory spent for nothing.

Use a doubly linked list when nodes are removed from the middle by a link you already hold, or when the list is walked both ways: a deque, which adds and removes at both ends; an LRU cache, which keeps its items in order of use: a hash table finds an item's node, and each time the item is read its node is unlinked where it stands and moved to the front, in O(1); back and forward history. Java's LinkedList and C++ std::list are doubly linked; C++ std::forward_list is singly linked.

Common mix-ups

  • A doubly linked list deletes from the middle in O(1). Only a node you already hold. To delete a value, it first walks from head to the value's node, O(n), just as a singly linked list does.
  • A doubly linked list has fast access by index. If it keeps its length, it can start from the nearer end, but it still walks node by node: O(n), against O(1) in an array.

Singly vs doubly linked list interview questions

Why use a singly linked list if a doubly linked list can do more?

It takes less memory, one link per node instead of two, and most insertions and deletions update fewer links: two instead of four for an insert in the middle. For a stack or a queue, which never need the node before another, the second link would buy nothing.

How do you delete a node from a singly linked list when you have only that node?

Copy the next node's value into it and delete the next node instead: O(1), with no walk. It fails for the last node, which has no next node to copy, and it moves values between nodes, so any other link held to the next node now refers to a deleted one.

Is Java's LinkedList singly or doubly linked?

Doubly linked: each node keeps links to the next and the previous node, and the list keeps both ends, so adding or removing at either end is O(1). C++ std::list is doubly linked too, and std::forward_list is the singly linked one.

One deletion here.
Both lists in the app.

In VisiGrab, the linked list and the doubly linked list are two slide shows, 73 and 60 slides, from what a node is to a list with a tail, played one step at a time.

Every insertion and deletion

At the front, in the middle and at the end, each a chapter of its own in both lists, with the walking markers and every link that changes.

A tail in both

In the singly linked list a tail makes insertion at the end O(1) while deletion there stays O(n); in the doubly linked list both become O(1).

Forward and back

Step through every slide and step back, or jump to any slide from the list. Each show reopens where you left it.

Theory and complexity

Info and Efficiency tabs in both, with complexity tables for a list with a head only and with a head and a tail.

Python, Java and C++

Both lists with six insert and delete methods, in the order the slide shows play them, then the versions with a tail. In C++, both free every removed node.

Two quizzes

Ten questions on each list, with an explanation for every option.

One link or two,
step by step.

Download VisiGrab to step through every insertion and deletion in both lists, with and without a tail.

The linked list and the doubly linked list are topics among 30+. See them all