Types of Link list

 

Circular Doubly Link List:

Objectives:

 

Ø  To gain familiarity with circular-linked lists.

Ø  To gain experience with the implementation of circular-linked lists.

Ø  To perform different operations on circular-linked lists.

Ø  To gain familiarity with doubly-linked lists.

Ø  To perform different operations on doubly-linked lists.

                                             

Linked list:

A list of items, called nodes, in which the order of the nodes is determined by the address, called the link, stored in each node.

Following are the important terms to understand the concept of Linked List.

·         Link − Each link of a linked list can store a data called an element.

·         Next − Each link of a linked list contains a link to the next link called Next.

Types of Linked List:

Following are the various types of linked list.

·        Simple Linked List − Item navigation is forward only.

·        Doubly Linked List − Items can be navigated forward and backward.

·       Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

 

Operations of Circular Doubly Link List:

In data structure Link List is a linear collection of data elements. Each element or node of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. In a linked list the entry point is called the head of the list.

In Circular Doubly Linked List two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and the first node also points to last node by previous pointer.

  Code:

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

struct nod {

   int info;

   struct nod *n;

   struct nod *p;

}*start, *last;

int count = 0;

class circulardoublylist {

   public:

      nod *create_node(int);

      void insert_begin();

      void insert_end();

      void insert_pos();

      void delete_pos();

      void search();

      void update();

      void display();

      void reverse();

      circulardoublylist() {

         start = NULL;

         last = NULL;

      }

};

int main() {

   int c;

   circulardoublylist cdl;

   while (1) //perform switch operation

{

      cout<<"1.Insert at Beginning"<<endl;

      cout<<"2.Insert at End"<<endl;

      cout<<"3.Insert at Position"<<endl;

      cout<<"4.Delete at Position"<<endl;

      cout<<"5.Update Node"<<endl;

      cout<<"6.Search Element"<<endl;

      cout<<"7.Display List"<<endl;

      cout<<"8.Reverse List"<<endl;

      cout<<"9.Exit"<<endl;

      cout<<"Enter your choice : ";

      cin>>c;

      switch(c) {

         case 1:

            cdl.insert_begin();

         break;

         case 2:

            cdl.insert_end();

         break;

         case 3:

            cdl.insert_pos();

         break;

         case 4:

            cdl.delete_pos();

         break;

         case 5:

            cdl.update();

         break;

         case 6:

            cdl.search();

         break;

         case 7:

            cdl.display();

         break;

         case 8:

            cdl.reverse();

         break;

         case 9:

            exit(1);

         default:

            cout<<"Wrong choice"<<endl;

      }

   }

   return 0;

}

nod* circulardoublylist::create_node(int v) {

   count++;

   struct nod *t;

   t = new(struct nod);

   t->info = v;

   t->n = NULL;

   t->p = NULL;

   return t;

}

void circulardoublylist::insert_begin() {

   int v;

   cout<<endl<<"Enter the element to be inserted: ";

   cin>>v;

   struct nod *t;

   t = create_node(v);

   if (start == last && start == NULL) {

      cout<<"Element inserted in empty list"<<endl;

      start = last = t;

      start->n = last->n = NULL;

      start->p = last->p = NULL;

   } else {

      t->n = start;

      start->p = t;

      start = t;

      start->p = last;

      last->n = start;

      cout<<"Element inserted"<<endl;

   }

}

void circulardoublylist::insert_end() {

   int v;

   cout<<endl<<"Enter the element to be inserted: ";

   cin>>v;

   struct nod *t;

   t = create_node(v);

   if (start == last && start == NULL) {

      cout<<"Element inserted in empty list"<<endl;

      start = last = t;

      start->n= last->n = NULL;

      start->p = last->p= NULL;

   } else {

      last->n= t;

      t->p= last;

      last = t;

      start->p = last;

      last->n= start;

   }

}

