concept · INFO-CS-ADS-043Doubly Linked Lists
A doubly linked list is a linked data structure in which each node contains data and references to both the previous and next nodes. This structure supports traversal in both directions.
Explanation
Overview
A doubly linked list is a sequence of nodes where each node maintains a reference to its predecessor and successor. The first node normally has a null previous reference, and the final node normally has a null next reference.
Purpose
Doubly linked lists are useful when an application needs forward and backward traversal or frequent insertion and deletion around nodes whose references are already available.
Time complexity
accessByIndex: O(n); search: O(n); forwardTraversal: O(n); backwardTraversal: O(n); insertAtHead: O(1); insertAtTailWithTailReference: O(1)
Space complexity
O(n) for n nodes, with two link references stored in each node.
Example
nodes: 10; 20; representation: NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL; explanation: The list can be traversed from 10 to 40 using next references or from 40 to 10 using previous references.
Advantages
Supports forward and backward traversal.; Allows efficient deletion when a reference to the target node is available.; Supports insertion before or after a known node.; Can simplify navigation-based applications.
Limitations
Requires more memory than a singly linked list.; Insertion and deletion require updating multiple references.; Implementation is more complex.; Incorrect pointer updates can break the connections in either direction.
Example or application
Representation
NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL
Explanation
The list can be traversed from 10 to 40 using next references or from 40 to 10 using previous references.
Definition
A doubly linked list is a sequence of nodes where each node maintains a reference to its predecessor and successor. The first node normally has a null previous reference, and the final node normally has a null next reference.
Purpose
Doubly linked lists are useful when an application needs forward and backward traversal or frequent insertion and deletion around nodes whose references are already available.
Node Structure
Previous
Reference to the preceding node.
Data
Stores the value or information.
Next
Reference to the following node.
Conceptual Representation
[Previous | Data | Next]
Main Components
Head: Reference to the first node.
Tail: Reference to the final node when maintained.
Previous reference: Connects a node to its predecessor.
Next reference: Connects a node to its successor.
Connection Pattern
Connections are bidirectional. Each pair of neighboring nodes maintains references to one another through their previous and next fields.
Forward Traversal
Begin at the head and repeatedly follow the next reference until the final node is reached.
Backward Traversal
Begin at the tail and repeatedly follow the previous reference until the first node is reached.
Insertion Methods
At the beginning: Connect the new node to the old head and update the old head's previous reference.
At the end: Connect the new node after the old tail and update the tail reference.
Before a known node: Update the new node's previous and next references and both neighboring connections.
After a known node: Update the new node's connections and the corresponding references of its neighbors.
Deletion Methods
From the beginning: Move the head to the second node and clear its previous reference.
From the end: Move the tail to the preceding node and clear its next reference.
From the middle: Connect the target node's predecessor directly to its successor in both directions.
Advantages
Supports forward and backward traversal.
Allows efficient deletion when a reference to the target node is available.
Supports insertion before or after a known node.
Can simplify navigation-based applications.
Limitations
Requires more memory than a singly linked list.
Insertion and deletion require updating multiple references.
Implementation is more complex.
Incorrect pointer updates can break the connections in either direction.
Time Complexity
Insert At Tail With Tail Reference
O(1)
Insert Before Or After Known Node
O(1)
Note
The stated constant-time insertion and deletion costs assume the required node references are already available.
Space Complexity
O(n) for n nodes, with two link references stored in each node.
Implementation Considerations
Update both previous and next references during insertion.
Update both neighboring nodes when deleting a middle node.
Handle empty lists and single-node lists.
Keep head.previous and tail.next null in a conventional non-circular implementation.
Ensure the head and tail references remain consistent.
Common Applications
Browser history navigation
Undo and redo systems
Music and video playlists with previous and next controls
Deque implementations
Navigation between connected records
Learning Objectives
Understand the structure of a doubly linked-list node.
Explain bidirectional connections.
Compare forward and backward traversal.
Describe insertion and deletion operations.
Identify the memory and complexity trade-offs.
Key Takeaways
Each node contains previous and next references.
Traversal can proceed in both directions.
A known node can be removed without searching for its predecessor.
The additional reference increases memory usage.
Correct updates to both links are essential.
Related Topics
Singly Linked Lists
Circular Doubly Linked Lists
Linked List Node and Memory Structure
Insertion in Linked Lists
Deletion in Linked Lists
Deque
Practice Questions
| Question | Answer |
|---|
What is the main purpose of doubly linked lists? | A doubly linked list is a linked data structure in which each node contains data and references to both the previous and next nodes. This structure supports traversal in both directions. |
What should be checked before applying doubly linked lists? | For doubly linked lists, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of doubly linked lists be validated? | Trace a representative doubly linked lists case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures