fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class DLLNode
  4. {
  5. public:
  6.     int data;
  7.     DLLNode *next, *prev;
  8.     DLLNode(int n) : data(n), next(nullptr), prev(nullptr) {}
  9. };
  10. class DLL
  11. {
  12. public:
  13.     DLLNode *head;
  14.     DLL()
  15.     {
  16.         head = nullptr;
  17.     }
  18.     bool empty()
  19.     {
  20.         return head == nullptr;
  21.     }
  22.     void InsertFromHead(int value)
  23.     {
  24.         // 1-declare a newnode and init with value
  25.         DLLNode *new_node = new DLLNode(value);
  26.         // 2-check if the list is empty--true--> head = newnode and terminate
  27.         if (empty())
  28.         {
  29.             head = new_node;
  30.             return;
  31.         }
  32.         // insert
  33.         // 1-newnode points to head
  34.         new_node->next = head;
  35.         // 2-the prev of head point to newnode
  36.         head->prev = new_node;
  37.         // 3-move the head to newnode
  38.         head = new_node;
  39.     }
  40.     void InsertFromTail(int value)
  41.     {
  42.         // 1-declare a newnode and init with value
  43.         DLLNode *new_node = new DLLNode(value);
  44.         // 2-check if the list is empty--true--> head = newnode and terminate
  45.         if (empty())
  46.         {
  47.             head = new_node;
  48.             return;
  49.         }
  50.         // 3- declare a temp and move to the last element
  51.         DLLNode *temp = head;
  52.         while (temp->next)
  53.         {
  54.             temp = temp->next;
  55.         }
  56.         // insert
  57.         // 1-prev of new point to the last elemtn
  58.         new_node->prev = temp;
  59.         // 2-last element point to the newelement
  60.         temp->next = new_node;
  61.     }
  62.         void InsertPos(int value, int pos)
  63.     {
  64.         // 1-declare a newnode and init with value
  65.         DLLNode *new_node = new DLLNode(value);
  66.         // 2-check if the list is empty true--> head = newnode and terminate
  67.         if (empty())
  68.         {
  69.             head = new_node;
  70.             return;
  71.         }
  72.         // 3-pos > size pos = size
  73.         //  if(pos>sz) pos = sz;
  74.         // 4-declare a temp ptr and iterat till the pos
  75.         DLLNode *temp = head;
  76.         for (int i = 1; i < pos - 1; temp = temp->next, i++)
  77.             ;
  78.         // شبك الجديد الاول
  79.         //  1- newnode points to what the elemrnt in pos points
  80.         new_node->next = temp->next;
  81.         // 2- the prev of newnode points to the element in the pos
  82.         new_node->prev = temp;
  83.         // القديم بقاا
  84.         //  1- pos points to new node
  85.         temp->next = new_node;
  86.         // 2- the prev of what the new node points make it point to new node
  87.         temp->next->prev = new_node;
  88.     }
  89.     int sz()
  90.     {
  91.         int cntr = 0;
  92.         if (empty())
  93.         {
  94.             return cntr;
  95.         }
  96.         DLLNode *temp = head;
  97.  
  98.         while (temp)
  99.         {
  100.             cntr++;
  101.             temp = temp->next;
  102.         }
  103.         return cntr;
  104.     }
  105.     bool IsFound(int n)
  106.     {
  107.         bool ret = false;
  108.         if (empty())
  109.             return ret;
  110.         DLLNode *temp = head;
  111.         while (temp)
  112.         {
  113.             if (temp->data == n)
  114.             {
  115.                 ret = true;
  116.                 break;
  117.             }
  118.             temp = temp->next;
  119.         }
  120.         return ret;
  121.     }
  122.     int RemoveFromHead()
  123.     {
  124.         // check if it is empty--> terminate
  125.         int delval = -1;
  126.         if (empty())
  127.         {
  128.             return delval;
  129.         }
  130.         // check if this element is the last in the list
  131.         if (head->next == nullptr)
  132.         {
  133.             delval = head->data;
  134.             delete head;
  135.             head = nullptr;
  136.             return delval;
  137.         }
  138.         // store the the first node and its value
  139.         DLLNode *delptr = head;
  140.         delval = delptr->data;
  141.         // make the prev of the node after points to null
  142.         head->next->prev = nullptr;
  143.         // move head to this node
  144.         head = head->next;
  145.         delete delptr;
  146.         return delval;
  147.     }
  148.     int RemoveFromTail()
  149.     {
  150.         // check if it is empty--> terminate
  151.         int delval = -1;
  152.         if (empty())
  153.         {
  154.             return delval;
  155.         }
  156.         // check if this element is the last in the list
  157.         if (head->next == nullptr)
  158.         {
  159.             delval = head->data;
  160.             delete head;
  161.             head = nullptr;
  162.             return delval;
  163.         }
  164.         // declare temp node iterat till the last;
  165.         DLLNode *temp = head;
  166.         while (temp->next)
  167.         {
  168.             temp = temp->next;
  169.         }
  170.         delval = temp->data;
  171.         // store the the last node node and its value in delptr and its value in delval
  172.         // the next of the node before equal nullptr
  173.         temp->prev->next = nullptr;
  174.         delete temp;
  175.         return delval;
  176.     }
  177.     int RemovePos(int n, int pos)
  178.     {
  179.         // empty list or the n is not in the list
  180.         int delval = -1;
  181.         if (empty() or !IsFound(n))
  182.         {
  183.             return delval;
  184.         }
  185.         // this is only one element in list
  186.         if (head->next == nullptr)
  187.         {
  188.             delval = head->data;
  189.             delete head;
  190.             head = nullptr;
  191.             return delval;
  192.         }
  193.         // if(pos > sz) pos = sz;
  194.         DLLNode *temp = head;
  195.         // store the elemt in posistion pos
  196.         for (int i = 1; i < pos; i++, temp = temp->next);
  197.         DLLNode *delptr = temp;
  198.         delval = delptr->data;
  199.         // 1- cut the conection betw the pos and the node befor and make the node before to point
  200.         // to the node after the pos node
  201.         if(temp->prev)
  202.             temp->prev->next = temp->next;
  203.         // 2 cut the connection between the node after and make the prev of node after to point
  204.         //  the node before pos node
  205.         //  this condetion as the pos may be the last since this next is nullptr ????!!!!! nullptr->prev errror
  206.         if (temp->next) {
  207.            temp->next->prev = temp->prev;
  208.             if(!temp->prev) {
  209.                 head = head->next;
  210.             }
  211.         }
  212.         // 3- finally delete the pos node
  213.         delete delptr;
  214.         return delval;
  215.     }
  216.     void print()
  217.     {
  218.         if (empty())
  219.         {
  220.             return;
  221.         }
  222.         DLLNode *temp = head;
  223.         while (temp)
  224.         {
  225.             cout << temp->data << ' ';
  226.             temp = temp->next;
  227.         }
  228.         cout << '\n';
  229.     }
  230. };
  231. int main()
  232. {
  233. #ifndef ONLINE_JUDGE
  234.     freopen("Input.txt", "r", stdin);
  235. #endif
  236.  
  237. #ifdef ONLINE_JUDGE
  238.  
  239. #endif
  240.     DLL dll;
  241.  
  242.     // Insert at head
  243.     dll.InsertFromHead(10);
  244.     dll.InsertFromHead(20);
  245.     dll.InsertFromHead(30);
  246.     cout << "After inserting at head (30, 20, 10):\n";
  247.     DLLNode *temp = dll.head;
  248.     dll.print();
  249.  
  250.     // Insert at tail
  251.     dll.InsertFromTail(5);
  252.     dll.InsertFromTail(1);
  253.     cout << "After inserting at tail (5, 1):\n";
  254.     dll.print();
  255.  
  256.     // Insert at position
  257.     dll.InsertPos(15, 2); // Insert 15 at position 2
  258.     cout << "After inserting 15 at position 2:\n";
  259.     dll.print();
  260.  
  261.     // Remove from head
  262.     cout << "Removing from head: " << dll.RemoveFromHead() << "\n";
  263.     cout << "List after removing from head:\n";
  264.     dll.print();
  265.  
  266.     // Remove from tail
  267.     cout << "Removing from tail: " << dll.RemoveFromTail() << "\n";
  268.     cout << "List after removing from tail:\n";
  269.     dll.print();
  270.  
  271.     // Check if element is found
  272.     int searchValue = 15;
  273.     cout << "Is " << searchValue << " found? " << (dll.IsFound(searchValue) ? "Yes" : "No") << "\n";
  274.  
  275.     // Remove a specific position
  276.     int removePos = 1;
  277.     cout << "Removing element at position " << removePos << ": " << dll.RemovePos(15, removePos) << "\n";
  278.     cout << "List after removing position " << removePos << ": ";
  279.     dll.print();
  280.  
  281.     return 0;
  282. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
After inserting at head (30, 20, 10):
30 20 10 
After inserting at tail (5, 1):
30 20 10 5 1 
After inserting 15 at position 2:
30 15 20 10 5 1 
Removing from head: 30
List after removing from head:
15 20 10 5 1 
Removing from tail: 1
List after removing from tail:
15 20 10 5 
Is 15 found? Yes
Removing element at position 1: 15
List after removing position 1: 20 10 5
https://ideone.com/mi8pI6
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!