Linked List Insertion and Deletion Program
Program for Singly Linked List Insertion and Deletion in C++
Lets try to understand how we can do Insertion and deletion Operations on a Linked List in C++. We will look at most effective methods to do so.
We will look at all different methods to insert and delete in the Linked List.
Make sure that you are acquainted with what Linked List is, all terminologies like
- head
- tail
- node
- data
- pointer
- next etc.
Structure of the Linked List
Using Struct
Using Class
Using Struct
struct Node{
int data;
struct Node *next;
};Using Class
class Node{
public:
int data;
Node *next;
};
Insertion in Linked List in C++
We will look at three different methods –
- Method 1: Linked List Insertion using Struct
- Method 2: Linked List Insertion using class (without class methods)
- Method 3: Linked List Insertion using class (with class methods)
Insertion Positions
Insertion can be done at the following positions, we will write separate methods for each to demonstrate all possible variations –
- At start (Default)
- At last
- After a certain Node
Method 1
Method 2
Method 3
Method 1
Run
#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
void insertStart(struct Node** head, int data){
// dynamically create memory for this newNode
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//re-assign head to this newNode
*head = newNode;
}
void insertEnd(struct Node** head, int data){
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
// since this will be the last node so it will point to NULL
newNode->next = NULL;
// if the Linked List is empty this is the first node being entered
if(*head==NULL){
*head = newNode;
return;
}
// create another variable to traverse the LL
// *head should not be used as we do not want to change head
struct Node* temp = *head;
// traverse to the last node of Linked List
while(temp->next!=NULL)
temp = temp->next;
// assign last node's next to this newNode
temp->next = newNode;
}
// required for insertAfter
int getCurrSize(struct Node* node){
int size=0;
while(node!=NULL){
node = node->next;
size++;
}
return size;
}
void insertAfter(int n, int data, struct Node** head)
{
int size = getCurrSize(*head);
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if(n < 1 || n > size)
cout << "Invalid position to insert"; else { struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = data;
newNode->next = NULL;
// temp used to traverse the Linked List
struct Node* temp = *head;
// traverse till the nth node
while(--n)
temp=temp->next;
// assign newNode's next to nth node's next
newNode->next= temp->next;
// assign nth node's next to this new node
temp->next = newNode;
// newNode inserted b/w 3rd and 4th node
}
}
void display(struct Node* node){
// as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " "; node = node->next;
}
cout << endl;
}
int main()
{
struct Node* head = NULL;
// Need '&' i.e. address as we need to change head
insertStart(&head,5);
insertStart(&head,10);
insertStart(&head,15);
insertEnd(&head,20);
insertEnd(&head,25);
insertEnd(&head,30);
insertEnd(&head,35);
//Inserts data: 100 after 3rd position
insertAfter(3, 100,&head);
display(head);
return 0;
}
Method 2
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void insertStart(Node** head, int data){
Node* newNode = new Node();
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//changing the new head to this freshly entered node
*head = newNode;
}
void insertLast(Node** head, int data){
Node* newNode = new Node();
newNode->data = data;
// since this will be the last node so it will point to NULL
newNode->next = NULL;
//need this if there is no node present in linked list at all
if(*head==NULL){
*head = newNode;
return;
}
struct Node* temp = *head;
// traverse to the last node of Linked List
while(temp->next!=NULL)
temp = temp->next;
// assign last node's next to this newNode
temp->next = newNode;
}
int calcSize(Node* node){
int size=0;
while(node!=NULL){
node = node->next;
size++;
}
return size;
}
void insertPosition(int n, int data, Node** head)
{
int size = calcSize(*head);
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if(n < 1 || size < n)
{
cout << "Not Valid position to insert" << endl;
}
else {
Node* temp = *head;
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
// traverse till the nth node
while(--n)
temp=temp->next;
// assign newNode's next to nth node's next
newNode->next= temp->next;
// assign nth node's next to this new node
temp->next = newNode;
// newNode inserted b/w 3rd and 4th node
}
}
void display(Node* node){
//as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " "; node = node->next;
}
cout << endl;
}
int main(){
Node* head = NULL;
/*Need & i.e. address as we
need to change head address
*/
insertStart(&head,5);
insertStart(&head,10);
insertStart(&head,15);
insertLast(&head,20);
insertLast(&head,25);
insertLast(&head,30);
insertLast(&head,35);
//Inserts after 3rd position
insertPosition(3,100,&head);
/*No need for & i.e. address as we do not
need to change head address
*/
display(head);
return 0;
}Method 3
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node* head;
public:
LinkedList() { // constructor
head = NULL;
}
int calcSize();
void insertStart(int data);
void insertLast(int data);
void insertPosition(int pos, int data);
void display();
};
void LinkedList::insertStart(int data){
Node* newNode = new Node();
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = head;
//changing the new head to this freshly entered node
head = newNode;
}
void LinkedList::insertLast(int data){
Node* newNode = new Node();
newNode->data = data;
// since this will be the last node so it will point to NULL
newNode->next = NULL;
//need this if there is no node present in linked list at all
if(head==NULL){
head = newNode;
return;
}
struct Node* temp = head;
// traverse to the last node of Linked List
while(temp->next!=NULL)
temp = temp->next;
// assign last node's next to this newNode
temp->next = newNode;
}
int LinkedList::calcSize(){
Node* node = new Node();
node = head;
int size=0;
while(node!=NULL){
node = node->next;
size++;
}
return size;
}
void LinkedList::insertPosition(int n, int data)
{
int size = calcSize();
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if( n < 1 || size < n)
{
cout << "Not Valid position to insert" << endl;
}
else {
Node* temp = head;
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
// traverse till the nth node
while(--n)
temp=temp->next;
// assign newNode's next to nth node's next
newNode->next= temp->next;
// assign nth node's next to this new node
temp->next = newNode;
// newNode inserted b/w 3rd and 4th node
}
}
void LinkedList::display(){
Node* node = new Node();
node = head;
//as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " "; node = node->next;
}
cout << endl;
}
int main()
{
LinkedList* list = new LinkedList();
list->insertStart(5);
list->insertStart(10);
list->insertStart(15);
list->insertLast(20);
list->insertLast(25);
list->insertLast(30);
list->insertLast(35);
// Inserts after 3rd position
list->insertPosition(3, 100);
list->display();
return 0;
}Output
15 10 5 100 20 25 30 35
Deletion in Linked List in C++
Again, we will look at three different methods –
- Method 1: Linked List deletion using Struct
- Method 2: Linked List deletion using class (without class methods)
- Method 3: Linked List deletion using class (with class methods)
Insertion Positions
Deletion can be done at the following positions, we will write separate methods for each to demonstrate all possible variations –
- At start (Default)
- At last
- After a certain Node
Method 1
Method 2
Method 3
Method 1
Run
#include<iostream>
#include<stdlib.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
void insert (struct Node **head, int data);
int getCurrSize (struct Node *node);
void deleteStart (struct Node **head)
{
struct Node *temp = *head;
// if there are no nodes in Linked List can't delete
if (*head == NULL)
{
cout << "Linked List Empty, nothing to delete";
return;
}
// move head to next node
*head = (*head)->next;
cout << "\nValue deleted: " << temp->data << endl;
free (temp);
}
void deleteEnd (struct Node **head)
{
struct Node *temp = *head;
struct Node *previous;
// if there are no nodes in Linked List can't delete
if (*head == NULL)
{
cout << "Linked List Empty, nothing to delete";
return;
}
// if Linked List has only 1 node
if (temp->next == NULL)
{
*head = NULL;
cout << "\nValue deleted: " << temp->data << endl;
return;
}
// else traverse to the last node
while (temp->next != NULL)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// Curr assign 2nd last node's next to Null
previous->next = NULL;
cout << "\nValue deleted: " << temp->data << endl;
// delete the last node
free (temp);
// 2nd last now becomes the last node
}
// to deletePos nth node
void deletePos (struct Node **head, int n)
{
struct Node *temp = *head;
struct Node *previous;
//if the head node itself needs to be deleted
int size = getCurrSize (*head);
// not valid
if (n < 1 || n > size)
{
cout << "\nEnter valid position\n";
return;
}
// delete the first node
if (n == 1)
{
deleteStart (head);
return;
}
// traverse to the nth node
while (--n)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// change previous node's next node to nth node's next node
previous->next = temp->next;
cout << "\nValue deleted: " << temp->data << endl;
// delete this nth node
free (temp);
}
void insert (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// required for deletePos
int getCurrSize (struct Node *node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}
void display (struct Node *node)
{
// as linked list will end when Node is Null
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main ()
{
struct Node *head = NULL;
insert (&head, 10);
insert (&head, 20);
insert (&head, 30);
insert (&head, 40);
insert (&head, 50);
insert (&head, 60);
insert (&head, 70);
display (head);
deleteStart (&head);
display (head);
deleteEnd (&head);
display (head);
// delete 4th node
deletePos (&head, 4);
display (head);
// delete the 1st node
deletePos (&head, 1);
display (head);
deletePos (&head, -2); // invalid pos
deletePos (&head, 10); // invalid pos
return 0;
}Method 2
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
int calcSize (Node * node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}
void deleteStart (Node ** head)
{
Node *temp = *head;
// if there are no nodes in Linked List can't delete
if (*head == NULL)
{
printf ("Linked List Empty, nothing to delete");
return;
}
cout << "\nValue Deleted: " << temp->data;
// move head to next node
*head = (*head)->next;
free (temp);
}
void deleteEnd (Node ** head)
{
Node *temp = *head;
Node *previous;
// Can't delete from empty Linked List
if (*head == NULL)
{
cout << ("Empty List, can't delete");
return;
}
// if Linked List has only 1 node
if (temp->next == NULL)
{
cout << "\nValue Deleted: " << (*head)->data;
*head = NULL;
return;
}
// else traverse to the last node
while (temp->next != NULL)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// Curr assign 2nd last node's next to Null
previous->next = NULL;
cout << "\nValue Deleted: " << temp->data;
// delete the last node
free (temp);
// 2nd last now becomes the last node
}
void deletePos (Node ** head, int n)
{
Node *temp = *head;
Node *previous;
int size = calcSize (*head);
if (n < 1 || n > size)
{
cout << "\nEnter valid position\n";
return;
}
// if first node has to be deleted
if (n == 1)
{
deleteStart (head);
return;
}
//traverse till the nth node
while (--n)
{
// store previous link as we need to change its next val
previous = temp;
temp = temp->next;
}
// previous node's next changed to nth node's next
previous->next = temp->next;
cout << "\nValue deleted: " << temp->data;
free (temp);
}
void insert (Node ** head, int data)
{
Node *newNode = new Node ();
newNode->data = data;
newNode->next = *head;
// assigned head to newNode
*head = newNode;
}
void display (Node * node)
{
cout << "\n";
//as linked list will end when Node is Null
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main ()
{
Node *head = NULL;
insert (&head, 10);
insert (&head, 20);
insert (&head, 30);
insert (&head, 40);
insert (&head, 50);
insert (&head, 60);
insert (&head, 70);
display (head);
deleteStart (&head);
display (head);
deleteEnd (&head);
display (head);
// delete 4th node
deletePos (&head, 4);
display (head);
// delete the 1st node
deletePos (&head, 1);
display (head);
deletePos (&head, -2); // invalid pos
deletePos (&head, 10); // invalid pos
return 0;
}Method 3
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node * head;
public:
LinkedList ()
{ // constructor
head = NULL;
}
int calcSize ();
void deleteStart ();
void deleteEnd ();
void deletePos (int pos);
void display ();
void insert (int data);
};
void LinkedList::deleteStart ()
{
Node *temp = head;
// if there are no nodes in Linked List can't delete
if (head == NULL)
{
printf ("Linked List Empty, nothing to delete");
return;
}
cout << "\nValue Deleted: " << temp->data;
// move head to next node
head = head->next;
free (temp);
}
void LinkedList::deleteEnd ()
{
Node *temp = head;
Node *previous;
// Can't delete from empty Linked List
if (head == NULL)
{
cout << ("Empty List, can't delete");
return;
}
// if Linked List has only 1 node
if (temp->next == NULL)
{
cout << "\nValue Deleted: " << head->data;
head = NULL;
return;
}
// else traverse to the last node
while (temp->next != NULL)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// Curr assign 2nd last node's next to Null
previous->next = NULL;
cout << "\nValue Deleted: " << temp->data;
// delete the last node
free (temp);
// 2nd last now becomes the last node
}
void LinkedList::deletePos (int n)
{
Node *temp = head;
Node *previous;
int size = calcSize ();
if (n < 1 || n > size)
{
cout << "\nEnter valid position\n";
return;
}
// if first node has to be deleted
if (n == 1)
{
deleteStart ();
return;
}
//traverse till the nth node
while (--n)
{
// store previous link as we need to change its next val
previous = temp;
temp = temp->next;
}
// previous node's next changed to nth node's next
previous->next = temp->next;
cout << "\nValue deleted: " << temp->data;
free (temp);
}
int LinkedList::calcSize ()
{
Node *node = new Node ();
node = head;
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}
void LinkedList::insert (int data)
{
Node *newNode = new Node ();
newNode->data = data;
newNode->next = head;
// assigned head to newNode
head = newNode;
}
void LinkedList::display ()
{
Node *node = new Node ();
node = head;
cout << "\n";
//as linked list will end when Node is Null
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main ()
{
LinkedList *list = new LinkedList ();
list->insert (10);
list->insert (20);
list->insert (30);
list->insert (40);
list->insert (50);
list->insert (60);
list->insert (70);
list->display ();
list->deleteStart ();
list->display ();
list->deleteEnd ();
list->display ();
// delete 4th node
list->deletePos (4);
list->display ();
// delete the 1st node
list->deletePos (1);
list->display ();
list->deletePos (-2); // invalid pos
list->deletePos (10); // invalid pos
}Output
70 60 50 40 30 20 10
Value Deleted: 70
60 50 40 30 20 10
Value Deleted: 10
60 50 40 30 20
Value deleted: 30
60 50 40 20
Value Deleted: 60
50 40 20
Enter valid position
Enter valid position
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
Login/Signup to comment