Primitive Operations

This article has Primitive operation of linked list. Below script has code for insertion in beginning, insertion in end, printing linked list & insert after a given node.

 

 Starter Code :

 

#include<iostream>
using namespace std;

class Node  
{  
    public: 
    int data;  
    Node *next;  
};

 

Other Resources : Data Structures, Algorithms, Competitive Coding, Development

 

 Insert in front :

//Add node in front
void push(Node** head_ref, int new_data)  
{  
    /* 1. allocate node */
    Node* new_node = new Node();  
  
    /* 2. put in the data */
    new_node->data = new_data;  
  
    /* 3. Make next of new node as head */
    //Next pointing to current head
    new_node->next = (*head_ref);  
  
    //4. move the head to point to the new node *    //Now head is our new_node
    (*head_ref) = new_node;  
}

 

Insert After :  

//Inserting after
void insertAfter(Node* prev_node, int new_data) 
{ 
  /*1. check if the given prev_node is NULL */ 
  if (prev_node == NULL)  
  {  
   printf("previous node cannot be NULL");              
   return;   
  }   

  /* 2. allocate new node */
  Node* new_node = new Node();  
   
  /* 3. put in the data  */
  new_node->data  = new_data; 
   
  /* 4. Make next of new node as next of prev_node */
  new_node->next = prev_node->next;  
   
  /* 5. move the next of prev_node as new_node */
  prev_node->next = new_node; 
}

 

Other Resources : Data Structures, Algorithms, Competitive Coding, Development

 

 Insertion in end :

//Inserting at end
void append(Node** head_ref, int new_data) 
{ 
  /* 1. allocate node */
  Node* new_node = new Node();  
  
  struct Node *last = *head_ref;  
   
  /* 2. put in the data  */
  new_node->data  = new_data; 
  
  /* 3. This new node is going to be the last node, 
  so make next of it as NULL*/
  new_node->next = NULL; 
  
  /* 4. If the Linked List is empty, 
  then make the new node as head */
  if (*head_ref == NULL) 
  { 
     *head_ref = new_node; 
     return; 
  }   
       
  /* 5. Else traverse till the last node */
  while (last->next != NULL) 
      last = last->next; 
   
  /* 6. Change the next of last node */
  last->next = new_node; 
  return;     
}

 

Print Linked List : 

void printList(Node *node)  
{  
  while (node != NULL)  
  {  
    cout<<" "<<node->data;  
    node = node->next;  
  }  
}

 

Main code :

 

/* Driver code*/
int main()  
{  
  /* Start with the empty list */
  Node* head = NULL;  
      
  // Insert 6. So linked list becomes 6->NULL  
  append(&head, 6);  
      
  // Insert 7 at the beginning.  
  // So linked list becomes 7->6->NULL  
  push(&head, 7);  
      
  // Insert 1 at the beginning.  
  // So linked list becomes 1->7->6->NULL  
  push(&head, 1);  
      
  // Insert 4 at the end. So  
  // linked list becomes 1->7->6->4->NULL  
  append(&head, 4);  
      
  // Insert 8, after 7. So linked  
  // list becomes 1->7->8->6->4->NULL  
  insertAfter(head->next, 8);  
      
  cout<<"Created Linked list is: ";  
  printList(head);  
      
  return 0;  
}

 

Other Resources : Data Structures, Algorithms, Competitive Coding, Development