Visualizer › Linked List
Linked List Insertion
Inserts a new node at a position: walk to the node before it, point the new node to the next one, then link the previous node to the new node.
How it works
- Inserting at the head is O(1).
- Order matters: set new.next first, then temp.next = new.
- No shifting of elements like in an array.
Complexity
- Best time: O(1)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(1)
Code (Python)
def insert_at(head, value, pos):
node = Node(value)
if pos == 0:
node.next = head
return node
temp = head
for _ in range(pos - 1):
temp = temp.next
node.next = temp.next
temp.next = node
return headPractise: Linked List problems