Doubly Linked List

Basics of Doubly Linked List

Hey Coders!
Let’s level up our understanding of linked lists by exploring the doubly linked list. We'll go through definitions, why it's needed, how to create and traverse one, and how to perform insertions and deletions at various positions.

List of Content:

• Definition
• Need of Doubly Linked List
• Creation and Traversal
• Insertion & Deletion Operations (Beginning, End, Specific Position)

Let’s get into it...

Definition:

A doubly linked list is a linear data structure where each node contains:

• Data
• Pointer to the previous node
• Pointer to the next node

This enables two-way traversal—both forward and backward.

Need of Doubly Linked List:

Doubly linked lists shine when:

• You want to traverse in both directions.
• You need efficient insertions/deletions from any position.
• Implementing features like undo/redo, history navigation, or deques.

Creation and Traversal:

In C :

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

void traverse(struct Node* head) {
    while (head != NULL) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

In Java :

class Node {
    int data;
    Node prev, next;
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

void traverse(Node head) {
    while (head != null) {
        System.out.print(head.data + " <-> ");
        head = head.next;
    }
    System.out.println("NULL");
}

In C++ :

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};

void traverse(Node* head) {
    while (head) {
        cout << head->data << " <-> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

Insertion Operations

In C :

Insert at Beginning :

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head != NULL) (*head)->prev = newNode;
    *head = newNode;
}

Insert at End :

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

Insert at Specific Position :

void insertAtPosition(struct Node** head, int pos, int data) {
    if (pos == 1) {
        insertAtBeginning(head, data);
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; temp && i < pos - 1; i++)
        temp = temp->next;
    if (!temp) return;
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = temp->next;
    newNode->prev = temp;
    if (temp->next) temp->next->prev = newNode;
    temp->next = newNode;
}

In Java :

Insert at Beginning :

Node insertAtBeginning(Node head, int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    if (head != null) head.prev = newNode;
    return newNode;
}

Insert at End :

void insertAtEnd(Node head, int data) {
    Node newNode = new Node(data);
    Node temp = head;
    while (temp.next != null) temp = temp.next;
    temp.next = newNode;
    newNode.prev = temp;
}

Insert at Specific Position :

void insertAtPosition(Node head, int pos, int data) {
    if (pos == 1) {
        insertAtBeginning(head, data);
        return;
    }
    Node temp = head;
    for (int i = 1; temp != null && i < pos - 1; i++)
        temp = temp.next;
    if (temp == null) return;
    Node newNode = new Node(data);
    newNode.next = temp.next;
    if (temp.next != null) temp.next.prev = newNode;
    temp.next = newNode;
    newNode.prev = temp;
}

In C++ :

Insert at Beginning :

void insertAtBeginning(Node*& head, int data) {
    Node* newNode = new Node(data);
    newNode->next = head;
    if (head) head->prev = newNode;
    head = newNode;
}

Insert at End :

void insertAtEnd(Node*& head, int data) {
    Node* newNode = new Node(data);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

Insert at Specific Position :

void insertAtPosition(Node*& head, int pos, int data) {
    if (pos == 1) {
        insertAtBeginning(head, data);
        return;
    }
    Node* temp = head;
    for (int i = 1; temp && i < pos - 1; i++) temp = temp->next;
    if (!temp) return;
    Node* newNode = new Node(data);
    newNode->next = temp->next;
    if (temp->next) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}

Deletion Operations

In C :

Delete from Beginning :

void deleteBeginning(struct Node** head) {
    if (*head == NULL) return;
    struct Node* temp = *head;
    *head = temp->next;
    if (*head) (*head)->prev = NULL;
    free(temp);
}

Delete from End :

void deleteEnd(struct Node** head) {
    if (*head == NULL) return;
    struct Node* temp = *head;
    while (temp->next) temp = temp->next;
    if (temp->prev) temp->prev->next = NULL;
    else *head = NULL;
    free(temp);
}

Delete at Specific Position :

void deleteAtPosition(struct Node** head, int pos) {
    if (*head == NULL) return;
    struct Node* temp = *head;
    if (pos == 1) {
        deleteBeginning(head);
        return;
    }
    for (int i = 1; temp && i < pos; i++) temp = temp->next;
    if (!temp) return;
    if (temp->prev) temp->prev->next = temp->next;
    if (temp->next) temp->next->prev = temp->prev;
    free(temp);
}

In Java :

Delete from Beginning :

Node deleteBeginning(Node head) {
    if (head == null) return null;
    head = head.next;
    if (head != null) head.prev = null;
    return head;
}

Delete from End :

void deleteEnd(Node head) {
    if (head == null) return;
    Node temp = head;
    while (temp.next != null) temp = temp.next;
    if (temp.prev != null) temp.prev.next = null;
}

Delete at Specific Position :

void deleteAtPosition(Node head, int pos) {
    if (head == null) return;
    Node temp = head;
    for (int i = 1; temp != null && i < pos; i++) temp = temp.next;
    if (temp == null) return;
    if (temp.prev != null) temp.prev.next = temp.next;
    if (temp.next != null) temp.next.prev = temp.prev;
}

In C++:

Delete from Beginning :

void deleteBeginning(Node*& head) {
    if (!head) return;
    Node* temp = head;
    head = head->next;
    if (head) head->prev = nullptr;
    delete temp;
}

Delete from End :

void deleteEnd(Node*& head) {
    if (!head) return;
    Node* temp = head;
    while (temp->next) temp = temp->next;
    if (temp->prev) temp->prev->next = nullptr;
    else head = nullptr;
    delete temp;
}

Delete at Specific Position :

void deleteAtPosition(Node*& head, int pos) {
    if (!head) return;
    if (pos == 1) {
        deleteBeginning(head);
        return;
    }
    Node* temp = head;
    for (int i = 1; temp && i < pos; i++) temp = temp->next;
    if (!temp) return;
    if (temp->prev) temp->prev->next = temp->next;
    if (temp->next) temp->next->prev = temp->prev;
    delete temp;
}

Summary:

Doubly linked lists are extremely versatile, supporting efficient insertions and deletions from anywhere in the list. With forward and backward navigation, they’re ideal for a variety of use-cases.

Next up : Circular Linked Lists – explore how the list connects end-to-start!

For more guides,click here.

Happy Coding!