Linked List: Insertion

Task: Insert 25 between 20 and 30

class Node { int value; Node next; } Node n = head;              // start at the headwhile (n != null) {         // walk to the end    n = n.next;             // follow one pointer} n.next = prev.next;         // insert: point it onprev.next = n;              // then point prev at itprev.next = prev.next.next; // delete: step over one

What you are watching

Inserting into a linked list moves nothing. The new node is allocated wherever there is room - drawn below the row, because its position in memory has nothing to do with its position in the list - and two pointers are rewritten: the new node points at 30, then 20 points at the new node. The order of those two writes is not optional.