Insertion in the middle of Linked List in C++
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.
Methods Discussed
We will be covering the following methods –
- Approach 1: With additional Global size variable
- Approach 2: Without additional Global size variable
Approach 1: With additional Global Size Variable
- Method 1: Using external functions
- Method 2: Using member functions
Method 1
Method 2
Method 1
Run
next;
size++;
} while (node != head);
return size;
}
void insert(Node** head, int data, int &size) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = *head;
*head = newNode;
size++;
}
void insertMiddle(Node** head, int data, int &size) {
Node* newNode = new Node();
newNode->data = data;
if (*head == NULL) {
newNode->data = data;
newNode->next = *head;
*head = newNode;
size++;
return;
}
Node* temp = *head;
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
while (--mid) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}
void display(Node* node)
{
cout << "Linked List: \n";
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n\n";
}
int main()
{
Node* head = NULL;
int size = 0;
insert(&head, 25, size);
insert(&head, 5, size);
display(head);
insertMiddle(&head, 10, size);
display(head);
insertMiddle(&head, 20, size);
display(head);
insertMiddle(&head, 15, size);
display(head);
return 0;
}
Output
Linked List : 5 25 Linked List : 5 10 25 Linked List : 5 10 20 25 Linked List : 5 10 15 20 25
Method 2
Run
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
class LinkedList {
private:
Node* head;
int size; // Member variable to keep track of the size
public:
LinkedList() {
head = NULL;
size = 0;
}
int getCurrSize();
void insertMiddle(int data);
void insert(int data);
void display();
};
void LinkedList::insert(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = head;
head = newNode;
size++;
}
void LinkedList::insertMiddle(int data) {
Node* newNode = new Node();
newNode->data = data;
if (head == NULL) {
newNode->data = data;
newNode->next = head;
head = newNode;
size++;
return;
}
Node* temp = head;
int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;
while (--mid) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}
void LinkedList::display() {
cout << "Linked List : \n";
Node* node = head;
// as linked list will end when Node is Null
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n\n";
}
int main() {
LinkedList* list = new LinkedList();
list->insert(25);
list->insert(5);
list->display();
list->insertMiddle(10);
list->display();
list->insertMiddle(20);
list->display();
list->insertMiddle(15);
list->display();
return 0;
}
Output
Linked List : 5 25 Linked List : 5 10 25 Linked List : 5 10 20 25 Linked List : 5 10 15 20 25
Approach 2: Without additional Global Size Variable
- Method 1: Using external functions
- Method 2: Using member functions
Method 1
Method 2
Method 1
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
int getCurrSize(Node* node){
int size=0;
while(node!=NULL){
node = node->next;
size++;
}
return size;
}
void insert(Node** head, int data){
Node* newNode = new Node();
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
void insertMiddle(Node** head, int data){
Node* newNode = new Node();
newNode->data = data;
// if the LL was empty
if(*head == NULL){
newNode->data = data;
newNode->next = *head;
*head = newNode;
return;
}
// otherwise
Node* temp = *head;
int size = getCurrSize(*head);
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
// traverse to current mid position
while(--mid){
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
void display(Node* node)
{
cout << "Linked List : \n";
// as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " ";
node = node->next;
}
cout << "\n\n";
}
int main()
{
Node* head = NULL;
insert(&head,25);
insert(&head,5);
display(head);
insertMiddle(&head, 10);
display(head);
insertMiddle(&head, 20);
display(head);
insertMiddle(&head, 15);
display(head);
return 0;
}
Output
Linked List : 5 25 Linked List : 5 10 25 Linked List : 5 10 20 25 Linked List : 5 10 15 20 25
Method 2
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node* head;
public:
LinkedList() { // constructor
head = NULL;
}
int getCurrSize();
void insertMiddle(int data);
void insert(int data);
void display();
};
int LinkedList::getCurrSize(){
int size=0;
Node* temp = head;
while(temp!=NULL){
temp = temp->next;
size++;
}
return size;
}
void LinkedList::insert(int data){
Node* newNode = new Node();
newNode->data = data;
newNode->next = head;
head = newNode;
}
void LinkedList::insertMiddle(int data){
Node* newNode = new Node();
newNode->data = data;
// if the LL was empty
if(head == NULL){
newNode->data = data;
newNode->next = head;
head = newNode;
return;
}
// otherwise
Node* temp = head;
int size = getCurrSize();
// find correct insertion position for middle
int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
// traverse to current mid position
while(--mid){
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
void LinkedList::display()
{
cout << "Linked List : \n";
Node* node = head;
// as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " "; node = node->next;
}
cout << "\n\n"; } int main() { LinkedList* list = new LinkedList(); list->insert(25);
list->insert(5);
list->display();
list->insertMiddle(10);
list->display();
list->insertMiddle(20);
list->display();
list->insertMiddle(15);
list->display();
return 0;
}
Output
Linked List : 5 25 Linked List : 5 10 25 Linked List : 5 10 20 25 Linked List : 5 10 15 20 25
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