Doubly Linked List Program in C: A Comprehensive Guide

A Doubly Linked List in C is a versatile data structure that connects nodes in a sequential chain using pointers. Each node in this list consists of three essential components:

• Data: Stores the actual value or information of the node.
• Previous Pointer: Contains the address of the preceding node in the sequence, allowing backward traversal.
• Next Pointer: Holds the address of the next node, enabling forward traversal.

Now, let’s use an example to see how a doubly linked list program in a data structure in C can be represented with the code. 

But first, the following key components must be defined: 

• Node: The fundamental building block of a doubly linked list. Each node contains three parts: the data item, a pointer to the next node, and a pointer to the previous node.
• Next Pointer: Points to the next node in the sequence, enabling forward traversal.
• Previous Pointer: Points to the preceding node, allowing backward traversal.
• Data: Holds the value stored in the node.
• Head: Marks the starting point of the doubly linked list. It is the entry point to access the entire structure

In the code, the single node is represented as:

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

Each struct node contains a data element and two pointers: one to the preceding node and one pointer to the next node.

Here’s a simple doubly linked list program in c with three nodes to understand how it works:

#include <stdio.h>
#include <stdlib.h>

// Structure for a node in a doubly linked list
struct Node {
    int data;               // Data stored in the node
    struct Node *next;      // Pointer to the next node
    struct Node *prev;      // Pointer to the previous node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1); // Exit the program if memory allocation fails
    }
    newNode->data = data;   // Set the data
    newNode->next = NULL;   // Initialize next pointer to NULL
    newNode->prev = NULL;   // Initialize prev pointer to NULL
    return newNode;
}

// Function to print the doubly linked list in forward order
void printList(struct Node* head) {
    struct Node* temp = head;
    printf("Forward Traversal: ");
 while (temp != NULL) {
        printf("%d ", temp->data); // Print the data in each node
        if (temp->next == NULL) {
            break;  // Stop when we reach the last node
        }
        temp = temp->next;  // Move to the next node
    }
    printf("\n");

    // Call the reverse traversal function starting from the last node
    printf("Reverse Traversal: ");
    while (temp != NULL) {
        printf("%d ", temp->data); // Print the data in each node
        temp = temp->prev;         // Move to the previous node
    }
    printf("\n");
}

// Function to free memory allocated for the list
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;         // Store the current node
        head = head->next;   // Move to the next node
        free(temp);          // Free the current node
    }
}

int main() {
    // Create nodes
    struct Node* node1 = createNode(10);  // First node
    struct Node* node2 = createNode(20);  // Second node
    struct Node* node3 = createNode(30);  // Third node

    // Link nodes
    node1->next = node2;
    node2->prev = node1;
    node2->next = node3;
    node3->prev = node2;

    // Print the list with forward and reverse traversal
    printList(node1);

    // Free allocated memory
    freeList(node1);

    return 0;
}

Output:

Forward Traversal : 10 20 30
Reverse Traversal : 30 20 10

• The prev stores null for node one as there is no node before it. Its value is 10 and the next stores the address of node two. 
• For node two, the prev stores one as the pointer. Its value is 20, and the next store is the address of node three. 
• For node three, the prev stores two as the pointer. Its value is 30, and the next store is null.  
• The printList function prints the list in both forward and reverse directions. 
• First, it traverses from the head to the last node using the next pointers. Then it traverses backward from the last node to the head using the prev pointers.

Adding a node to a doubly linked list is similar to inserting a node in a singly linked list, but it requires additional steps to manage the prev pointer for backward traversal.

In a doubly linked list, nodes can be inserted at three positions:

1. At the Beginning: The new node becomes the head of the list.
2. In Between Nodes: The new node is inserted between two existing nodes.
3. At the End: The new node is appended as the last node of the list.

For example, consider a doubly linked list with elements 1, 2, and 3. These operations allow flexible modification of the list structure.

Insertion

As discussed above, the insertion of nodes can be done in the beginning, in between or at the end. Let’s look at the example of insertion at the beginning: 

In this example, we’ll add a node of value 6 to the beginning of the doubly linked list. 

