Insertion in Linked List (DSA)

🚀 Introduction

Insertion is a fundamental operation in a Linked List, where a new node is added at a specific position.

👉 Unlike arrays, linked lists do not require shifting elements, making insertion efficient.

---

🔹 What is a Node?

Each node in a linked list contains:

• Data → Value of the node
• Next Pointer → Address of next node

---

🔹 Types of Insertion

There are 3 main types:

1. Insert at Beginning
2. Insert at End
3. Insert at a Specific Position

---

🔹 1. Insert at Beginning

💡 Algorithm

1. Create a new node
2. Set newNode.next = head
3. Update head = newNode

---

🧾 Example

Before:

10 → 20 → 30 → NULL

After inserting 5:

5 → 10 → 20 → 30 → NULL

---

⚡ Complexity

👉 O(1) (Fastest insertion)

---

🔹 2. Insert at End

💡 Algorithm

1. Create a new node
2. Traverse to last node
3. Set last.next = newNode

---

🧾 Example

Before:

10 → 20 → NULL

After inserting 30:

10 → 20 → 30 → NULL

---

⚡ Complexity

👉 O(n) (Traversal required)

---

🔹 3. Insert at Specific Position

💡 Algorithm

1. Traverse to position – 1
2. Set newNode.next = temp.next
3. Set temp.next = newNode

---

🧾 Example

Before:

10 → 20 → 30 → NULL

Insert 25 at position 3:

10 → 20 → 25 → 30 → NULL

---

⚡ Complexity

👉 O(n)

---

⚙️ Pseudocode

function insertAtPosition(head, data, pos):
    newNode = createNode(data)    if pos == 1:
        newNode.next = head
        head = newNode
        return head    temp = head
    for i = 1 to pos-1:
        temp = temp.next    newNode.next = temp.next
    temp.next = newNode    return head

---

🎯 Key Points

✅ No shifting of elements (unlike arrays)
✅ Efficient insertion using pointers
✅ Requires traversal for middle/end insertion

---

🧠 Interview Tips

👉 Always handle edge cases:

• Empty list
• Position = 1
• Position out of bounds

👉 Common variations:

• Insert in sorted list
• Insert in circular linked list
• Insert using recursion

---

⚡ Time Complexity Summary

Type	Complexity
Beginning	O(1)
End	O(n)
Specific Position	O(n)

---

🏁 Conclusion

Insertion is one of the most important operations in Linked Lists.

👉 Mastering it helps you:

• Understand pointer manipulation
• Solve complex linked list problems
• Perform well in coding interviews