fork download
copy 
  1. // Singly Linked List
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. class node
  7. {
  8. public:
  9.   int data;
  10.   node *next;
  11.  
  12.   node(int val)
  13.   {
  14.     data = val;
  15.     next = NULL;
  16.   }
  17. };
  18.  
  19. void display(node *head)
  20. {
  21.   node *temp = head;
  22.   while (temp != NULL)
  23.   {
  24.     cout << temp->data << " -> ";
  25.     temp = temp->next;
  26.   }
  27.   cout << "NULL" << endl;
  28. }
  29.  
  30. // Insertion
  31.  
  32. void insertAtHead(node *&head, int val)
  33. {
  34.   node *n = new node(val); // created a block
  35.   n->next = head;          // connecting it with the head
  36.   head = n;
  37. }
  38. void insertAtTail(node *&head, int val)
  39. {
  40.  
  41.   node *n = new node(val);
  42.   if (head == NULL)
  43.   {
  44.     cerr << "Head is NULL" << endl;
  45.     head = n;
  46.     return;
  47.   }
  48.   node *temp = head;
  49.   while (temp->next != NULL)
  50.   {
  51.     cerr << "Traversing to node with value-> " << temp->data <<endl;
  52.     temp = temp->next;
  53.   }
  54.  
  55.   cerr << "Creating a node with value-> " << n->data  <<"with node of value -> " << temp->data<<endl;
  56.   temp->next = n;
  57. }
  58. void insertAtPosition(node* &head, int pos, int val){
  59.   if (pos <= 0) {
  60.     // Invalid position, nothing to insert
  61.     return;
  62.   }
  63.  
  64.   if (pos == 1 || head == NULL) {
  65.     // Insert at the head
  66.     insertAtHead(head, val);
  67.     return;
  68.   }
  69.  
  70.   int count = 1;
  71.   node* temp = head;
  72.   while (temp->next != NULL && count + 1 != pos) {
  73.     temp = temp->next;
  74.     count++;
  75.   }
  76.  
  77.   if (pos > count + 1 || temp->next == NULL) {
  78.     // Position is greater than the size of the list
  79.     // or the position is at the end of the list
  80.     return;
  81.   }
  82.  
  83.   node* n = new node(val);
  84.   n->next = temp->next;
  85.   temp->next = n;
  86. }
  87.  
  88. // Deletion
  89.  
  90. void deleteAtHead(node* &head){
  91.   node* deletingNode = head;
  92.   head = head->next;
  93.   delete deletingNode;
  94. }
  95.  
  96. void deleteAtTail(node *&head)
  97. {
  98.   if (head == NULL)
  99.   { // if Head is NULL, just return
  100.     return;
  101.   }
  102.   node *temp = head;
  103.   if (temp->next == NULL)
  104.   { // if LinkedList is having only one element, delete it
  105.     deleteAtHead(head);
  106.     return;
  107.   }
  108.  
  109.   while (temp->next->next != NULL)
  110.   { // if LL has more than 1 element, traverse to
  111.     // last 2nd
  112.     temp = temp->next;
  113.   }
  114.   node *deletingNode = temp->next; // element we need to delete
  115.   // because it is pointing at nothing now.
  116.   temp->next = NULL;   // point the last second node to NULL
  117.   delete deletingNode; // way to delete something from the memory
  118. }
  119. void deletePosition(node* &head, int pos){
  120.   if(pos <= 0 || head == nullptr){
  121.     // Invalid position or empty list, nothing to delete
  122.     return;
  123.   }
  124.  
  125.   if(pos == 1){
  126.     // Deleting the head node
  127.     deleteAtHead(head);
  128.     return;
  129.   }
  130.  
  131.   int count = 1;
  132.   node* temp = head;
  133.   while(temp->next != nullptr && count + 1 != pos){
  134.     temp = temp->next;
  135.     count++;
  136.   }
  137.  
  138.   if(pos > count + 1 || temp->next == nullptr){
  139.     // Position is greater than the size of the list
  140.     // or the position is at the end of the list
  141.     return;
  142.   }
  143.  
  144.   // Delete the node at the given position
  145.   node* toDelete = temp->next;
  146.   temp->next = toDelete->next;
  147.   delete toDelete;
  148. }
  149.  
  150. // Searching
  151.  
  152. bool searchInLL(node *head, int target)
  153. {
  154.  
  155.   node *temp = head;
  156.  
  157.   while (temp != NULL)
  158.   {
  159.     if (temp->data == target)
  160.       return true;
  161.     temp = temp->next;
  162.   }
  163.  
  164.   return false;
  165. }
  166.  
  167. // Problems
  168.  
  169. void findPointers(node *head)
  170. {
  171.   node *temp = head;
  172.  
  173.   int firstIndex = -1;
  174.   int secondIndex = -1;
  175.   int count = 1;
  176.   while (temp->next != NULL)
  177.   {
  178.     if (temp->data == 0)
  179.     { // if it's a node with zero value
  180.       if (firstIndex == -1)
  181.       { // when it's very first time we saw zero
  182.         firstIndex = count;
  183.       }
  184.       else
  185.       { // if we already saw zero somewhere, probably it's second index
  186.         secondIndex = count;
  187.       }
  188.     }
  189.     temp = temp->next; // move the pointer to next node
  190.     count++;           // count++ to keep a track of indices
  191.   }
  192.   // once loop is over, we might have got our firstI and secondI
  193.   cout << firstIndex << ' ' << secondIndex << endl;
  194. }
  195.  
  196. int sumLinkList(node *head)
  197. {
  198.   int sum = 0;
  199.   if (head == NULL)
  200.     return sum;
  201.   node *temp = head;
  202.   while (temp != NULL)
  203.   {
  204.     sum += (temp->data);
  205.     temp = temp->next;
  206.   }
  207.   return sum;
  208. }
  209. int main()
  210. {
  211.  
  212.   node *head = NULL;
  213.  
  214.   insertAtTail(head, 1);
  215.   insertAtTail(head, 2);
  216.   insertAtTail(head, 3);
  217.   insertAtHead(head, 4);
  218.   display(head);
  219.   deleteAtTail(head);
  220.   display(head);
  221.   insertAtHead(head, 5);
  222.   display(head);
  223.   insertAtHead(head, 6);
  224.   display(head);
  225.   deleteAtTail(head);
  226.   display(head);
  227.   deleteAtHead(head);
  228.   display(head);
  229.  
  230.   // Create a node
  231.   // add at last
  232.   // add at first
  233.   // remove from last
  234.   // remove from first
  235.   // Search in LL
  236. }
Success #stdin #stdout #stderr 0.01s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 -> 1 -> 2 -> 3 -> NULL
4 -> 1 -> 2 -> NULL
5 -> 4 -> 1 -> 2 -> NULL
6 -> 5 -> 4 -> 1 -> 2 -> NULL
6 -> 5 -> 4 -> 1 -> NULL
5 -> 4 -> 1 -> NULL
stderr
copy 
Head is NULL
Creating a node with value-> 2with node of value -> 1
Traversing to node with value-> 1
Creating a node with value-> 3with node of value -> 2
https://ideone.com/ZsLsAT
language:
C++14 (gcc 8.3)
created:
2 years 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!