Circular Doubly Linked List using Sentinel

Circular Doubly Linked List

Without a sentinel node

Using a sentinel node

A circular view

An Empty List

Without a sentinel : head is NULL

With a sentinel: head is always the sentinel

Remove a node

With sentinel

Only two opeations

node->prev->next = node->next;
node->next->prev = node->prev;

Node removal

Without sentinel

Need to check the node to be removed against the head node

Removing non-head node

Removing head node

Node insertion

With sentinel

Four steps

    // example for insert a new node before a node "loc"
    // deal with the previous node of loc
    node->prev = loc->prev;
    loc->prev->next = node;
    
    // deal with loc related pointers
    loc->prev = node;
    node->next = loc;

Without a sentinel

You need to check if you are inserting the node to an empty list or if you are inserting before the head node

Insertion into an empty list

Insertion before the head node when not using a sentinel node

Advantage of using sentinels

Treat all insertions and removals in a unified manner at a slight memory overhead

Insertion

All insertions are in between existing nodes

Removal

All nodes to be deleted have neighbors on both sides

Using the sentinel nodes make writing your insert and remove code easier.

Example Code

Node Removal

Circular doubly linked list with a sentinel

// remove a node from a circular doubly linked list with sentinel
// not handling memory release

// with this operation, you cannot remove a sentinel node from an empty list
// as it always points to itself
void remove(Node* node) {
  if(NULL == node) { return; }
  
  // only two lines are needed to remove a node 
  // for circular doubly linked list with sentinel
  // my prev node points to my next node
  node->prev->next = node->next;
  // my next node points to my prev node
  node->next->prev = node->prev;
}

Circular doubly linked list with out a sentinel

// remove a node from a circular doubly linked list (without sentinel)
// not handling memory release

void remove(Node** head, Node* node) {
   // Invalid head, Empty list or invalid node
    if (NULL == head || NULL == *head || NULL == node) return;
    
    // Only one node in the list, will be empty after the node removed
    // simply set head to NULL
    if (*head == node && node->next == node) {
        *head = NULL;
        return;
    }
    
    // the esential two lines
    // Adjust the previous and next pointers
    // my prev node points to my next node
    node->prev->next = node->next;
    // my next node points to my prev node
    node->next->prev = node->prev;
    
    // if head is removed, move head to the next node
    if (*head == node) {
        *head = node->next;
    }

}

Insertion of a node after another node

Circular doubly linked list with a sentinel

// insert a node beore a location
// in a circular doubly linked list with a sentinel
void insert_before(Node* node, Node * loc) 
{
    if (NULL == node || NULL == loc) return;
    
    // only four lines are needed to insert a node into
    // a circular doubly-linked list with a sentinel
    // deal with the previous node of loc
    node->prev = loc->prev;
    loc->prev->next = node;
    
    // deal with loc itself
    loc->prev = node;
    node->next = loc;
}

Circular doubly linked list without a sentinel

void insert_before(Node** head, Node * node, Node* loc) {
    // Invalid head address or location
    // or an empty list
    if ((NULL == head) || (NULL == * head) || (loc == NULL)) return; 

    // Insert the new node after loc
    // deal with the previous node of loc
    node->prev = loc->prev;
    loc->prev->next = node;
    
    // deal with loc itself
    loc->prev = node;
    node->next = loc;

    // If the list was initially empty, set head to the new node
    if (* head == loc) {
        * head = node;
    }
}