Insert and delete

Changing a linked list means changing a few next references. Each change is quick. The hard part is doing the changes in the right order, so that no part of the list is lost on the way.

Insert after a node

Say cur refers to a node, and you want a new node just after it. Two references must change: the new node must point to whatever came after cur, and cur must point to the new node.

The order matters. cur.next is the only reference to the rest of the list. If you change it first, the rest is gone. So first let the new node take a copy of that reference, then change cur.next. Step through both orders:

node = Node(7)
node.next = cur.next     # 1: new node points on
cur.next = node          # 2: then link it in

Neither order needs a loop, so insertion after a node you hold is O(1), however long the list is. Finding that node in the first place may take a walk, which is O(n).

Delete after a node

To delete a node, make the node before it skip over it: cur.next = cur.next.next. The deleted node is still in memory for a moment, but nothing refers to it. Python counts references to every object, and when the count reaches zero it frees the object. You never free a node yourself.

Note that you need the node before the one you delete. In a one-way list, a node does not know what comes before it. This is why a walk that deletes usually looks one node ahead:

cur = head
while cur.next is not None:
    if cur.next.value == x:
        cur.next = cur.next.next    # delete; do not move on yet
    else:
        cur = cur.next

After a delete, cur stays where it is, because its new next has not been checked yet. Moving on would skip it. If two nodes in a row hold x, that skip would leave the second one in the list.

The head is a special case

The code above never checks the head itself, because the head has no node before it. Deleting the head means changing the name head, not a next reference:

while head is not None and head.value == x:
    head = head.next
# ...then the loop above, starting at the new head

This works, but it is two pieces of code for one job. Inserting at the front has the same problem. Special cases like this are where most linked list bugs come from.

A dummy node removes it

The fix is to put an extra node in front of the head. It holds no real value. It is called a dummy node (or a sentinel). Now every real node, the head included, has a node before it, so one loop handles all of them. The walk starts at the dummy:

dummy = Node(None, head)    # holds no real value
cur = dummy                 # start one node before the head

Then run the delete loop from above. At the end, return dummy.next, not the old head: if the old head was deleted, dummy.next is the new one. The dummy node costs one extra object, and the head is no longer a special case. Lesson 6 uses a dummy node again, to build a new list.

Now try LINK-P1, Remove a station.