A doubly circular linked list augmented with a sentinel node (dummy head) represents one of the most robust sequential data structures in low-level programming. Unlike singly linked variants, this architecture maintains bidirectional references and circular connectivity, enabling O(1) operations at both ends without special-casing empty lists or boundary conditions.

Node Structure

Each node maintains pointers to both successor and predecessor elements:

typedef int ValueType;

typedef struct LinkNode {
    struct LinkNode* back;
    struct LinkNode* forward;
    ValueType payload;
} LinkNode;

List Initialization

The sentinel node serves as an anchor point. Initially, its forward and backward pointers reference itself, establishing the circular invariant:

LinkNode* initialize_list(void) {
    LinkNode* header = malloc(sizeof(LinkNode));
    if (header == NULL) return NULL;
    
    header->forward = header;
    header->back = header;
    return header;
}

This dummy element stores no application data, eliminating the need for double-pointer indirection in modification operations.

Node Allocation

static LinkNode* allocate_node(ValueType data) {
    LinkNode* node = malloc(sizeof(LinkNode));
    if (node == NULL) return NULL;
    
    node->payload = data;
    node->forward = NULL;
    node->back = NULL;
    return node;
}

Generic Insertion

Inserting before an arbitrary position requires only local pointer manipulations:

void insert_at(LinkNode* position, ValueType data) {
    assert(position != NULL);
    
    LinkNode* incoming = allocate_node(data);
    LinkNode* predecessor = position->back;
    
    predecessor->forward = incoming;
    incoming->back = predecessor;
    incoming->forward = position;
    position->back = incoming;
}

Generic Deletion

Removing a specified node operates in constant time:

void erase_at(LinkNode* target) {
    assert(target != NULL && target->forward != target);
    
    LinkNode* left = target->back;
    LinkNode* right = target->forward;
    
    left->forward = right;
    right->back = left;
    free(target);
}

Boundary Operations

All positional operations reduce to the generic primitives:

void prepend(LinkNode* header, ValueType data) {
    insert_at(header->forward, data);
}

void append(LinkNode* header, ValueType data) {
    insert_at(header, data);
}

void remove_first(LinkNode* header) {
    assert(header->forward != header);
    erase_at(header->forward);
}

void remove_last(LinkNode* header) {
    assert(header->back != header);
    erase_at(header->back);
}

Traversal and Search

Iteration proceeds from the first data node until returning to the header:

void traverse(LinkNode* header) {
    assert(header != NULL);
    
    LinkNode* iter = header->forward;
    while (iter != header) {
        printf("%d ", iter->payload);
        iter = iter->forward;
    }
    printf("\n");
}

LinkNode* search(LinkNode* header, ValueType key) {
    LinkNode* iter = header->forward;
    while (iter != header) {
        if (iter->payload == key) return iter;
        iter = iter->forward;
    }
    return NULL;
}

Memory Reclamation

Deallocation must preserve the circualr refeernce to avoid premature access violations:

void deallocate_list(LinkNode* header) {
    if (header == NULL) return;
    
    LinkNode* iter = header->forward;
    while (iter != header) {
        LinkNode* next = iter->forward;
        free(iter);
        iter = next;
    }
    free(header);
}

Note that the external pointer referencing the header remains dangling after this operation; callers must manually nullify their handle to prevent undefined behavior.