Doubly Linked List

Doubly Linked Lists

A doubly linked list extends the singly linked list by adding a prev pointer to each node. Every node knows both its successor and its predecessor.

struct DNode {
    int val;
    struct DNode *prev;
    struct DNode *next;
};

NULL <-> [1] <-> [2] <-> [3] <-> NULL

Insert at Head

Create a new node, point its next to the old head, and update the old head's prev:

struct DNode *insert_head(struct DNode *head, int val) {
    struct DNode *n = new_dnode(val);
    n->next = head;
    if (head != NULL) head->prev = n;
    return n;
}

Insert at Tail

Walk to the last node and attach:

struct DNode *insert_tail(struct DNode *head, int val) {
    struct DNode *n = new_dnode(val);
    if (head == NULL) return n;
    struct DNode *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
    n->prev = cur;
    return head;
}

Delete a Node by Value

Find the node, then rewire its neighbors to skip over it:

struct DNode *delete_node(struct DNode *head, int val) {
    struct DNode *cur = head;
    while (cur != NULL) {
        if (cur->val == val) {
            if (cur->prev) cur->prev->next = cur->next;
            else head = cur->next;          // deleting head
            if (cur->next) cur->next->prev = cur->prev;
            free(cur);
            return head;
        }
        cur = cur->next;
    }
    return head;
}

Backward Traversal

Because each node has a prev pointer, you can walk the list in reverse from the tail:

void print_reverse(struct DNode *head) {
    if (head == NULL) return;
    struct DNode *cur = head;
    while (cur->next != NULL) cur = cur->next;
    while (cur != NULL) {
        printf("%d\n", cur->val);
        cur = cur->prev;
    }
}

Your Task

Implement all four functions: insert_head, insert_tail, delete_node, and print_reverse.