Create a generic class called LinkedList. LinkedList will use nodes that store a

Question

Create a generic class called LinkedList. LinkedList will use nodes that store a value of the generic type to store its contents. The linked list should be doubly-linked and circular. It should not use sentinel nodes (header and tail nodes).

Methods: addHead, addTail, removeHead, removeTail, setHead

I am not sure how to do this because without the sentinel nodes how can we find out which is the head and tail node?

Explanation / Answer

Dear Friend hope this will help u here is the code for the doubly linked list and the circular linked list Doubly ---- #include using namespace std; struct nodeType { char info; nodeType *next; nodeType *back; }; class doublylinkedList { public: doublylinkedList() { head=new nodeType; head=0; } ~doublylinkedList() { destroyList(); } void insertFirst(char val) { nodeType *p; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { p->next=head->next; head=p; } } void insertLast(char val) { nodeType *p; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { nodeType *c; c=head; while(c->next!=0) c=c->next; c->next=p; p->back=c; } } void insertAfter(int loc,char val) { nodeType *p; p=new nodeType; p->info=val; p->back=0; p->next=0; if(head==0) head=p; else { nodeType *c; c=head; int count=0; while(countnext; count++; } p->next=c->next; p->back=c; c->next=p; } } void insertBefore(int loc,char val) { nodeType *p; int count=0; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { nodeType *c; c=head; while(countnext; count++; } p->next=c->next; p->back=c; c->next=p; c->next->next->back=c->next; } } void initializeList() { destroyList(); } void destroyList() { nodeType *q; while(head!=0) { q=head; head=head->next; delete q; } } bool isEmpty() { return (head->next == NULL); } void print() { nodeType *curent=head; while(curent != NULL) { coutinfo); return -1; } char back() { nodeType *curent=head; while(curent->next != NULL) curent = curent -> next; return (curent->info); } protected: nodeType *head; public: void copyList(const doublylinkedList &cf) { destroyList(); nodeType *c; if(cf.head!=0) c=cf.head; while(c!=0) { insertLast(c->info); c=c->next; } } void removeAfter(int loc) { nodeType *p; int counter=0; int len=length(); p=head; if(head!=0 && loc =0) { while(counter!=loc+1 && counternext; counter++; } if(loc+1==len-1) { p->back->next=0; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeBefore(int loc) { int counter=0; int len=length(); nodeType *p; p=head; if(head!=0 && loc>0 && locnext; counter++; } if(loc-1==0) { p->next->back=0; head=p->next; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeAt(int loc) { int count=0; nodeType *p; if(head!=0 && loc>=0) { if(loc>0) removeAfter(loc-1); else { p=head; head=head->next; head->next->back=0; delete p; } } } }; int main() { doublylinkedList obj1; obj1.insertFirst('x'); obj1.print(); coutback=0; if(head==0) head=p; else { nodeType *c; c=head; while(countnext; count++; } p->next=c->next; p->back=c; c->next=p; c->next->next->back=c->next; } } void initializeList() { destroyList(); } void destroyList() { nodeType *q; while(head!=0) { q=head; head=head->next; delete q; } } bool isEmpty() { return (head->next == NULL); } void print() { nodeType *curent=head; while(curent != NULL) { coutinfo); return -1; } char back() { nodeType *curent=head; while(curent->next != NULL) curent = curent -> next; return (curent->info); } protected: nodeType *head; public: void copyList(const doublylinkedList &cf) { destroyList(); nodeType *c; if(cf.head!=0) c=cf.head; while(c!=0) { insertLast(c->info); c=c->next; } } void removeAfter(int loc) { nodeType *p; int counter=0; int len=length(); p=head; if(head!=0 && loc =0) { while(counter!=loc+1 && counternext; counter++; } if(loc+1==len-1) { p->back->next=0; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeBefore(int loc) { int counter=0; int len=length(); nodeType *p; p=head; if(head!=0 && loc>0 && locnext; counter++; } if(loc-1==0) { p->next->back=0; head=p->next; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeAt(int loc) { int count=0; nodeType *p; if(head!=0 && loc>=0) { if(loc>0) removeAfter(loc-1); else { p=head; head=head->next; head->next->back=0; delete p; } } } }; int main() { doublylinkedList obj1; obj1.insertFirst('x'); obj1.print(); coutlink=c->link; c->link=p; } } } void insertBefore(int loc,char val) { nodeType *p; p=new nodeType; int count=0; p->info=val; p->link=0; if(head==0) { head=p; head->link=head; } else if(loc==0) insertFirst(val); else { nodeType *c=head; while(countlink; count++; } p->link=c->link; c->link=p; } } void initializeList() { destroyList(); } void destroyList() { nodeType *q; int count=0; int len=length(); if(head!=0) { while(count!=len) { q=head; head=head->link; delete q; count++; } } } bool isEmpty() { return (head == 0); } void print() { nodeType *curent=head; while(curent->link != head) { cout link; return (curent->info); } protected: nodeType *head; public: void copyList(const linkedListType &cf) { nodeType *p; nodeType *c; c=cf.head; if(cf.head==0) head=0; else { head=new nodeType; p=head; p->info=c->info; p->link=p; c=c->link; head=p; while(c!=cf.head) { p->link=new nodeType; p=p->link; p->info=c->info; p->link=0; c=c->link; } p->link=head; } } }; int main() { linkedListType obj1; cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.