Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
communitycreator

# 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.

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

public:
// default constructor.
}

// 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)
// else, make the new_node the head and its next, the previous head
else{
}
}

// 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;
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){
return;
}
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(){
// 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++
communitycreator

CONTRIBUTOR