Structural Definition

A headed circular doubly linked list utilizes a sentinel node (head) that acts as a starting point. Unlike a singly linked list, each node contains two pointers: prev pointing to the predecessor and next pointing to the successor. The sentinel node's prev points to the tail, and the tail's next points back to the sentinel, forming a closed loop. This structure allows for O(1) access to both the head and the tail of the list.

typedef int DataType;

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

Initialization

Initialization involves allocating the sentinel node. Since the list is initially empty, the sentinel node's pointers must reference itself to maintain the circular property.

CNode* ListInit() {
    CNode* pSentinel = (CNode*)malloc(sizeof(CNode));
    if (pSentinel == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    pSentinel->val = -1; // Sentinel data is typically unused
    pSentinel->prev = pSentinel;
    pSentinel->next = pSentinel;
    return pSentinel;
}

Node Creation Helper

Before performing insertions, a helper function is necessary to allocate new nodes and handle memory allocation errors.

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

Insertion Operations

The circular nature simplifies insertion logic, as the sentinel node provides immediate access to both ends of the list.

Head Insertion

To insert at the front, the new node is placed immediately after the sentinel node.

void ListPushFront(CNode* pSentinel, DataType x) {
    assert(pSentinel);
    CNode* newNode = CreateNode(x);
    
    newNode->next = pSentinel->next;
    newNode->prev = pSentinel;
    
    pSentinel->next->prev = newNode;
    pSentinel->next = newNode;
}

Tail Insertion

Inserting at the back requires linking the new node before the sentinel node. The sentinel's prev pointer acts as the tail pointer.

void ListPushBack(CNode* pSentinel, DataType x) {
    assert(pSentinel);
    CNode* newNode = CreateNode(x);
    
    newNode->prev = pSentinel->prev;
    newNode->next = pSentinel;
    
    pSentinel->prev->next = newNode;
    pSentinel->prev = newNode;
}

Deletion Operations

Deletion requires checks to ensure the list is not empty (i.e., the sentinel does not point to itself).

Head Deletion

The node immediately following the sentinel is removed.

void ListPopFront(CNode* pSentinel) {
    assert(pSentinel && pSentinel->next != pSentinel);
    CNode* target = pSentinel->next;
    
    target->next->prev = pSentinel;
    pSentinel->next = target->next;
    
    free(target);
    target = NULL;
}

Tail Deletion

The node immediately preceding the sentinel is removed.

void ListPopBack(CNode* pSentinel) {
    assert(pSentinel && pSentinel->prev != pSentinel);
    CNode* target = pSentinel->prev;
    
    target->prev->next = pSentinel;
    pSentinel->prev = target->prev;
    
    free(target);
    target = NULL;
}

Lookup and Positional Operations

Finding a node involves traversing from the sentinel's next until the loop returns to the sentinel.

CNode* ListFind(CNode* pSentinel, DataType x) {
    assert(pSentinel);
    CNode* current = pSentinel->next;
    while (current != pSentinel) {
        if (current->val == x) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Insertion at Position

This function inserts a new node after a specified valid position.

void ListInsertAfter(CNode* pSentinel, CNode* pos, DataType x) {
    assert(pSentinel && pos);
    CNode* newNode = CreateNode(x);
    
    newNode->prev = pos;
    newNode->next = pos->next;
    
    pos->next->prev = newNode;
    pos->next = newNode;
}

Erasure at Position

This function unlinks a specific node from the chain and frees its memory.

void ListErase(CNode* pSentinel, CNode* pos) {
    assert(pSentinel && pos && pos != pSentinel);
    
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    
    free(pos);
    pos = NULL;
}

Memory Management

To prevent memory leaks, the list must be destroyed by iterating through all valid nodes and freeing them before freeing the sentinel.

void ListDestroy(CNode* pSentinel) {
    assert(pSentinel);
    CNode* current = pSentinel->next;
    while (current != pSentinel) {
        CNode* nextNode = current->next;
        free(current);
        current = nextNode;
    }
    free(pSentinel);
}