.png)
Linked List Insertion in a Singly Linked List
Introduction to Linked List Insertion
Insertion is one of the most fundamental operations in a singly linked list. Unlike arrays, linked lists allow dynamic memory allocation, making insertion efficient without shifting elements.
In a singly linked list, insertion can occur at three major positions:
- Insertion at the beginning
- Insertion at the end
- Insertion at a specific position
Each of these cases requires careful pointer manipulation.
Understanding Node Structure
Each node in a singly linked list contains:
- Data
- A pointer to the next node
Structure representation:
Data | Next Pointer
Example:
10 → 20 → 30 → NULL
Insertion at the Beginning
Concept
When inserting at the beginning:
- Create a new node.
- Make its next pointer point to the current head.
- Update head to the new node.
This operation is constant time because no traversal is required.
Time and Space Complexity
Time Complexity: O(1)
Space Complexity: O(1)
C Implementation – Insert at Beginning
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* insertBeginning(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
return newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
// Inserting in reverse order to get output: 10 20 30
head = insertBeginning(head, 30);
head = insertBeginning(head, 20);
head = insertBeginning(head, 10);
printf("Linked List after insertion at beginning: ");
printList(head);
return 0;
}
Output:
Linked List after insertion at beginning: 10 20 30
C++ Implementation – Insert at Beginning
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* insertBeginning(Node* head, int data) {
Node* newNode = new Node(data);
newNode->next = head;
return newNode;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = NULL;
// Insert in reverse order to get 10 20 30
head = insertBeginning(head, 30);
head = insertBeginning(head, 20);
head = insertBeginning(head, 10);
cout << "Linked List after insertion at beginning: ";
printList(head);
return 0;
}Output:
Linked List after insertion at beginning: 10 20 30
Java Implementation – Insert at Beginning
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node insertBeginning(Node head, int data) {
Node newNode = new Node(data);
newNode.next = head;
return newNode;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
head = insertBeginning(head, 30);
head = insertBeginning(head, 20);
head = insertBeginning(head, 10);
System.out.print("Linked List after insertion at beginning: ");
printList(head);
}
}
Output:
Linked List after insertion at beginning: 10 20 30
Python Implementation – Insert at Beginning
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
head = None
head = insert_beginning(head, 30)
head = insert_beginning(head, 20)
head = insert_beginning(head, 10)
print("Linked List after insertion at beginning:", end=" ")
print_list(head)
Output:
Linked List after insertion at beginning: 10 20 30
Insertion at the End of a Singly Linked List
Concept
When inserting at the end:
- Create a new node.
- If the list is empty, the new node becomes the head.
- Otherwise, traverse the list until the last node.
- Set the last node’s next pointer to the new node.
Unlike insertion at the beginning, this operation requires traversal.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation – Insert at End
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* insertEnd(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
// If list is empty
if (head == NULL) {
return newNode;
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
head = insertEnd(head, 10);
head = insertEnd(head, 20);
head = insertEnd(head, 30);
printf("Linked List after insertion at end: ");
printList(head);
return 0;
}Output:
Linked List after insertion at end: 10 20 30
C++ Implementation – Insert at End
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* insertEnd(Node* head, int data) {
Node* newNode = new Node(data);
// If list is empty
if (head == NULL)
return newNode;
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = NULL;
// Insert in normal order
head = insertEnd(head, 10);
head = insertEnd(head, 20);
head = insertEnd(head, 30);
cout << "Linked List after insertion at end: ";
printList(head);
return 0;
}
Output:
Linked List after insertion at end: 10 20 30
Java Implementation – Insert at End
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node insertEnd(Node head, int data) {
Node newNode = new Node(data);
if (head == null)
return newNode;
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
head = insertEnd(head, 10);
head = insertEnd(head, 20);
head = insertEnd(head, 30);
System.out.print("Linked List after insertion at end: ");
printList(head);
}
}
Output:
Linked List after insertion at end: 10 20 30
Python Implementation – Insert at End
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_end(head, data):
new_node = Node(data)
if head is None:
return new_node
temp = head
while temp.next:
temp = temp.next
temp.next = new_node
return head
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
head = None
head = insert_end(head, 10)
head = insert_end(head, 20)
head = insert_end(head, 30)
print("Linked List after insertion at end:", end=" ")
print_list(head)
Output:
Linked List after insertion at end: 10 20 30
Insertion at a Specific Position in a Singly Linked List
Concept
To insert at a given position (1-based index):
- If position is 1 → insert at beginning.
- Traverse to position - 1.
- Adjust pointers:
- newNode->next = temp->next
- temp->next = newNode
Important Considerations
- Handle invalid positions.
- Handle empty list.
- Position must not exceed list length + 1.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation – Insert at Position
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* insertAtPosition(struct Node* head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
// Insert at beginning
if (position == 1) {
newNode->next = head;
return newNode;
}
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) {
printf("Invalid position\n");
return head;
}
newNode->next = temp->next;
temp->next = newNode;
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
head = insertAtPosition(head, 10, 1);
head = insertAtPosition(head, 30, 2);
head = insertAtPosition(head, 20, 2);
printf("Linked List after insertion at position: ");
printList(head);
return 0;
}Output:
Linked List after insertion at position: 10 20 30
Continuing the same section with complete implementations and output included.
Insertion at a Specific Position in a Singly Linked List
C++ Implementation – Insert at Position
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* insertAtPosition(Node* head, int data, int position) {
Node* newNode = new Node(data);
if (position == 1) {
newNode->next = head;
return newNode;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Invalid position" << endl;
return head;
}
newNode->next = temp->next;
temp->next = newNode;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = NULL;
head = insertAtPosition(head, 10, 1);
head = insertAtPosition(head, 30, 2);
head = insertAtPosition(head, 20, 2);
cout << "Linked List after insertion at position: ";
printList(head);
return 0;
}Output:
Linked List after insertion at position: 10 20 30
Java Implementation – Insert at Position
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node insertAtPosition(Node head, int data, int position) {
Node newNode = new Node(data);
if (position == 1) {
newNode.next = head;
return newNode;
}
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Invalid position");
return head;
}
newNode.next = temp.next;
temp.next = newNode;
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
head = insertAtPosition(head, 10, 1);
head = insertAtPosition(head, 30, 2);
head = insertAtPosition(head, 20, 2);
System.out.print("Linked List after insertion at position: ");
printList(head);
}
}
Output:
Linked List after insertion at position: 10 20 30
Python Implementation – Insert at Position
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_position(head, data, position):
new_node = Node(data)
if position == 1:
new_node.next = head
return new_node
temp = head
for _ in range(position - 2):
if temp is None:
print("Invalid position")
return head
temp = temp.next
if temp is None:
print("Invalid position")
return head
new_node.next = temp.next
temp.next = new_node
return head
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
head = None
head = insert_at_position(head, 10, 1)
head = insert_at_position(head, 30, 2)
head = insert_at_position(head, 20, 2)
print("Linked List after insertion at position:", end=" ")
print_list(head)
Output:
Linked List after insertion at position: 10 20 30
Next problem in the series:
Deleting a Given Key from a Singly Linked List
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