1. First, we create the new node by allocating memory for the newnode and assigning data to the newnode. 

      2. Second the prev and next pointers are set for the new node. The next of the newnode is is pointed to the first node in the list. Then the prev of the new node is           pointed to the null.

Next, we make the new node as head node. For this the prev of the first node (formerly head node) is pointed to the newnode. Then point head to the newnode.

Here’s the doubly linked list in the data structure program in c for insertion at the beginning. This code shows the above example:  

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a node
struct Node {
    int data;               // Data part of the node
    struct Node* next;      // Pointer to the next node
    struct Node* prev;      // Pointer to the previous node
};

// Function to insert a node at the front of the doubly linked list
void insertFront(struct Node** head, int data) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) { // Check if memory allocation succeeded
        printf("Memory allocation failed\n");
        return;
    }

    // Assign data to the new node
    newNode->data = data;

    // Set the next pointer of the new node to the current head
    newNode->next = *head;

    // Set the prev pointer of the new node to NULL
    newNode->prev = NULL;

    // If the list is not empty, update the previous pointer of the current head
    if (*head != NULL) {
        (*head)->prev = newNode;
    }

    // Update the head to point to the new node
    *head = newNode;
}
// Function to print the doubly linked list
void printList(struct Node* head) {
    struct Node* temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Driver code to test the insertFront function
int main() {
    struct Node* head = NULL; // Initialize an empty doubly linked list

    // Create a list with nodes 1, 2, and 3
    insertFront(&head, 3); // List: 3
    insertFront(&head, 2); // List: 2 -> 3
    insertFront(&head, 1); // List: 1 -> 2 -> 3

    // Insert new node with value 6 at the front
    insertFront(&head, 6); // List: 6 -> 1 -> 2 -> 3

    // Print the doubly linked list
    printList(head);

    return 0;
}

Output:

Doubly Linked List : 6 1 2 3

Deletion

Deletion can also be done similar to insertion from three different positions. We’ll take a look at an example for how it can be done in the beginning on the same original doubly linked list as above.

To delete the first node (head node) in a doubly linked list, the head pointer is updated to point to the next node (head = head->next), making the second node the new head. If the new head is not NULL, its previous pointer is set to NULL to ensure there is no reference to the deleted node.

Finally, the memory of the old head node is freed to remove it from the list.

Code to delete the first node:

#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
    int data;               // Data part of the node
    struct Node* next;      // Pointer to the next node
    struct Node* prev;      // Pointer to the previous node
};

// Function to insert a node at the front of the doubly linked list
void insertFront(struct Node** head, int data) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) { // Check if memory allocation succeeded
        printf("Memory allocation failed\n");
        return;
    }

    // Assign data to the new node
    newNode->data = data;

    // Set the next pointer of the new node to the current head
    newNode->next = *head;

    // Set the prev pointer of the new node to NULL
    newNode->prev = NULL;

    // If the list is not empty, update the previous pointer of the current head
    if (*head != NULL) {
        (*head)->prev = newNode;
    }

    // Update the head to point to the new node
    *head = newNode;
}

// Function to delete the first node in the doubly linked list
void deleteFirstNode(struct Node** head) {
    // Check if the list is empty
    if (*head == NULL) {
        printf("The list is empty, nothing to delete.\n");
        return;
    }

    // Store the old head node temporarily
    struct Node* temp = *head;

    // Update head to the next node
    *head = (*head)->next;

    // If the new head is not NULL, set its prev to NULL
    if (*head != NULL) {
        (*head)->prev = NULL;
    }

    // Free the memory of the old head
    free(temp);
}

