Doubly Linked List


A doubly linked list is a type of linked list in which each node contains a data element and two pointers, one pointing to the next node in the sequence (like a regular linked list) and another pointing to the previous node. This bidirectional linking enables easy traversal in both directions.

Here's a breakdown of the doubly linked list and various operations:

Doubly Linked List Structure:

A node in a doubly linked list typically looks like this in a C-style struct:

Doubly Linked List Node Structure

struct Node 
{ int data; 
struct Node* next; 
struct Node* prev; 
};
data: Holds the actual data of the node.
next: Points to the next node in the list.
prev: Points to the previous node in the list.



Doubly Linked List Operations:

Insertion:

At the beginning (prepend):
Create a new node.
Set its next to the current head.
Set the prev of the current head to the new node.
Update the head to the new node.


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

    if (head != NULL) {
        head->prev = newNode;
    }

    return newNode;
}

At the end (append):
Create a new node.
Set its prev to the current tail.
Set the next of the current tail to the new node.
Update the tail to the new node.

struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = head;

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        return newNode;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode;
    newNode->prev = last;

    return head;
}


In the middle (insert after a specific node):
Create a new node.
Set its next to the next node of the specified node.
Set its prev to the specified node.
Update the next of the specified node to the new node.
Update the prev of the next node to the new node.


struct Node* insertAfter(struct Node* head, struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL");
        return head;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    prevNode->next = newNode;

    if (newNode->next != NULL) {
        newNode->next->prev = newNode;
    }

    return head;
}


Deletion:
Image credit:geeksforgeeks

At the beginning:
Update the next of the head to the next node.
Update the prev of the new head to NULL.
Free the memory of the old head.

struct Node* deleteAtBeginning(struct Node* head) {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return NULL;
    }

    struct Node* temp = head;
    head = temp->next;

    if (head != NULL) {
        head->prev = NULL;
    }

    free(temp);
    return head;
}



At the end:
Update the prev of the tail to the previous node.
Update the next of the new tail to NULL.
Free the memory of the old tail.

struct Node* deleteAtEnd(struct Node* head) {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return NULL;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    if (temp->prev != NULL) {
        temp->prev->next = NULL;
    } else {
        head = NULL;
    }

    free(temp);
    return head;
}


In the middle (delete a specific node):
Update the next of the previous node to the next node of the specified node.
Update the prev of the next node to the previous node of the specified node.
Free the memory of the specified node.

struct Node* deleteNode(struct Node* head, struct Node* delNode) {
    if (head == NULL || delNode == NULL) {
        printf("List is empty or node to be deleted is NULL.\n");
        return head;
    }

    if (delNode->prev != NULL) {
        delNode->prev->next = delNode->next;
    } else {
        head = delNode->next;
    }

    if (delNode->next != NULL) {
        delNode->next->prev = delNode->prev;
    }

    free(delNode);
    return head;
}



Traversal(Display):
Traverse the list from the head to the tail or vice versa using the next and prev pointers.

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

Search:
Traverse the list and compare the data of each node with the target value until the node is found or the end of the list is reached.

Advantages of Doubly Linked List:
    Bidirectional Traversal: Easy traversal in both directions.
    Insertion and Deletion: Efficient insertion and deletion operations at both ends and in the middle.
    We can quickly insert a new node before a given node.
    In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous     node, sometimes the list is traversed. In DLL, we can get the previous node using the previous        
    pointer  
Disadvantages:
    Extra Memory: Requires extra memory for the prev pointers.
    All operations require an extra pointer previous to be maintained. For example, in insertion, we need      to modify previous pointers together with the next pointers.
Complexity: 
    Slightly more complex implementation compared to singly linked lists.
    Algorithms Complexity:
    Insertion/Deletion at the beginning or end: O(1)
    Insertion/Deletion in the middle: O(n) (where n is the number of nodes)
    Search: O(n)

These complexities are based on the assumption that you have a reference to the node where you want to perform insertion, deletion, or search. If you need to search for a node first, additional time will be required.


Doubly Linked List- C program Implementation
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>

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



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

    if (head != NULL) {
        head->prev = newNode;
    }

    return newNode;
}

struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = head;

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        return newNode;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode;
    newNode->prev = last;

    return head;
}

struct Node* insertAfter(struct Node* head, struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL");
        return head;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    prevNode->next = newNode;

    if (newNode->next != NULL) {
        newNode->next->prev = newNode;
    }

    return head;
}

struct Node* deleteAtBeginning(struct Node* head) {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return NULL;
    }

    struct Node* temp = head;
    head = temp->next;

    if (head != NULL) {
        head->prev = NULL;
    }

    free(temp);
    return head;
}

struct Node* deleteAtEnd(struct Node* head) {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return NULL;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    if (temp->prev != NULL) {
        temp->prev->next = NULL;
    } else {
        head = NULL;
    }

    free(temp);
    return head;
}

struct Node* deleteNode(struct Node* head, struct Node* delNode) {
    if (head == NULL || delNode == NULL) {
        printf("List is empty or node to be deleted is NULL.\n");
        return head;
    }

    if (delNode->prev != NULL) {
        delNode->prev->next = delNode->next;
    } else {
        head = delNode->next;
    }

    if (delNode->next != NULL) {
        delNode->next->prev = delNode->prev;
    }

    free(delNode);
    return head;
}

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

int main() {
    struct Node* head = NULL;

    head = insertAtEnd(head, 10);
    head = insertAtBeginning(head, 5);
    head = insertAfter(head, head->next, 7);
    head = insertAfter(head, head->next, 100);
    head = insertAfter(head, head, 200);
    printf("Doubly Linked List: ");
    traverse(head);

    head = deleteNode(head, head->next); // Delete the node with data 5

    printf("Doubly Linked List after deletion: ");
    traverse(head);

    head = deleteAtBeginning(head);
    printf("Doubly Linked List after deletion at the beginning: ");
    traverse(head);

    head = deleteAtEnd(head);
    printf("Doubly Linked List after deletion at the end: ");
    traverse(head);

    return 0;
}




Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more