Understanding Doubly Linked Lists Doubly linked lists are a fundamental data structure where each node contains a pointer to both the next and previous nodes in the sequence. This bidirectional nature allows for efficient traversal in both directions, unlike singly linked lists which can only be traversed forward.

In this implementation, we'll create a doubly linked list with a sentinel node (also called a dummy head node). The sentinel node doesn't store actual data but serves as a placeholder that simplifies edge case handling, particularly for insertions and deletions at the beginning and end of the list.

Node Structure Definition First, let's define the structure for our doubly linked list nodes:

typedef int DataType;
typedef struct Node {
    DataType data;
    struct Node* next;
    struct Node* prev;
} DListNode;

Function Declarations Our implementation will include the following operations:

DListNode* createList();
bool isEmpty(DListNode* head);
DListNode* createNode(DataType value);
DListNode* findNode(DListNode* head, DataType value);
void printList(DListNode* head);
void insertAfter(DListNode* position, DataType value);
void insertBefore(DListNode* position, DataType value);
void pushFront(DListNode* head, DataType value);
void pushBack(DListNode* head, DataType value);
void deleteNode(DListNode* node);
void popFront(DListNode* head);
void popBack(DListNode* head);
void destroyList(DListNode* head);

Creating the Sentinel Node The sentinel node acts as both the head and tail of our circular list, pointing to itself initially:

DListNode* createList() {
    DListNode* sentinel = (DListNode*)malloc(sizeof(DListNode));
    if (sentinel == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    
    sentinel->next = sentinel;
    sentinel->prev = sentinel;
    return sentinel;
}

Node Creation Creating a new node involves allocating memory and initializing its pointers:

DListNode* createNode(DataType value) {
    DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        return NULL;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

Checking if List is Empty We can determine if the list is empty by checking if the sentinel node points to itself:

bool isEmpty(DListNode* head) {
    assert(head != NULL);
    return head->next == head;
}

Insertion Operations Insertion in a doubly linked list requires updating four pointers. We'll implement a generic insertion function that can be reused for both head and tail insertions:

void insertAfter(DListNode* position, DataType value) {
    assert(position != NULL);
    
    DListNode* newNode = createNode(value);
    DListNode* nextNode = position->next;
    
    position->next = newNode;
    newNode->prev = position;
    newNode->next = nextNode;
    nextNode->prev = newNode;
}

void insertBefore(DListNode* position, DataType value) {
    assert(position != NULL);
    insertAfter(position->prev, value);
}

Head and Tail Insetrions Using our generic insertion functions, we can implement head and tail insertions:

void pushFront(DListNode* head, DataType value) {
    assert(head != NULL);
    insertAfter(head, value);
}

void pushBack(DListNode* head, DataType value) {
    assert(head != NULL);
    insertBefore(head, value);
}

List Traversal and Printing To print the list, we traverse from the sentinel node's next pointer until we return to the sentinel:

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

Searching for a Node We can search for a node by value by traversing the list:

DListNode* findNode(DListNode* head, DataType value) {
    assert(head != NULL);
    
    DListNode* current = head->next;
    while (current != head) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Deletion Operations Deleting a node requires updating the pointers of its neighbors and freeing the node's memory:

void deleteNode(DListNode* node) {
    assert(node != NULL);
    
    DListNode* prevNode = node->prev;
    DListNode* nextNode = node->next;
    
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
    free(node);
}

void popFront(DListNode* head) {
    assert(head != NULL);
    assert(!isEmpty(head));
    
    deleteNode(head->next);
}

void popBack(DListNode* head) {
    assert(head != NULL);
    assert(!isEmpty(head));
    
    deleteNode(head->prev);
}

Destroying the List To free all memory used by the list, we traverse and delete each node:

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

Example Usage Here's how we might use our doubly linked list implementation:

void testDoublyLinkedList() {
    DListNode* list = createList();
    
    pushFront(list, 10);
    pushFront(list, 20);
    pushBack(list, 30);
    pushBack(list, 40);
    
    printf("List contents: ");
    printList(list);  // Output: 20 10 30 40
    
    DListNode* node = findNode(list, 10);
    if (node != NULL) {
        deleteNode(node);
    }
    
    printf("After deletion: ");
    printList(list);  // Output: 20 30 40
    
    popFront(list);
    popBack(list);
    
    printf("After popping: ");
    printList(list);  // Output: 30
    
    destroyList(list);
}

int main() {
    testDoublyLinkedList();
    return 0;
}

This implementation demonstrates the power of doubly linked lists with sentinel nodes, providing efficient insertions and deletions at both ends of the list while simplifying edge case handling.