Doubly linked list: bank customer records

Assume each node stores the customer data and the list is kept sorted by account number:

struct cust {
    struct cust *prev;
    char acc[10];          /* e.g. "00056PR" */
    char name[30];
    float balance;
    struct cust *next;
};

start points to the first node.

Deleting customer 00056PR

1. If start == NULL, print "list empty" and stop.
2. Set p = start; while p != NULL and strcmp(p->acc, "00056PR") != 0, set p = p->next.
3. If p == NULL, print "customer not found" and stop.
4. If p->prev != NULL, set p->prev->next = p->next; otherwise (first node) start = p->next.
5. If p->next != NULL, set p->next->prev = p->prev.
6. free(p).

Before: [A] <-> [00056PR] <-> [B]
After : [A] <-> [B]      A->next = B, B->prev = A

Inserting a new customer (kept in sorted order)

1. Allocate node new and fill its data.
2. If the list is empty or strcmp(new->acc, start->acc) < 0: new->prev = NULL; new->next = start; if start != NULL then start->prev = new; start = new; stop.
3. Else find p, the last node whose account number is smaller than the new one: p = start; while (p->next != NULL && strcmp(p->next->acc, new->acc) < 0) p = p->next;
4. new->next = p->next; new->prev = p;
5. If p->next != NULL then p->next->prev = new.
6. p->next = new.

Before: [p] <-> [q]
After : [p] <-> [new] <-> [q]

Difference from a singly linked list

So a doubly list makes deletion simpler (no trailing pointer) but needs two extra pointer updates and more memory.