// Function to print the doubly linked list
void printList(struct Node* head) {
    struct Node* temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Driver code to test the insertFront and deleteFirstNode functions
int main() {
    struct Node* head = NULL; // Initialize an empty doubly linked list

    // Create a list with nodes 1, 2, and 3
    insertFront(&head, 3); // List: 3
    insertFront(&head, 2); // List: 2 -> 3
    insertFront(&head, 1); // List: 1 -> 2 -> 3

    // Print the list before deleting the first node
    printf("Before deleting the first node:\n");
    printList(head);

    // Delete the first node
    deleteFirstNode(&head); // List after deletion: 2 -> 3

    // Print the list after deleting the first node
    printf("After deleting the first node:\n");
    printList(head);

    return 0;
}

Output:

before deleting the first node:
Doubly Linked List : 1 2 3
After deleting the first node:
Doubly linked List : 2 3

Traversal

Traversal across the doubly linked list can be performed in the forward and backward manner. The forward traversal starts by initializing a pointer to the head of the list. As long as the pointer is not null, the data at the current node is visited. Then the pointer is moved to the next node. 

For backward traversal, the process begins by initializing a pointer to the tail of the list. Similarly, as long as the pointer is not null, the data at the current node is visited. Then the pointer is moved to the previous node.

The code for traversal is as follows: 

#include <stdio.h>
#include <stdlib.h>

// Define the Node structure
struct Node {
    int data; // Data stored in the node
    struct Node* next; // Pointer to the next node
    struct Node* prev; // Pointer to the previous node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}
/ Function to traverse the doubly linked list 
// in forward direction
void forwardTraversal(struct Node* head) {
  
    // Start traversal from the head of the list
    struct Node* curr = head;

    // Continue until the current node is not
    // null (end of list)
    while (curr != NULL) {
      
        // Output data of the current node
        printf("%d ", curr->data);
      
        // Move to the next node
        curr = curr->next;
    }

    // Print newline after traversal
    printf("\n");
}

// Function to traverse the doubly linked list 
// in backward direction
void backwardTraversal(struct Node* tail) {
  
    // Start traversal from the tail of the list
    struct Node* curr = tail;

    // Continue until the current node is not 
    // null (end of list)
    while (curr != NULL) {
      
        // Output data of the current node
        printf("%d ", curr->data);
      
        // Move to the previous node
        curr = curr->prev;
    }

    // Print newline after traversal
    printf("\n");
}

int main() {
  
    // Sample usage of the doubly linked list and 
    // traversal functions
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    struct Node* third = createNode(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    printf("Forward Traversal:\n");
    forwardTraversal(head);

    printf("Backward Traversal:\n");
    backwardTraversal(third);

    // Free memory allocated for nodes
    free(head);
    free(second);
    free(third);

    return 0;
}

Output:

Forward Traversal:
1 2 3
Backward traversal:
3 2 1

The key applications of doubly linked list in C include the following:

• They are used in web browsers for forward and backward navigation
• They are used in employee management systems to hold and modify employee information
• Enables efficient implementation of undo/redo operations in applications
• Helps in efficient allocation and deallocation of memory in systems
• Stores and navigates through the history of visited websites
• Efficiently handles elements in a queue with operations at both ends

Learning about doubly linked lists in C is crucial for anyone advancing in software development. It strengthens the understanding of fundamental data structures and memory management. Mastering this concept lays the groundwork for tackling more complex algorithms and systems. To learn more and build your foundation for a career in software, enroll to the CCBP 4.0 Academy course.

1. What is a Doubly Linked List?

A doubly linked list is a data structure where each node contains data, a pointer to the next node, and a pointer to the previous node. It allowing traversal in both directions. 

2. How is a Doubly Linked List Represented in C?

In C, a doubly linked list is represented using a struct, where each node has three components: data, a pointer to the next node, and a pointer to the previous node. The list is manipulated using pointers to these nodes.

3. What are the Basic Operations that can be Performed on a Doubly Linked List in C?

Basic operations on a doubly linked list include insertion (at the beginning, end, or in-between), deletion (of nodes), traversal (in both directions), and searching for elements. 

4. What are the Advantages of a Doubly Linked List over a Singly Linked List?

Doubly linked lists allow traversal in both forward and backward directions which makes them more flexible than singly linked lists. They also enable deletion and insertion at both ends of the list.

5. What are the Applications of Doubly Linked List?

Doubly linked lists are used in applications like browser history management, music and video player playlists, undo/redo functionality in software, and memory management systems.