C Program to Implement Doubly Linked List

1. Introduction

A doubly linked list is a type of linked list in which each node contains a data part and two pointers. The two pointers are:

1. A pointer to the next node in the sequence (next pointer).

2. A pointer to the previous node in the sequence (previous pointer).

This allows for a more flexible and efficient traversal in both forward and backward directions.

2. Program Overview

In this program, we will:

1. Define the basic structure of a node in a doubly linked list.

2. Implement functions to:

- Create a new node.

- Insert an element at the beginning of the list.

- Display the linked list in forward and reverse order.

- Delete a node from the doubly linked list.

3. Code Program

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

// Define the node structure for a doubly linked list
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 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 insert an element at the beginning of the doubly linked list
void insertBegin(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    if (*head != NULL)
        (*head)->prev = newNode;
    *head = newNode;
}

// Function to display the doubly linked list in forward order
void displayListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward order: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to display the doubly linked list in reverse order
void displayListReverse(struct Node* head) {
    struct Node* temp = head;
    if (temp == NULL) return;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    printf("Reverse order: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

// Function to delete a node from the doubly linked list
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }
    if (temp == NULL) return;  // Key was not found
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    } else {
        *head = temp->next;
    }
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    free(temp);
}

int main() {
    struct Node* head = NULL;
    insertBegin(&head, 40);
    insertBegin(&head, 30);
    insertBegin(&head, 20);
    insertBegin(&head, 10);
    displayListForward(head);
    displayListReverse(head);
    printf("\nDeleting node 30:\n");
    deleteNode(&head, 30);
    displayListForward(head);
    return 0;
}

Output:

Forward order: 10 <-> 20 <-> 30 <-> 40 <-> NULL
Reverse order: 40 <-> 30 <-> 20 <-> 10 <-> NULL

Deleting node 30:
Forward order: 10 <-> 20 <-> 40 <-> NULL

4. Step By Step Explanation

1. We start by defining the structure of a node using the struct keyword. The Node has integer data and pointers to the next and previous nodes.

2. The createNode function helps in creating a new node with the given data.

3. The insertBegin function is used to insert an element at the beginning of the doubly linked list.

4. To display the doubly linked list in forward and reverse order, we use the displayListForward and displayListReverse functions respectively.

5. The deleteNode function is designed to delete a node from the list based on a given key.

6. In the main function, we demonstrate various operations on the doubly linked list.