A doubly circular linked list supports core operations such as initialization, destruction, emptiness checking, traversal, insertion, deletion, search, and modification. Insertion and deletion can further be categorized into head/tail vraiants.

This implementation is organized across three files:

• List.h: Declares the node structure and function prototypes.
• List.c: Defines all declared functions.
• Test.c: Contains test cases to validate functionality.

List.h – Header File

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

typedef int LTDataType;

typedef struct ListNode {
    struct ListNode* prev;
    struct ListNode* next;
    LTDataType data;
} LTNode;

LTNode* LTInit(void);
void LTDestory(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);

void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);

void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

void LTUpdate(LTNode* pos, LTDataType x);

List.c – Implementation File

Helper: Node Allocation

LTNode* CreateNode(LTDataType value) {
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (!node) {
        perror("Failed to allocate node");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

Initialization

LTNode* LTInit(void) {
    LTNode* sentinel = CreateNode(0);
    sentinel->next = sentinel;
    sentinel->prev = sentinel;
    return sentinel;
}

Destruction

void LTDestory(LTNode* phead) {
    assert(phead);
    LTNode* current = phead->next;
    while (current != phead) {
        LTNode* next = current->next;
        free(current);
        current = next;
    }
    free(phead);
}

Emptiness Check

bool LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead;
}

Traversal and Print

void LTPrint(LTNode* phead) {
    assert(phead);
    printf("HEAD<=>");
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

Head Insertion

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* new_node = CreateNode(x);
    new_node->next = phead->next;
    new_node->prev = phead;
    phead->next->prev = new_node;
    phead->next = new_node;
}

Head Deletion

void LTPopFront(LTNode* phead) {
    assert(phead && !LTEmpty(phead));
    LTNode* target = phead->next;
    phead->next = target->next;
    target->next->prev = phead;
    free(target);
}

Tail Insertion

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* new_node = CreateNode(x);
    new_node->prev = phead->prev;
    new_node->next = phead;
    phead->prev->next = new_node;
    phead->prev = new_node;
}

Tail Deletion

void LTPopBack(LTNode* phead) {
    assert(phead && !LTEmpty(phead));
    LTNode* target = phead->prev;
    phead->prev = target->prev;
    target->prev->next = phead;
    free(target);
}

Generic Insertion

void LTInsert(LTNode* position, LTDataType x) {
    assert(position);
    LTNode* new_node = CreateNode(x);
    LTNode* prior = position->prev;
    prior->next = new_node;
    new_node->prev = prior;
    new_node->next = position;
    position->prev = new_node;
}

Generic Deletion

void LTErase(LTNode* node) {
    assert(node);
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

Search

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

Update

void LTUpdate(LTNode* node, LTDataType x) {
    assert(node);
    node->data = x;
}

Test.c – Validation Examples

The test file verifies all operations:

• Insertions at head and tail
• Deletinos from head and tail
• Arbitrary insertions and deletions using position pointers
• Search followed by update or removal