Introduction to Doubly Linked Lists

In a singly linked list, each node contains only a pointer too its successor, which creates a limitation: accessing a node's predecessor requires traversing the list from the beginning. This results in O(1) time compelxity for accessing the next node but O(n) for accessing the previous node. Doubly linked lists solve this problem by maintaining two pointers in each node.

A doubly linked list node contains two pointers: prev pointing to the predecessor and next pointing to the successor. The node structure can be defined as follows:

typedef int DataType;

typedef struct DListNode {
    DataType val;
    struct DListNode* next;
    struct DListNode* prev;
} DListNode;

Using DataType instead of directly using int provides flexibility for future type modifications.

Implementation

Creating a New Node

Before initialization, we need a function to allocate and create new nodes:

DListNode* CreateNode(DataType value) {
    DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    if (node == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    
    node->val = value;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

List Initialization

The initialization creates a sentinel (head) node that points to itself, forming a circular structure:

DListNode* ListInit() {
    DListNode* head = CreateNode(-1);
    head->next = head;
    head->prev = head;
    return head;
}

The sentinel node must point to itself; otherwise, the pointers would be NULL, breaking the circular structure.

Printing the List

void ListPrint(DListNode* head) {
    assert(head != NULL);
    
    DListNode* current = head->next;
    while (current != head) {
        printf("%d -> ", current->val);
        current = current->next;
    }
    printf("NULL\n");
}

The loop condition current != head prevents infinite iteration since the list is circular.

Ensertion Operations

Tail Insertion:

void ListPushBack(DListNode* head, DataType value) {
    assert(head != NULL);
    
    DListNode* newNode = CreateNode(value);
    DListNode* last = head->prev;
    
    // Link new node between last and head
    last->next = newNode;
    newNode->prev = last;
    newNode->next = head;
    head->prev = newNode;
}

Head Insertion:

void ListPushFront(DListNode* head, DataType value) {
    assert(head != NULL);
    
    DListNode* newNode = CreateNode(value);
    DListNode* first = head->next;
    
    // Link new node between head and first
    newNode->next = first;
    newNode->prev = head;
    head->next = newNode;
    first->prev = newNode;
}

Deletion Operations

Head Deletion:

void ListPopFront(DListNode* head) {
    assert(head != NULL);
    assert(head->next != head);  // List is not empty
    
    DListNode* target = head->next;
    DListNode* newFirst = target->next;
    
    head->next = newFirst;
    newFirst->prev = head;
    
    free(target);
}

Tail Deletion:

void ListPopBack(DListNode* head) {
    assert(head != NULL);
    assert(head->next != head);
    
    DListNode* target = head->prev;
    DListNode* newLast = target->prev;
    
    newLast->next = head;
    head->prev = newLast;
    
    free(target);
}

Insertion at Arbitrary Position

void ListInsert(DListNode* position, DataType value) {
    assert(position != NULL);
    
    DListNode* newNode = CreateNode(value);
    DListNode* previous = position->prev;
    
    // Insert before position
    previous->next = newNode;
    newNode->prev = previous;
    newNode->next = position;
    position->prev = newNode;
}

Deletion at Arbitrary Position

void ListErase(DListNode* position) {
    assert(position != NULL);
    
    DListNode* before = position->prev;
    DListNode* after = position->next;
    
    before->next = after;
    after->prev = before;
    
    free(position);
}

Finding an Element

DListNode* ListFind(DListNode* head, DataType value) {
    assert(head != NULL);
    
    DListNode* current = head->next;
    while (current != head) {
        if (current->val == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // Not found
}

Destroying the List

void ListDestroy(DListNode* head) {
    assert(head != NULL);
    
    DListNode* current = head->next;
    while (current != head) {
        DListNode* temp = current->next;
        free(current);
        current = temp;
    }
    free(head);
}

Complete Header File

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct DListNode {
    DataType val;
    struct DListNode* next;
    struct DListNode* prev;
} DListNode;

// Initialization
DListNode* ListInit();

// Node creation
DListNode* CreateNode(DataType value);

// Print
void ListPrint(DListNode* head);

// Insertion
void ListPushBack(DListNode* head, DataType value);
void ListPushFront(DListNode* head, DataType value);
void ListInsert(DListNode* position, DataType value);

// Deletion
void ListPopFront(DListNode* head);
void ListPopBack(DListNode* head);
void ListErase(DListNode* position);

// Search
DListNode* ListFind(DListNode* head, DataType value);

// Cleanup
void ListDestroy(DListNode* head);

Example Usage

#include "DList.h"

int main() {
    DListNode* list = ListInit();
    
    ListPushBack(list, 10);
    ListPushBack(list, 20);
    ListPushBack(list, 30);
    ListPushFront(list, 5);
    
    ListPrint(list);  // Output: 5 -> 10 -> 20 -> 30 -> NULL
    
    DListNode* found = ListFind(list, 20);
    if (found != NULL) {
        ListErase(found);
    }
    
    ListPrint(list);  // Output: 5 -> 10 -> 30 -> NULL
    
    ListDestroy(list);
    return 0;
}