AlgoVerse

Sorted linked list (insert, search, delete)

Insert items one by one into their places in a sorted linked list, then search for one and delete it; only pointers change, no item moves.

A linked list is a chain of nodes, each holding a value and a pointer to the next node. Unlike an array, inserting or deleting in the middle moves no items: only two pointers change.

Read the full explanation ↓
Input:
n=5 · target=23PDF export

42, 17, 88, 23 and 5 are inserted into the sorted list, then 23 is found and removed.

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  7. def sorted_list(items, target):
  8. # Insert every item into a sorted linked list, then search for target and delete it.
  9. head = None
  10. for x in items:
  11. node = Node(x)
  12. if head is None or x <= head.val:
  13. node.next = head
  14. head = node
  15. continue
  16. cur = head
  17. while cur.next is not None and cur.next.val < x:
  18. cur = cur.next
  19. node.next = cur.next
  20. cur.next = node
  21. prev, cur, node = None, head, None
  22. while cur is not None and cur.val < target:
  23. prev, cur = cur, cur.next
  24. if cur is None or cur.val != target:
  25. return False
  26. if prev is None:
  27. head = cur.next
  28. else:
  29. prev.next = cur.next
  30. return True

Invariant: The list from head is always sorted, and every node appears in it exactly once.

Start

headnull

Local variables

target23

Orange = changed in this step

items list

421788235

Call stack

  1. sorted_list()line 7
Step 1 of 62
Black = insert_front, insert_after · Orange = key stepinsert_front: 0/3 · walk: 0/1 · insert_after: 0/2 · search: 0/2 · unlink: 0/1
    Explanation

    The idea

    A linked list is a chain of nodes, each holding a value and a pointer to the next node. Unlike an array, inserting or deleting in the middle moves no items: only two pointers change.

    Operations on a sorted list

    • Insert: walk from the head until the next value is not smaller than x; link x in between cur and its next.
    • Search: walk until a value not smaller than the target; since the list is sorted, you can stop before the end.
    • Delete: link the node before (prev) straight to the node after the one removed.

    Cost

    Finding the place costs O(n) (there is no random access), but the insert or delete itself is O(1).

    What to watch in the trace

    • The list is drawn from head; the pointer names (cur, prev, node) appear under the nodes.