Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
linkedlist
communitycreator

Number of positions for removing an element in a LinkedList

Hasham Ahmad

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.

Positions for inserting an element in a LinkedList

Legal position for removing an element from a LinkedList

We can remove any element from a given LinkedList. Let’s understand the process of removing an element with the help of a scenario. Suppose that a LinkedList has n number of elements. We can remove any element located at any position in the LinkedList. Hence, in this case, the possible position(s) for removing elements from the given LinkedList are n.

Delete element

Code example

#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;
}

Code explanation

  • Lines 6 to 9: We make a node struct that contains a data int and a pointer.
  • Line 11: We create a class called LinkedList.
  • Lines 17 to 21: We create a default constructor and initialize the head pointer.
  • Lines 24 to 41: We create inserting elements at the start function.
  • Lines 44 to 54: We create the search function.
  • Lines 57 to 99: We create the remove function.
  • Lines 101 to 110: We create the remove function.
  • Lines 113 to 136: We call all these functions in the main.

RELATED TAGS

c++
linkedlist
communitycreator
RELATED COURSES

View all Courses

Keep Exploring