3.7

Idea – keep a “pointer to the pointer that leads to each node”.
For every node x we store, in addition to key and next, a field pprev that points to the variable that currently holds the reference to x (either the list’s head or some other node’s next).

With this extra field
• changing the predecessor’s pointer becomes
*x->pprev = x->next
• and, if x is not the last node, we also repair
x->next->pprev = x->pprev
Both are O(1), so deletion is O(1) even when we start with a direct pointer to x only.

C-style pseudocode
struct Node { // one extra word
  Item key;
  Node *next;
  Node **pprev; // “pointer to the pointer that points to me”
};

Node *head = NIL;

// INSERT AT HEAD
void push_front(Item k){
  Node *x = new Node;
  x->key = k;
  x->next = head;
  x->pprev = &head
  if(head) head->pprev = &x->next;
  head = x;
}

// DELETE GIVEN ONLY A POINTER x
void erase(Node *x){
  if(x->next) x->next->pprev = x->pprev;
  *x->pprev = x->next;
  free(x);
}

// SEARCH (unchanged)
Node* find(Item k){ for(Node *p=head; p; p=p->next) if(p->key==k) return p; return NIL; }


Complexities
• push_front, erase: O(1) time, O(1) extra space per node (the pprev word).
• search: O(n) time (inherent for unordered lists).

Thus we fulfil the footnote’s promise: every list operation is as fast as in a doubly-linked list, yet we keep only one real next link; the second “link” is a light-weight pointer-to-pointer used solely for updates.

Back to Chapter 3