Sorted Doubly Linked List

sorted_doubly_linked_list.cpp

struct Node {
    int value;
    Node *prev;
    Node *next;
};

struct DList {
    Node *head;
};

void insert(DList *list, int value) {

    Node *n = new Node;
    n->value = value;

    // Case 1: list is empty
    if (!list->head) {
        n->next = NULL;
        n->prev = NULL;
        list->head = n;
        return;
    }

    // Case 2: list is non-empty
    Node *prev = list->head;
    // we know list->head != NULL
    Node *cur = list->head->next;

    while (cur) {
        if (cur->value > value)
            break;

        prev = cur;
        cur = cur->next;
    }

    if (cur) {
        // Sub-case 1: insert before head
        if (cur == list->head) {
            n->next = list->head;
            list->head = n;
            return;
        }

        // Sub-case 2: insert after head
        n->next = cur;
        n->prev = cur->prev;
        cur->prev = n;
        n->prev->next = n;
    } else {
         // Case 3: List insertion is at end of list
         // so cur is empty
         n->next = NULL;
         n->prev = prev;
         prev->next = n;
    }
}

void delete(DList *list, int value) {

    Node *cur = list->head;

    while (cur) {
        if (cur->value == value)
            break;
        cur = cur->next;
    }

    // Case 1: delete head
    if (cur == list->head) {
        list->head = cur->next;
        list->head->prev = NULL;
        delete cur;
        return;
    }

    // Case 2: delete after head if element exists
    if (cur) {
        if (cur->prev)
            cur->prev->next = cur->next;
        if (cur->next)
            cur->next->prev = cur->prev;
        delete cur;
    }
}

Special case: Insertion at end of list. This is why we need both prev and cur pointers in insert.