Advertisement
shabbyheart

Doubly link list

Apr 28th, 2019
457
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.00 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. class Node{
  4. public:
  5.     int data;
  6.     Node *next;
  7.     Node *prev;
  8. };
  9.  
  10. class LinkList{
  11. public:
  12.     Node *head;
  13.     LinkList(){
  14.         head = NULL;
  15.     }
  16.     void insert_at_first( int value)
  17.     {
  18.         Node *newNode = new Node();
  19.         newNode->data = value;
  20.         newNode->next = head;
  21.         newNode->prev = NULL;
  22.  
  23.         if( head != NULL)
  24.         {
  25.             head->prev = newNode;
  26.         }
  27.         head = newNode;
  28.         //cout<<head->data;
  29.     }
  30.     ///insert after a specific node;
  31.     void insert_at_middle(int value)
  32.     {
  33.         Node *temp = head->next;
  34.         if( temp == NULL)
  35.         {
  36.             cout<<"The given previous node can not be NUlL";
  37.             return ;
  38.         }
  39.  
  40.         Node *newNode = new Node();
  41.         newNode->data = value;
  42.         newNode->next = temp->next;
  43.         temp->next = newNode;
  44.  
  45.         newNode->prev = temp;
  46.  
  47.         if(newNode->next != NULL)
  48.             newNode->next->prev = newNode;
  49.     }
  50.     void insert_after_value(int value,int key)
  51.     {
  52.         Node *temp = head;
  53.         if(temp == NULL)
  54.         {
  55.             cout<<"Link list is empty";
  56.             return ;
  57.         }
  58.         do{
  59.             if(temp->data == key)
  60.             {
  61.                 Node *newNode = new Node();
  62.                 newNode->data = value;
  63.                 newNode->next = temp->next;
  64.                 temp->next = newNode;
  65.                 newNode->prev = temp;
  66.                 if(newNode->next != NULL)
  67.                 {
  68.                     newNode->next->prev = newNode;
  69.  
  70.                 }
  71.                 return ;
  72.             }
  73.             temp = temp ->next;
  74.         }while(temp != NULL);
  75.         cout<<"Value is not found";
  76.     }
  77.  
  78.     void insert_at_end( int value)
  79.     {
  80.  
  81.         Node *temp = head;
  82.  
  83.         Node *newNode = new Node();
  84.         newNode->data = value;
  85.         newNode->next = NULL;
  86.  
  87.         if(head == NULL)
  88.         {
  89.             newNode->prev = NULL;
  90.             head  = newNode;
  91.             return ;
  92.         }
  93.         while( temp->next != NULL)
  94.         {
  95.             temp = temp->next;
  96.         }
  97.         temp->next = newNode;
  98.         newNode->prev = temp;
  99.     }
  100.  
  101.  
  102.     void bubble_sort()
  103.     {
  104.         int swapped;
  105.         Node *right_ptr = NULL;
  106.  
  107.         if( head == NULL)
  108.             return ;
  109.         do{
  110.             swapped = 0;
  111.             Node *temp = head;
  112.             while ( temp->next != right_ptr)
  113.             {
  114.                 if(temp->data > temp->next->data )
  115.                 {
  116.                     swap(temp->data, temp->next->data);
  117.                     swapped = 1;
  118.                 }
  119.                 temp = temp->next;
  120.             }
  121.             right_ptr = temp;
  122.             //cout<<lptr<<endl;
  123.         }while(swapped);
  124.     }
  125.  
  126.     void delete_node(int key)
  127.     {
  128.         Node *temp = head,*previous;
  129.         //cout<<temp->data;
  130.         if( temp->data == key)
  131.         {
  132.             head = temp->next;
  133.             head->prev = NULL;
  134.             delete(temp);
  135.             return;
  136.         }
  137.         while(temp != NULL && temp->data != key)
  138.         {
  139.             previous = temp;
  140.             temp = temp->next;
  141.         }
  142.         if(temp == NULL)
  143.         {
  144.             cout<<"Value is not found";
  145.             return;
  146.         }
  147.         cout<<previous->data;
  148.         previous->next = temp->next;
  149.         if(temp->next != NULL)
  150.             previous->next->prev = previous;
  151.     }
  152.  
  153.     void display()
  154.     {
  155.         Node *temp,*last;
  156.         temp = head;
  157.         cout<<"Traversal in forward direction "<<endl;
  158.         while( temp != NULL)
  159.         {
  160.             cout<<temp->data<<" ";
  161.             last = temp;
  162.             temp = temp-> next;
  163.         }
  164.  
  165.         cout<<endl<<" Traversal in reverse direction "<<endl;
  166.         while(last != NULL)
  167.         {
  168.             cout<<last->data<<" ";
  169.             last= last->prev;
  170.         }
  171.     }
  172.     void reverse_List()
  173.     {
  174.         Node *temp = NULL;
  175.         Node *curr = head;
  176.         cout<<endl<<endl;
  177.         while( curr != NULL)
  178.         {
  179.             ///swap between node previous and node next;
  180.             temp = curr->prev;
  181.             curr->prev = curr->next;
  182.             curr->next = temp;
  183.             curr = curr->prev;
  184.         }
  185.  
  186.         if( temp != NULL)
  187.             head = temp->prev;
  188.     }
  189.  
  190. };
  191. int main()
  192. {
  193.     LinkList ll;
  194.     ll.insert_at_first(10);
  195.     ll.insert_at_first(20);
  196.     ll.insert_at_first(30);
  197.     ll.insert_at_middle(500);
  198.     ll.insert_at_end(600);
  199.     ll.display();
  200.     cout<<endl<<"which value after you want to insert"<<endl;
  201.     int value;
  202.     cin>>value;
  203.     ll.insert_after_value(40,value);
  204.     ll.display();
  205.  
  206.     cout<<endl<<"after reverse"<<endl;
  207.     ll.reverse_List();
  208.     ll.display();
  209.  
  210.     cout<<endl<<"After short"<<endl;
  211.  
  212.     ll.bubble_sort();
  213.     ll.display();
  214.  
  215.     cout<<endl<<"After Delete"<<endl;
  216.     cout<<"which value you want to delete"<<endl;
  217.     cin>>value;
  218.     ll.delete_node(value);
  219.     ll.display();
  220. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement