✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-043

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.

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

Nodes

  • 10

  • 20

  • 30

  • 40

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

Access By Index

O(n)

Search

O(n)

Forward Traversal

O(n)

Backward Traversal

O(n)

Insert At Head

O(1)

Insert At Tail With Tail Reference

O(1)

Insert Before Or After Known Node

O(1)

Delete 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

QuestionAnswer

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