A doubly linked list is a linear data structure where each node contains two pointers: one to the next node and another to the previous node. This design enables bidirectional traversal, making operations like insertion and deletion more flexible compared to singly linked lists.

The core structure of a node in this implementation uses an integer data type and two pointers:

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

To simplify management and avoid edge cases during insertions and deletions, a sentinel node (also known as a dummy head) is used. This node acts as both the start and end of the list, forming a circular structure where next points to the first real element and prev points to the last.

Initialization is performed by allocating a single node that links to itself:

LTNode* LTBuyNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (!newnode) {
        perror("malloc failed");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode;
    return newnode;
}

// Preferred initialization method
LTNode* newLTInit() {
    return LTBuyNode(-1);
}

Printing the list leverages the sentinel node to detect the end of traversal:

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

Insertion at the back involves updating the previous node’s next, the sentinel’s prev, and linking the new node properly:

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

Similarly, front insertion updates the sentinel's next and the next node’s prev:

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

Finding a node with a specific value requires traversing from the first real node until reaching the sentinel again:

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

Inserting after a given position follows similar logic to back insertion, adjusting the pointers around the target node:

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    
    newnode->next = pos->next;
    newnode->prev = pos;
    
    pos->next->prev = newnode;
    pos->next = newnode;
}

Deletion of a node removes it from the chain and frees memory. The surrounding nodes are reconnected before freeing the node:

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

Memory cleanup must be done carefully. Since the sentinel node is managed internally, it can be freed within the destructor function. However, the external pointer to the list must also be set to NULL after destruction:

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

After calling LTDestory, the caller should assign plist = NULL to prevent dangling pointers.