Number of positions for removing an element in a LinkedList

Overview

A LinkedList is a data structure that can grow dynamically, which means that we can add any number of nodes to it.

The operations of a LinkedList

These are the operations that we perform on a LinkedList:

Inserting
Deleting
Traversing
Updating
Searching

One of the main questions that may arise in our mind, with regards to a LinkedList, is how many legal positions are possible for inserting and/or removing an element in a LinkedList.

Note: The type of the LinkedList does not matter. It may be single, double, or circular; it does not matter.

Positions to insert an element in a LinkedList

In a LinkedList, there are three typical positions for insertion:

Insert at start.
Insert at end.
Insert at middle.

However, it is possible to insert an element at any point in a LinkedList.

Let’s understand these scenarios with the help of a diagram.

#include <iostream>
using namespace std;
// Create a node struct that contains a data having integer and a pointer
// to another node
struct Node{ 
  int data; 
  Node *next; 
};
class LinkedList{
    // Head pointer
    Node* head;
  public:
    // default constructor. 
    LinkedList(){
      head = NULL; //Initializing head pointer
    }
    // inserting elements (At start of the list)
    void insert(int val){
      // create a new node
      Node* new_node = new Node;
      new_node->data = val;
      new_node->next = NULL;
      // check If list is empty, make the new node, the head
      if (head == NULL)
        head = new_node;
      // else, make the new_node the head and its next, the previous head
      else{
        new_node->next = head;
        head = new_node;
      }
    }
    // loop over the list. return true if element found
    bool search(int val){
      Node* temp = head;
      while(temp != NULL){
        if (temp->data == val)
          return true;
        temp = temp->next;
      }
      return false;
    }
    void remove(int val){
      // If the head is to be deleted
      if (head->data == val){
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
      }
      // If there is only one element in the list
      if (head->next == NULL){
        // If the head is to be deleted. Assign null to the head
        if (head->data == val){
          delete head;
          head = NULL;
          return;
        }
        // else print, value not found
        cout << "Data not found!" << endl;
        return;
      }
      // Else loop over the list and search for the node to delete
      Node* temp = head;
      while(temp->next!= NULL){
        // When node is found, delete the node and modify the pointers
        if (temp->next->data == val){
          Node* temp_ptr = temp->next->next;
          delete temp->next;
          temp->next = temp_ptr;
          return;
        }
        temp = temp->next;
      }
      // Else, the value was neve in the list
      cout << "Value not found" << endl;
    }
    void show(){
      Node* temp = head;
      while(temp != NULL){
        cout << temp->data << " ";
        temp = temp->next;
      }
      cout << endl;
    }
};
int main(){
  LinkedList list;
  // inserting elements
  list.insert(61);
  list.insert(91);
  list.insert(11);
  list.insert(31);
  list.insert(71);
  cout << " *******Linked List:******** "<<endl;
  list.show();
  cout << "Removing 11: ";
  list.remove(11);
  list.show();
  cout << "Removing 26: ";
  list.remove(26);
  cout << "Searching for 71: ";
  cout << list.search(71) << endl;
  cout << "Searching for 100: ";
  cout << list.search(100) << endl;
}

Number of positions for removing an element in a LinkedList

Overview

The operations of a LinkedList

Positions to insert an element in a LinkedList

Legal position for removing an element from a LinkedList

Code example

Code explanation