void circulardoublylist::insert_pos() {

   int v, pos, i;

   cout<<endl<<"Enter the element to be inserted: ";

   cin>>v;

   cout<<endl<<"Enter the position of element inserted: ";

   cin>>pos;

   struct nod *t, *s, *ptr;

   t = create_node(v);

   if (start == last && start == NULL) {

      if (pos == 1) {

         start = last = t;

         start->n = last->n = NULL;

         start->p = last->p = NULL;

      } else {

         cout<<"Position out of range"<<endl;

         count--;

         return;

      }

   } else {

      if (count < pos) {

         cout<<"Position out of range"<<endl;

         count--;

         return;

      }

      s = start;

      for (i = 1;i <= count;i++) {

         ptr = s;

         s = s->n;

         if (i == pos - 1) {

            ptr->n = t;

            t->p= ptr;

            t->n= s;

            s->p = t;

            cout<<"Element inserted"<<endl;

            break;

         }

      }

   }

}

void circulardoublylist::delete_pos() {

   int pos, i;

   nod *ptr, *s;

   if (start == last && start == NULL) {

      cout<<"List is empty, nothing to delete"<<endl;

      return;

   }

   cout<<endl<<"Enter the position of element to be deleted: ";

   cin>>pos;

   if (count < pos) {

      cout<<"Position out of range"<<endl;

      return;

   }

   s = start;

   if(pos == 1) {

      count--;

      last->n = s->n;

      s->n->p = last;

      start = s->n;

      free(s);

      cout<<"Element Deleted"<<endl;

      return;

   }

   for (i = 0;i < pos - 1;i++ ) {

      s = s->n;

      ptr = s->p;

   }

   ptr->n = s->n;

   s->n->p = ptr;

   if (pos == count) {

      last = ptr;

   }

   count--;

   free(s);

   cout<<"Element Deleted"<<endl;

}

void circulardoublylist::update() {

   int v, i, pos;

   if (start == last && start == NULL) {

      cout<<"The List is empty, nothing to update"<<endl;

      return;

   }

   cout<<endl<<"Enter the position of node to be updated: ";

   cin>>pos;

   cout<<"Enter the new value: ";

   cin>>v;

   struct nod *s;

   if (count < pos) {

      cout<<"Position out of range"<<endl;

      return;

   }

   s = start;

   if (pos == 1) {

      s->info = v;

      cout<<"Node Updated"<<endl;

      return;

   }

   for (i=0;i < pos - 1;i++) {

      s = s->n;

   }

   s->info = v;

   cout<<"Node Updated"<<endl;

}

void circulardoublylist::search() {

   int pos = 0, v, i;

   bool flag = false;

   struct nod *s;

   if (start == last && start == NULL) {

      cout<<"The List is empty, nothing to search"<<endl;

      return;

   }

   cout<<endl<<"Enter the value to be searched: ";

   cin>>v;

   s = start;

   for (i = 0;i < count;i++) {

      pos++;

      if (s->info == v) {

         cout<<"Element "<<v<<" found at position: "<<pos<<endl;

         flag = true;

      }

      s = s->n;

   }

   if (!flag)

      cout<<"Element not found in the list"<<endl;

}

void circulardoublylist::display() {

   int i;

   struct nod *s;

   if (start == last && start == NULL) {

      cout<<"The List is empty, nothing to display"<<endl;

      return;

   }

   s = start;

   for (i = 0;i < count-1;i++) {

      cout<<s->info<<"<->";

      s = s->n;

   }

   cout<<s->info<<endl;

}

void circulardoublylist::reverse() {

   if (start == last && start == NULL) {

      cout<<"The List is empty, nothing to reverse"<<endl;

      return;

   }

   struct nod *p1, *p2;

   p1 = start;

   p2 = p1->n;

   p1->n = NULL;

   p1->p= p2;

   while (p2 != start) {

      p2->p = p2->n;

      p2->n = p1;

      p1 = p2;

      p2 = p2->p;

   }

   last = start;

   start = p1;

   cout<<"List Reversed"<<endl;

}