What Is a Double Linked List in Data Structure?

//

Angela Bailey

A double linked list is a data structure that consists of a sequence of nodes. Each node contains two pointers, one pointing to the previous node and the other pointing to the next node in the sequence. This allows for efficient traversal in both directions, hence the name “double linked list”.

Advantages of Double Linked List

  • Bi-directional traversal: Unlike a singly linked list, which only allows forward traversal, a double linked list enables both forward and backward traversal.
  • Efficient insertion and deletion: Inserting or deleting a node in a double linked list is more efficient compared to an array or a singly linked list because it does not require shifting elements.
  • Flexibility: Double linked lists can be easily modified to implement other data structures such as stacks, queues, and circular lists.

Structure of a Double Linked List Node

A double linked list node typically consists of three components:

  • Data: The actual data stored in the node.
  • Previous Pointer: A pointer that points to the previous node in the sequence. For the first node, this pointer will be NULL.
  • Next Pointer: A pointer that points to the next node in the sequence. For the last node, this pointer will be NULL.

An Example

To better understand how a double linked list works, let’s consider an example where we want to store names of fruits in a double linked list.

We start by creating three nodes: Node A (with data “Apple”), Node B (with data “Banana”), and Node C (with data “Cherry”).

Node A will have its previous pointer set to NULL and its next pointer set to Node B. Node B will have its previous pointer set to Node A and its next pointer set to Node C. Finally, Node C will have its previous pointer set to Node B and its next pointer set to NULL.

This arrangement creates a sequence of nodes with bi-directional links, allowing us to traverse the list from both ends.

Operations on Double Linked List

Double linked lists support various operations, including:

  • Insertion: Inserting a node can be done at the beginning, end, or at a specific position within the list.
  • Deletion: Deleting a node can also be performed at the beginning, end, or at a specific position within the list.
  • Traversal: Traversing the double linked list allows you to access each node in the sequence, either forward or backward.

Doubly Linked List Example in C++

#include <iostream>
using namespace std;

struct Node {
    string data;
    Node* prev;
    Node* next;
};

int main() {
    // Creating nodes
    Node* A = new Node();
    A->data = "Apple";
    A->prev = NULL;

    Node* B = new Node();
    B->data = "Banana";
    B->prev = A;

    Node* C = new Node();
    C->data = "Cherry";
    C->prev = B;
  
    // Linking nodes
    A->next = B;
    B->next = C;
    C->next = NULL;

    // Traversing the list forward
    Node* current = A;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }

    cout << endl;

    // Traversing the list backward
    current = C;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->prev;
    }

    return 0;
}

In this example, we create three nodes and link them together to form a double linked list. We then traverse the list forward and backward to display the data stored in each node.

Conclusion

A double linked list is a versatile data structure that allows for efficient traversal in both directions. It provides flexibility, efficient insertion and deletion operations, and can be used to implement various other data structures. Understanding and implementing double linked lists can greatly enhance your ability to solve complex problems efficiently.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy