Lecture Notes: Insert at Position Method in Singly Linked List

Overview

• Method Name: insertAtPosition
• Purpose: Insert a new node at a specific position in a singly linked list.
  • Takes two parameters: data and position

Initial Setup

• 0-indexed positions: The method operates using 0-based indexing.
• Example: For a list with 6 nodes (size 6):
  • Position 0: first node, Position 1: second node, ..., Position 5: sixth node

Validation Checks

1. Position must be non-negative:
   • If position < 0, throw IllegalArgumentException: "Invalid position, cannot be negative."
2. Position must not exceed list size:
   • If position > size, throw IllegalArgumentException: "Invalid position, exceeds list size."
   • Note: Position equal to list size is valid.

Inserting the Node

1. Creating the new node:
   • Store the data in the new node.
2. If position is 0:
   • Insert at beginning.
     • Assign new node's next to current head.
     • Update head to new node.
     • Increase the list size.
     • This handles the case where insertion happens at the start of the list.
3. If position is valid and not 0:
   • Traverse to the node just before the desired position.
   • Use a temporary pointer current starting from head and a counter to move to the desired node.
   • Loop until counter < position - 1.
     • Move current to next node.
     • Increment counter.
   • Update the new node's next to current.next.
   • Update current's next to the new node.
   • Increase the list size.

Examples

1. Insert at Position 0:
   • List is empty, insert node with data 10 at position 0.
   • List: 10, Size: 1
2. Insert at Position 1:
   • Insert node with data 12 at position 1 (after the node with data 10).
   • List: 10 -> 12, Size: 2
3. Insert at Position 2:
   • Insert node with data 15 at position 2 (after the node with data 12).
   • List: 10 -> 12 -> 15, Size: 3
4. Insert at a Specific Position:
   • Insert node with data 25 at position 2 (between nodes with data 12 and 15).
   • List: 10 -> 12 -> 25 -> 15, Size: 4

Edge Cases

• Negative Position: Throw exception for negative index.
• Position Greater than Size: Throw exception for index beyond list size.

Conclusion

• The method ensures nodes are inserted at correct positions with index validation and proper pointer adjustments.
• Summary of steps: Validate index, create node, traverse to position, insert node, adjust pointers, update size.

---

End of Lecture Notes