Insertion Operations in Singly Linked List (Beginning, End & Specific Position)
Welcome to Part 2 of our Singly Linked List in Java series.
In Part 1, we learned:
- ✅ What is a Linked List?
- ✅ Why Linked Lists are needed
- ✅ Node Structure
- ✅ Creating Nodes
- ✅ Traversing a Linked List
Now it’s time to perform one of the most important operations on a linked list—Insertion.
Unlike arrays, where inserting an element often requires shifting many elements, linked lists make insertion much easier because only the references (links) need to be updated.
In this tutorial, we’ll learn:
- ➕ Insertion at the Beginning
- ➕ Insertion at the End
- ➕ Insertion at a Specific Position
- 💻 Java Programs
- 🧠 Dry Runs
- 📈 Time Complexity Analysis
- 🎯 Interview Questions
Let’s get started!
📚 Table of Contents
- What is Insertion?
- Why is Insertion Easy in Linked Lists?
- Types of Insertion
- Insertion at the Beginning
- Insertion at the End
- Insertion at a Specific Position
- Java Programs
- Dry Runs
- Time Complexity
- Advantages
- Interview Questions
- Conclusion
➕ What is Insertion?
Insertion means adding a new node into the linked list.
For example,
Before insertion
10 → 20 → 30 → NULL
After inserting 40
10 → 20 → 30 → 40 → NULL
A new node has been added to the list.
🤔 Why is Insertion Easy in Linked Lists?
Suppose we have an array:
10 20 30 40
Insert 25.
10 20 25 30 40
To insert 25, we must shift:
- 30
- 40
This takes O(n) time.
Now consider a linked list.
10 → 20 → 30 → 40
Insert 25.
We simply change two links.
No shifting is required.
That’s why linked lists are excellent for insertion operations.
📌 Types of Insertion
There are three common insertion operations.
1️⃣ Insertion at the Beginning
Before
10 → 20 → 30
After
5 → 10 → 20 → 30
2️⃣ Insertion at the End
Before
10 → 20 → 30
After
10 → 20 → 30 → 40
3️⃣ Insertion at a Specific Position
Before
10 → 20 → 40
After inserting 30
10 → 20 → 30 → 40
🚀 Insertion at the Beginning
This is the easiest insertion operation.
Step-by-Step Algorithm
Suppose we have
Head
↓
10 → 20 → 30 → NULL
Insert 5.
Step 1
Create a new node.
5 → NULL
Step 2
Make the new node point to the current head.
5 → 10 → 20 → 30
Step 3
Update head.
Head
↓
5 → 10 → 20 → 30 → NULL
Done!
Only two references changed.
💻 Java Program – Insert at Beginning
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SinglyLinkedList {
Node head = null;
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.insertAtBeginning(30);
list.insertAtBeginning(20);
list.insertAtBeginning(10);
list.display();
}
}
Output
10 -> 20 -> 30 -> NULL
🔍 Dry Run
Initially
Head = NULL
Insert 30
30 → NULL
Insert 20
20 → 30 → NULL
Insert 10
10 → 20 → 30 → NULL
Perfect!
📈 Time Complexity
Only two references are updated.
Therefore,
O(1)
Space Complexity
O(1)
🚀 Insertion at the End
Now we insert a new node at the last position.
Suppose we have
10 → 20 → 30 → NULL
Insert
40
Result
10 → 20 → 30 → 40 → NULL
Algorithm
Step 1
Create new node.
Step 2
Traverse until the last node.
Step 3
Last node’s next becomes the new node.
Step 4
New node points to NULL.
💻 Java Program – Insert at End
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
public class SinglyLinkedList {
Node head = null;
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String args[]) {
SinglyLinkedList list = new SinglyLinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.display();
}
}
Output
10 -> 20 -> 30 -> 40 -> NULL
🔍 Dry Run
Current List
10 → 20 → 30 → NULL
Traverse
10
↓
20
↓
30
30 is the last node.
Change
30.next = 40
Result
10 → 20 → 30 → 40 → NULL
📈 Time Complexity
Traversal is required.
Therefore,
O(n)
Space Complexity
O(1)
🚀 Insertion at a Specific Position
Suppose
10 → 20 → 40 → 50
Insert
30
at Position 3.
Result
10 → 20 → 30 → 40 → 50
Algorithm
- Create new node.
- Traverse until the node before the required position.
- Store the next reference.
- Connect the new node.
- Restore the remaining link.
Visual Explanation
Current
10 → 20 → 40 → 50
New node
30
Step 1
30.next = 40
Step 2
20.next = 30
Result
10 → 20 → 30 → 40 → 50
💻 Java Program – Insert at a Specific Position
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
public class SinglyLinkedList {
Node head;
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
}
public void insertAtPosition(int position, int data) {
Node newNode = new Node(data);
if (position == 1) {
newNode.next = head;
head = newNode;
return;
}
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;
}
newNode.next = temp.next;
temp.next = newNode;
}
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String args[]) {
SinglyLinkedList list = new SinglyLinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(40);
list.insertAtEnd(50);
list.insertAtPosition(3,30);
list.display();
}
}
Output
10 -> 20 -> 30 -> 40 -> 50 -> NULL
🔍 Dry Run
Current
10 → 20 → 40 → 50
Need to insert
30
Move to Position 2.
Current node
20
Save
40
Update
30.next = 40
Update
20.next = 30
Final
10 → 20 → 30 → 40 → 50
📈 Time Complexity
Insertion at Beginning
O(1)
Insertion at End
O(n)
Insertion at Position
O(n)
Space Complexity
O(1)
📊 Comparison of Insertion Operations
| Operation | Time Complexity |
|---|---|
| Insert at Beginning | O(1) |
| Insert at End | O(n) |
| Insert at Position | O(n) |
🌟 Advantages of Linked List Insertion
✅ No shifting of elements
✅ Dynamic memory allocation
✅ Efficient insertion at the beginning
✅ Easy to expand the list
❓ Frequently Asked Questions
Q1. Which insertion operation is the fastest?
Insertion at the beginning, because only two references are updated.
Q2. Why is insertion at the end O(n)?
Because we must traverse the list to reach the last node (unless a tail pointer is maintained).
Q3. Why is insertion easier in a linked list than in an array?
Because linked lists only require updating references, whereas arrays require shifting elements.
Q4. Can we insert at any position?
Yes. As long as the position is valid and we can reach the previous node.
Q5. What happens if the position is invalid?
The insertion should be rejected, and an appropriate error message should be displayed.
🎯 Key Takeaways
- ➕ A new node can be inserted at the beginning, end, or any valid position.
- 🚀 Insertion at the beginning is the fastest operation with O(1) time complexity.
- 🚶 Insertion at the end and at a specific position requires traversal, resulting in O(n) time complexity.
- 🔗 Insertion works by updating node references instead of shifting elements.
- 💾 Linked lists provide a flexible and dynamic way to manage data, especially when frequent insertions are required.
🎉 Conclusion
Insertion is one of the strongest advantages of a Singly Linked List over arrays. Since linked lists store data as interconnected nodes rather than contiguous memory locations, adding new elements is much simpler and more efficient in many scenarios.
In this part, you learned how to insert nodes at the beginning, end, and a specific position, along with complete Java implementations, dry runs, and complexity analysis.
👉 In Part 3, we’ll explore the opposite operation—Deletion in a Singly Linked List. You’ll learn how to:
- ❌ Delete the first node
- ❌ Delete the last node
- ❌ Delete a node at a specific position
- ❌ Delete a node by value
- 🧪 Understand each operation through detailed Java programs, diagrams, and dry runs.
