Question

Can someone explain me AddAtHead,AddAtTail And AddInOrder functions
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

template <class T>
class DNode{
public:
    T data;
    DNode *next,*prev;
    DNode(){ next=prev=NULL;}
    DNode(T d, DNode *n=NULL, DNode *p=NULL){ data=d; next=n; prev=p;}
};
template <class T>
ostream& operator<<(ostream &out, const DNode<T> &n){
    out<<n.data<<' ';
    return out;
}
template <class T>
class HCDLL{
    DNode<T> *head;
public:
    HCDLL(){   head=new DNode<T>; head->next=head->prev=head;}
    void addAtHead(T d){
        head->next=head->next->prev=new DNode<T>(d, head->next, head);
    }
    void addAtTail(T d){
        head->prev=head->prev->next=new DNode<T>(d, head, head->prev);
    }
    void addInOrder(T d){
        DNode<T> *t;
        for (t=head->next;t!=head && t->data<d;t=t->next);
                t->prev=t->prev->next=new DNode<T>(d, t, t->prev);
    }
    void show(){
        for (DNode<T> *t=head->next;t!=head;t=t->next)
                cout<<*t<<' ';
        cout<<'\n';       
        }
};
int main() {
    //srand((unsigned int)time(0));
    HCDLL <int> list;
    list.addAtHead(5);
    list.addAtHead(3);
    list.addAtHead(1);
        list.show();
    list.addAtTail(7);
    list.addAtTail(9);
        list.show();
        list.addInOrder(8);
        list.addInOrder(10);    
        list.show();
    return 0;
}

Answer 1

Doubly Circular Linked List (CDLL)

Two consecutive elements are linked by previous and next pointer and the last node points to first node by next pointer and also the previous pointer of the head node points to the tail node.

Start Next Next Data Data Prev PrevData

Lets see some basic operation on this data structure

Insertion at the beginning of the list: To insert a node at the beginning of the list, create a node(Say T) with data = 5, T next pointer points to first node of the list, T previous pointer points to last node the list, last node’s next pointer points to this T node, first node’s previous pointer also points this T node

New node(T) Start 6 5 Start Start

Insertion in between the nodes of the list: To insert a node in between the list, two data values are required one after which new node will be inserted and another is the data of the new node.

Start 5 6 8 9 7

Method	Operation
addAtHead	Insertion at the beginning of the list
addAtTail	Insertion at the end of the list
addInOrder	Insertion in between the nodes of the list First find correct position and insert

I have added and simplified the program with comments for better understanding

#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

template <class T>
class DNode{
public:
    T data;
    DNode *next,*prev;
    DNode()
   {
       next=prev=NULL;
   }
    DNode(T d, DNode *n=NULL, DNode *p=NULL)
   {
       data=d;
       next=n;
       prev=p;
   }
};

template <class T>
ostream& operator<<(ostream &out, const DNode<T> &n){
    out<<n.data<<' ';
    return out;
}

template <class T>
class HCDLL{
    DNode<T> *head;
public:
    HCDLL()
   {
       head=new DNode<T>;
       //head->next = head->prev = head;
       //simplifying the above one line statment in multiline
       head->prev = head;
       head->next = head->prev;
   }
  
    void addAtHead(T d){
        //head->next=head->next->prev=new DNode<T>(d, head->next, head);
        //simplifying the above one line statment in multiline
      
        /*
           Special attentation to this function
           new DNode<T>(d, head->next, head);
           it says new node with data d and its next pointer head->next and prevois pointer head
           i.e. 1st agrument it data 2nd is its next and 3rd is it prevois pointer
          
           and newly added node in head now
       */
      
      
       /*       new DNode<T>(d, head->next, head);
      
              
       */
       DNode<T> *temp = new DNode<T>(d, head->next, head);
          
        head->next->prev = temp;
        head->next = head->next->prev;
    }
    void addAtTail(T d)
   {
        //head->prev = head->prev->next = new DNode<T>(d, head, head->prev);
        //simplifying the above one line statment in multiline
      
        head->prev->next = new DNode<T>(d, head, head->prev);
        head->prev = head->prev->next;
    }
    void addInOrder(T d)
   {
        DNode<T> *t;
        for (t=head->next;t!=head && t->data<d;t=t->next);
        //loop is doing nothing see semicolon at end
        //this find the correct posiotn to insert
      
       //t->prev=t->prev->next=new DNode<T>(d, t, t->prev);
       //simplifying the above one line statment in multiline
       t->prev->next=new DNode<T>(d, t, t->prev);
       t->prev=t->prev->next;
    }
  
    void show(){
        for (DNode<T> *t=head->next;t!=head;t=t->next)
                cout<<*t<<' ';
        //end of loop
       cout<<'\n';     
    }
};
int main() {
    //srand((unsigned int)time(0));
    HCDLL <int> list;
    list.addAtHead(5);
    list.addAtHead(3);
    list.addAtHead(1);
    list.show();
    list.addAtTail(7);
    list.addAtTail(9);
    list.show();
    list.addInOrder(8);
    list.addInOrder(10);  
    list.show();
    return 0;
}

comment if doubt