The implementation of Double Linked List with C Programming

Introduction

A double-linked list is a linked list that contains two pointers

• The first pointer contains the link to the previous node.
• The second pointer contains the link to the next node.

What do we infer from this?

Consider that the two links in a double-linked list are called the left link (link for the previous node) and the right link(link for the next node).

What values will be the left link of the first node and the right link of the last node hold?

Obviously, the left link of the first node will hold a NULL pointer because there is no node before it, and the right link of the last node will contain a NULL pointer.

The below figure depicts a double-linked list.

Insertion in a Double Linked List.

• At the beginning
• In the Middle
• At the end

Adding a node to a Double Linked List at the beginning

Step 1. Allocate new nodes and copy data.

temp=ALLOCATE
temp->information=insert->information
temp->previous=NULL

Step 2. Make a new node point to the first node.

temp->next=begin

Step 3. The Original new node points to the first node points.

begin->previous=temp

Step 4. Adjust the beginning pointer.

begin=temp

Step 5. Terminate.

Exit

Adding a node to a Double Linked List in the Middle

Step 1. Allocate new nodes and copy data.

temp=ALLOCATE
temp->information=insert->information

Step 2. Make a new node point to the previous node before the current node in the list.

temp->previous=current->previous

Step 3. The old node should now point to the intermediate node.

begin->next=current

Step 4. Make the previous node the new node.

current->previous=temp

Step 5. The mode before the new node points to the newly allocated nodes.

temp->previous->next=temp

Step 6. Exit.

Adding a node to a Double Linked List in the End.

Step 1. Allocate new nodes and copy data.

temp=ALLOCATE
temp->information=insert->information
temp->next=NULL

Step 2. Make the last node point to the newly attached node.

end->next=temp

Step 3. Make the last node point to the previous node.

temp->previous=end

Step 4. Shift the end pointer.

end=temp

Step 5. Exit.

Consider a program to illustrate the creation and traversing in a double-linked list.

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

struct telephone {
    struct telephone *previous;
    int phone_no;
    char name_cust[20];
    char address[30];
    struct telephone *next;
};

struct telephone *nodepointer = NULL;

void _add() {
    struct telephone *new_node, *temp;

    new_node = (struct telephone *) malloc(sizeof(struct telephone));
    if (new_node == NULL) {
        printf("Unable to allocate memory...\n");
        exit(0);
    }

    printf("Enter phone number: ");
    scanf("%d", &new_node->phone_no);
    printf("Enter customer name: ");
    scanf("%s", new_node->name_cust);
    printf("Enter customer address: ");
    scanf("%s", new_node->address);

    new_node->next = NULL;
    new_node->previous = NULL;

    if (nodepointer == NULL) {
        nodepointer = new_node;
    } else {
        temp = nodepointer;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->previous = temp;
    }
}

void print_list() {
    struct telephone *temp = nodepointer;

    while (temp != NULL) {
        printf("\nPhone Number: %d", temp->phone_no);
        printf("\nCustomer Name: %s", temp->name_cust);
        printf("\nAddress: %s\n", temp->address);
        temp = temp->next;
    }
}

void main() {
    char answer = 'Y';
    clrscr();

    while (answer == 'y' || answer == 'Y') {
        _add();
        printf("\nWish to Add Another Record (Y/N): ");
        scanf(" %c", &answer);  // Added a space before %c to avoid newline character issues
    }

    print_list();
    getch();
}

Output

Summary

A Doubly Linked List in C programming is a linear data structure where each node consists of three components: a data field to store the actual data, a previous pointer (prev) that points to the preceding node, and a next pointer (next) that points to the succeeding node. Unlike singly linked lists, doubly linked lists allow traversal in both directions, forward and backward, making it more flexible for operations like insertion and deletion at any position in the list.

The basic operations in a doubly linked list include inserting nodes at the beginning, end, or a specified position, deleting nodes by updating the adjacent node pointers and traversing the list in either direction. The structure is commonly defined using struct in C, and memory for new nodes is dynamically allocated using malloc() and freed using free() when a node is deleted. The use of NULL helps indicate the start or end of the list, marking unassigned or empty pointers. This dynamic data structure provides efficient manipulation compared to arrays, especially in scenarios requiring frequent insertions or deletions.