fueanta

Doubly Linked List [implemented on singly]

Nov 25th, 2016
148
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4.  
  5. struct node {
  6.     int data;
  7.     node *next, *prev;
  8. } *head, *tail, *newNODE;
  9.  
  10. int length;
  11.  
  12. void listInitiate(); //
  13. void create_List(int); //
  14. void show_List();
  15. void show_List2(); //
  16. void search_List(int);
  17. void search_List2(int); //
  18. void insert_AT_first(int); //
  19. void insert_after_value(int,int); //
  20. void insert_before_value(int,int);
  21. void insert_between_values(int,int,int);
  22. void insert_AT_pos(int, int);
  23. void insert_AT_last(int); //
  24. void delete_AT_first(); //
  25. void delete_after_value(int); //
  26. void delete_before_value(int);
  27. void delete_between_values(int, int);
  28. void delete_AT_pos(int);
  29. void delete_AT_last(); //
  30.  
  31. int main() {
  32.     create_List(4);
  33.     show_List();
  34.     delete_after_value(3);
  35.     show_List();
  36.     show_List2();
  37. }
  38.  
  39. void listInitiate() {
  40.     head = NULL;
  41.     tail = NULL;
  42. }
  43.  
  44. void create_List(int n) {
  45.     listInitiate();
  46.     cout << "\nCreating a new list of size " << n << "." << endl; length = n;
  47.     for (int i = 0; i < n; i++) {
  48.         int item; cout << "\nElement " << i + 1 << ": "; cin >> item;
  49.         newNODE = new node;
  50.         newNODE->data = item;
  51.         newNODE->prev = tail;
  52.         newNODE->next = NULL;
  53.         if (head == NULL) {
  54.             head = newNODE;
  55.             tail = newNODE;
  56.         }
  57.         else {
  58.             tail->next = newNODE;
  59.             tail = newNODE;
  60.         }
  61.     }
  62. }
  63.  
  64. void show_List() { node *i; int l;
  65.     if (head != NULL) {
  66.         cout << "\nCurrently in the List, you have following elements: \n";
  67.         for (i = head, l = 1; i != NULL; i = i->next, l++) {
  68.             cout << "\nElement " << l << ": " << i->data << endl;
  69.         }
  70.         cout << "\nEnd of the list." << endl;
  71.     }
  72.     else cout << "\nYour list is empty." << endl;
  73. }
  74.  
  75. void show_List2() {
  76.     node *i; int l;
  77.     if (head != NULL) {
  78.         cout << "\nReversed list : " << endl;
  79.         for (i = tail, l = 1; i != NULL; i = i->prev, l++) {
  80.             cout << "\nElement " << l << ": " << i->data << endl;
  81.         }
  82.         cout << "\nEnd of the list." << endl;
  83.     }
  84.     else cout << "\nYour list is empty." << endl;
  85. }
  86.  
  87. void search_List(int item) { node *i; int l;
  88.     for (i = head, l = 1; i->data != item && i->next != NULL; l++)
  89.         i = i->next;
  90.     if (i->data == item)
  91.         cout << "\nElement found..! Position of first appearance in the list : " << l << endl;
  92.     else cout << "\nSorry! Element isn't in the list." << endl;
  93. }
  94.  
  95. void search_List2(int item) {
  96.     node *i; int l;
  97.     for (i = tail, l = 1; i->data != item && i->prev != NULL; l++)
  98.         i = i->prev;
  99.     if (i->data == item)
  100.         cout << "\nElement found..! Position of first appearance in the reversed list : " << l << endl;
  101.     else cout << "\nSorry! Element isn't in the list." << endl;
  102. }
  103.  
  104. void insert_AT_first(int item) {
  105.     newNODE = new node;
  106.     newNODE->data = item;
  107.     newNODE->next = head;
  108.     newNODE->prev = NULL;
  109.     head->prev = newNODE;
  110.     head = newNODE;
  111.     cout << "\nElement " << item << " has been added as the new head of the list." << endl;
  112. }
  113.  
  114. void insert_after_value(int value, int item) {
  115.     node *i; int l;
  116.     for (i = head, l = 1; i->data != value && i->next != NULL; l++)
  117.         i = i->next;
  118.     if (i->data == value) {
  119.         newNODE = new node;
  120.         newNODE->data = item;
  121.         newNODE->next = i->next;
  122.         newNODE->prev = i;
  123.         newNODE->next->prev = newNODE;
  124.         i->next = newNODE;
  125.         cout << "\nElement " << value << " has been found on the list at postion no: " << l
  126.             << " and " << item << " has been added after " << value << " at position no: "
  127.             << l + 1 << endl;
  128.     }
  129.     else {
  130.         cout << "\nOPERATION failed..!" << endl;
  131.         cout << "Searched for " << value << " among the " << l << " elements of the list but "
  132.             << value << " could not be found." << endl;
  133.     }
  134. }
  135.  
  136. void insert_before_value(int value, int item) {
  137.     node *i; int l;
  138.     if (head->data == value) {
  139.         insert_AT_first(item);
  140.         cout << "\nElement " << value <<
  141.             " has been found on the head so " << item << " has been added as the new head."
  142.             << endl;
  143.     }
  144.     else {
  145.         for (i = head, l = 1; i->next->data != value && i->next != NULL; l++)
  146.             i = i->next;
  147.         if (i->next->data == value) {
  148.             newNODE = new node;
  149.             newNODE->data = item;
  150.             newNODE->next = i->next;
  151.             i->next = newNODE;
  152.             cout << "\nElement " << value << " has been found on the list at postion no: " << l + 1
  153.                 << " and " << item << " has been added before " << value << " at position no: "
  154.                 << l + 1 << endl;
  155.         }
  156.         else {
  157.             cout << "\nOPERATION failed..!" << endl;
  158.             cout << "Searched for " << value << " among the " << l << " elements of the list but "
  159.                 << value << " could not be found." << endl;
  160.         }
  161.     }
  162. }
  163.  
  164. void insert_between_values(int val1, int val2, int item) {
  165.     node *i; int l;
  166.     for (i = head, l = 1; i->data != val1 && i->next != NULL; l++)
  167.         i = i->next;
  168.     if (i->data == val1 && i->next->data == val2) {
  169.         newNODE = new node;
  170.         newNODE->data = item;
  171.         newNODE->next = i->next;
  172.         i->next = newNODE;
  173.         cout << "\nElement " << val1 << " has been found on the list at postion no: " << l
  174.             << " and element " << val2 << " has been found on the list at positon no: " << l + 1
  175.             << " So, " << item << " has been added between them at position no: " << l + 1 << endl;
  176.     }
  177.     else {
  178.         cout << "\nOPERATION failed..!" << endl;
  179.         cout << val1 << " and " << val2 << " couldn't be found sequencially." << endl;
  180.     }
  181. }
  182.  
  183. void insert_AT_pos(int position, int item) {
  184.     node *i; int l;
  185.     if (position == 1) {
  186.         insert_AT_first(item);
  187.     }
  188.     else {
  189.         for (i = head, l = 1; l != position - 1 && i->next != NULL; l++)
  190.             i = i->next;
  191.         if (l == position - 1) {
  192.             newNODE = new node;
  193.             newNODE->data = item;
  194.             newNODE->next = i->next;
  195.             i->next = newNODE;
  196.             cout << "\nElement " << item << " has been added at the list at position no: "
  197.                 << l + 1 << endl;
  198.         }
  199.         else {
  200.             cout << "\nOPERATION failed..!" << endl;
  201.             cout << "\nGiven position is out of the range." << endl;
  202.         }
  203.     }
  204. }
  205.  
  206. void insert_AT_last(int item) {
  207.     node *i; int l;
  208.     newNODE = new node;
  209.     newNODE->data = item;
  210.     newNODE->next = NULL;
  211.     newNODE->prev = tail;
  212.     if (head == NULL) {
  213.         head = newNODE;
  214.         tail = newNODE;
  215.         cout << "\nList was empty so, data " << item << " has been added at the list as the head."
  216.             << endl;
  217.     }
  218.     else {
  219.         tail->next = newNODE;
  220.         tail = tail->next;
  221.         cout << "\nElement " << item << " has been added at the tail of the list at position no: "
  222.             << ++length << endl;
  223.     }
  224. }
  225.  
  226. void delete_AT_first() {
  227.     node *i = head;
  228.     head = head->next;
  229.     head->prev = NULL;
  230.     cout << "\nPrevious head " << i->data << " has been deleted." << endl;
  231.     delete i;
  232.     if (head != NULL)
  233.         cout << "\nNew head value: " << head->data << endl;
  234. }
  235.  
  236. void delete_after_value(int value) {
  237.     node *i; int l;
  238.     for (i = head, l = 1; i->data != value && i->next != NULL; l++)
  239.         i = i->next;
  240.     if (i->data == value && i->next != NULL) {
  241.         newNODE = new node;
  242.         newNODE = i->next;
  243.         i->next = i->next->next;
  244.         if (i->next != NULL) {
  245.             i->next->prev = i;
  246.         }
  247.         else tail = i;
  248.         newNODE->next = NULL;
  249.         newNODE->prev = NULL;
  250.         delete newNODE;
  251.         cout << "\nElement " << value << " has been found at position no: " << l << " so, item at"
  252.             << " position no: " << l + 1 << " has been deleted." << endl;
  253.     }
  254.     else if (i->data == value && i->next == NULL) {
  255.         cout << "\nElement found at position no: " << l << ", which is the last element of the list."
  256.             << " So, operation could not be done." << endl;
  257.     }
  258.     else {
  259.         cout << "\nOPERATION Failed..!" << endl;
  260.         cout << "\nGiven Value isn't in the list." << endl;
  261.     }
  262. }
  263.  
  264. void delete_before_value(int value) {
  265.     if (head->data == value) {
  266.         cout << "\nOperation Failed. No element exists before the head." << endl;
  267.     }
  268.     else if (head->next != NULL) {
  269.         if (head->next->data == value)
  270.             delete_AT_first();
  271.         else if (head->next->next != NULL) {
  272.             node *i; int l;
  273.             for (i = head, l = 3; i->next->next->data != value && i->next->next->next != NULL; l++)
  274.                 i = i->next;
  275.             if (i->next->next->data == value) {
  276.                 newNODE = new node;
  277.                 newNODE = i->next;
  278.                 i->next = newNODE->next;
  279.                 newNODE->next = NULL;
  280.                 delete newNODE;
  281.                 cout << "\nElement " << value << " has been found at position no: " << l << " therefore,"
  282.                     << " element at position no: " << l - 1 << " has been deleted." << endl;
  283.             }
  284.             else cout << "\nOperation Failed. Such element doesn't exist on the list." << endl;
  285.         }
  286.         else cout << "\nOperation Failed. Such element doesn't exist on the list." << endl;
  287.     }
  288.     else cout << "\nOperation Failed. Such element doesn't exist on the list." << endl;
  289. }
  290.  
  291. void delete_between_values(int val1, int val2) {
  292.     node *i; int l;
  293.     for (i = head, l = 1; i->data != val1 && i->next != NULL; l++)
  294.         i = i->next;
  295.     if (i->data == val1 && i->next != NULL) {
  296.         if (i->next->next != NULL && i->next->next->data == val2) {
  297.             newNODE = new node;
  298.             newNODE = i->next;
  299.             i->next = i->next->next;
  300.             newNODE->next = NULL;
  301.             cout << "\nElement " << val1 << " has been found at position no: " << l << " and element "
  302.                 << val2 << " has been found at position no: " << l + 2 << " therefore, data "
  303.                 << newNODE->data << " has been deleted from position no: " << l + 1 << endl;
  304.         }
  305.         else cout << "\nNo such element exists between " << val1 << " and " << val2
  306.             << " or may be " << val2 << " doesn't exist." << endl;
  307.     }
  308.     else cout << "\nEither " << val1 << " or " << val2 << " or both doesn't exist." << endl;
  309. }
  310.  
  311. void delete_AT_pos(int position) {
  312.     node *i; int l;
  313.     if (position == 1)
  314.         delete_AT_first();
  315.     else {
  316.         for (i = head, l = 1; l != position - 1 && i->next != NULL; l++)
  317.             i = i->next;
  318.         if (i->next == NULL)
  319.             cout << "\nInvalid position." << endl;
  320.         else {
  321.             newNODE = new node;
  322.             newNODE = i->next;
  323.             i->next = newNODE->next;
  324.             newNODE->next = NULL;
  325.             cout << "\nElement at position no: " << position << " is " << newNODE->data << " and just got"
  326.                 << " deleted." << endl;
  327.             delete newNODE;
  328.         }
  329.     }
  330. }
  331.  
  332. void delete_AT_last() {
  333.     node *i;
  334.     if (head->next == NULL)
  335.         delete_AT_first();
  336.     else {
  337.         newNODE = new node;
  338.         newNODE = tail;
  339.         tail = tail->prev;
  340.         tail->next = NULL;
  341.         newNODE->prev = NULL;
  342.         cout << "\nLast element of the list was " << newNODE->data << " which was at position no: "
  343.             << length-- << " and just got deleted." << endl;
  344.         delete newNODE;
  345.     }
  346. }
RAW Paste Data