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
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?
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.
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.
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.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 linked list | Doubly linked list | |
|---|---|---|
| Links per node | One: next | Two: next and prev |
| Walk | Forward only | Forward and backward |
| Insert or delete at the front | O(1) | O(1) |
| Insert at the end, with a tail | O(1) | O(1) |
| Delete at the end, with a tail | O(n) | O(1) |
| Delete a node you hold, or insert before it | O(n) | O(1) |
| Search, access by index | O(n) | O(n) |
| Links changed by an insert in the middle | 2 | 4 |
| Links changed by a delete in the middle | 1 | 2 |
| Typical uses | Stacks, queues, hash table chains | Deques, LRU caches, back and forward history |
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.
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.O(n), against O(1) in an array.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.
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.
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.
// 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.
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.
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).
Step through every slide and step back, or jump to any slide from the list. Each show reopens where you left it.
Info and Efficiency tabs in both, with complexity tables for a list with a head only and with a head and a tail.
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.
Ten questions on each list, with an explanation for every option.
// step through both
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