Data Structures Data Structures Resources
Python Java C++ C C# PHP R SQL DS Algo InterviewQ

Linked List Operations - Traverse, Insert and Delete



In the previous section, we had discussed about structure of linked list. In this section, we will learn about basic operations of a linked list.

Traverse a Linked List

Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item.

//C++ Code
//Display the content of the list
void PrintList() {
  
  //1. create a temp node pointing to head
  Node* temp = head;
  
  //2. if the temp node is not null continue 
  //   displaying the content and move to the 
  //   next node till the temp becomes null
  if(temp != NULL) {
    cout<<"\nThe list contains: ";
    while(temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
    }
  } else {
    
    //3. If the temp node is null at the start, 
    //   the list is empty
    cout<<"\nThe list is empty.";
  }
} 

Insert a new node in Linked List

A new node can be inserted into a list in three ways:

  • Insert a node at the start
  • Insert a node at the given position
  • Insert a node at the end

Insert a new node at the start

In this method, a new node is inserted at the beginning of the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at the start, the list becomes 100->10->20->30.

Inserting a new node at the beginning of the Linked List is very easy. First, a new node with given element is created. It is then added before the head of the given list that makes the newly added node to new head of the list by changing the head pointer to point to the new node.

//C++ Code
//Inserts a new node at the start 
void push_front(int newElement) {
  
  //1. allocate a new node
  Node* newNode = new Node();
  
  //2. assign data element 
  newNode->data = newElement;
  
  //3. make next node of new node as head
  newNode->next = head;
  
  //4. make new node as head 
  head = newNode;   
}

Insert a new node at the given position

In this method, a new element is inserted at the specified position in the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.

First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not. In case of null, the specified position does not exist. In other case, assign next of the new node as next of the previous node and next of previous node as new node.

//C++ Code
//Inserts a new node at the given position
void push_at(int newElement, int position) {
  
  //1. allocate node to new element
  Node* newNode = new Node(); 
  newNode->data = newElement;
  newNode->next = NULL;

  //2. check if the position is > 0
  if(position < 1) {
    cout<<"\nposition should be >= 1.";
  } else if (position == 1) {
  
  //3. if the position is 1, make next of the
  //   new node as head and new node as head
    newNode->next = head;
    head = newNode;
  } else {

   //4. Else, make a temp node and traverse to the 
   //   node previous to the position
    Node* temp = head;
    for(int i = 1; i < position-1; i++) {
      if(temp != NULL) {
        temp = temp->next;
      }
    }
 
    //5. If the previous node is not null, make 
    //   newNode next as temp next and temp next 
    //   as newNode.
    if(temp != NULL) {
      newNode->next = temp->next;
      temp->next = newNode;  
    } else {
      
      //6. When the previous node is null
      cout<<"\nThe previous node is null.";
    } 
  }
}

Insert a new node at the end

In this method, a new node is inserted at the end of the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at the end, the list becomes 10->20->30->100.

Inserting a new node at the end of the Linked List is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node.

//C++ Code
//Inserts a new node at the end
void push_back(int newElement) {
  
  //1. allocate node
  Node* newNode = new Node();
  
  //2. assign data element
  newNode->data = newElement;
  
  //3. assign null to the next of new node
  newNode->next = NULL; 
  
  //4. Check the list is empty or not,
  //   if empty make the new node as head 
  if(head == NULL) {
    head = newNode;
  } else {
    
    //5. Else, traverse to the last node
    Node* temp = head;
    while(temp->next != NULL)
      temp = temp->next;
    
    //6. Change the next of last node to new node
    temp->next = newNode;
  }    
}

Delete a Node from Linked List

A node can be deleted from a list in three ways:

  • Delete the first node
  • Delete the node at given position
  • Delete the last node

Delete the first node

In this method, the first node of the linked list is deleted. For example - if the given list is 10->20->30->40 and the first node is deleted, the list becomes 20->30->40.

Deleting the first node of the linked list is very easy. If the head is not null then create a temp node pointing to head and move head to the next of head. Then delete the temp node.

//C++ Code
//Deletes the first node
void pop_front() {
  if(head != NULL) {
    
    //1. if head is not null, create a
    //   temp node pointing to head
    Node* temp = head;

    //2. move head to next of head
    head = head->next; 

    //3. delete temp node
    free(temp); 
  }
}

Delete a node from middle

In this method, a node at the specified position in the linked list is deleted. For example - if the given list is 10->20->30 and the 2nd node is deleted, the list becomes 10->20.

First, the specified position must be greater than equal to 1. If the specified position is 1 and head is not null, then make the head to head next. Else, traverse to the node that is previous to the specified position. If the specified node and previous to the specified node are not null then adjust the link and delete the node at specified position. In other case, the specified node will be already null.

//C++ Code
//Deletes the node at given position
void pop_at(int position) {     
  
  //1. check if the position is > 0
  if(position < 1) {
    cout<<"\nposition should be >= 1.";
  } else if (position == 1 && head != NULL) {
      
    //2. if the position is 1 and head is not null,
    //   make head to head next and delete the 
    //   previous head
    Node* nodeToDelete = head;
    head = head->next;
    free(nodeToDelete);
  } else {
    
    //3. Else, make a temp node and traverse to the 
    //   node previous to the position
    Node* temp = head;
    for(int i = 1; i < position-1; i++) {
      if(temp != NULL) {
        temp = temp->next;
      }
    }
 
    //4. If the previous node and next of the previous  
    //   is not null, adjust links 
    if(temp != NULL && temp->next != NULL) {
        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        free(nodeToDelete); 
    } else {

      //5. Else the given node will be empty.
      cout<<"\nThe node is already null.";
    }       
  }
} 

Delete the last node

In this method, the last node of the linked list is deleted. For example - if the given list is 10->20->30->40 and the last node is deleted, the list becomes 10->20->30.

Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, then release the head, else traverse to the second last node of the list. Then, link the next of second last node to NULL and delete the last node.

//C++ Code
//Deletes the last node
void pop_back() {
  if(head != NULL) {
    
    //1. if head in not null and next of head
    //   is null, release the head
    if(head->next == NULL) {
      head = NULL;
    } else {
      
      //2. Else, traverse to the second last 
      //   element of the list
      Node* temp = head;
      while(temp->next->next != NULL)
        temp = temp->next;
      
      //3. Change the next of the second 
      //   last node to null and delete the
      //   last node
      Node* lastNode = temp->next;
      temp->next = NULL; 
      free(lastNode);
    }
  }
}

5