Dummy Head Node Linked List

Question

I'm trying to write an insert function for string values for a circular doubly linked list. I saw that creating a dummy node is beneficial in doing this so I can eliminate special cases like when the list is empty. The problem is I'm not finding alot of good information on dummy head nodes. I understand their purpose, but I don't understand how I create/implement it.

appreciate all the code examples guys, tried to figure it out on my own getting a little stuck though if someone can look at it.

 #include <iostream>
 #include <string>
 using namespace std;
 typedef string ListItemType;

struct node {
node * next;
node * prev;
ListItemType value;

};
node * head;
node * dummyHead = new node;
void insert(const ListItemType input, node *  & within);

void main(){
     insert("bob",dummyHead);
}

void insert( const ListItemType input, node *  &ListHead){
   node *newPtr = new node;
   node *curr;
   newPtr->value = input;

curr = ListHead->next; //point to first node;
while (curr != ListHead && input < curr->value){
    curr = curr->next;
}
        //insert the new node pointed to by the newPTr before
        // the node pointed to by curr
    newPtr->next = curr;
    newPtr->prev = curr->prev;
    curr->prev = newPtr;
    newPtr->prev->next = newPtr;
}

Answer 1

For a circular doubly linked list, you can setup 1 sentinel node where both "next" and "prev" points to itself when list is empty. When list is not empty, sentinel->next points to first element and sentinel->prev points to last element. With this knowledge, your insert and remove function would look something like this.

This is very basic and your LinkedList and Node class maybe implemented differently. That is OK. The main thing is the insert() and remove() function implementation that shows how sentinel node(s) removes the need for checking for NULL values.

Hope this helps.

class DoublyLinkedList
{
    Node *sentinel;
    int size = 0;

    public DoublyLinkedList() {
        sentinel = new Node(null);
    }

    // Insert to the end of the list
    public void insert(Node *node) {
        // being the last node, point next to sentinel
        node->next = sentinel;

        // previous would be whatever sentinel->prev is pointing previously
        node->prev = sentinel->prev;

        // setup previous node->next to point to newly inserted node
        node->prev->next = node;

        // sentinel previous points to new current last node
        sentinel->prev = node;

        size++;
    }

    public Node* remove(int index) {
        if(index<0 || index>=size) throw new NoSuchElementException();

        Node *retval = sentinel->next;
        while(index!=0) {
            retval=retval->next;
            index--;
        }

        retval->prev->next = retval->next;
        retval->next->prev = retval->prev;
        size--;
        return retval;
    }
}

class Node 
{
    friend class DoublyLinkedList;
    string *value;
    Node *next;
    Node *prev;

    public Node(string *value) {
        this->value = value;
        next = this;
        prev = this;
    }

    public string* value() { return value; }
}