Skip to content
Lesson 5 of 8

Step 1 of 5 · Reading · ~1 min

Read

Delete & Iterate

Delete Algorithm

Mirror of insert:

  1. Find predecessors at each level.
  2. If the next node's key matches, splice it OUT at every level it participates in.
  3. Decrease the list's tracked max level if the topmost level became empty.
python

Same complexity as insert: O(log n).

For concurrent skip lists, deletion uses the standard "mark for delete then unlink" pattern. The marker bit prevents inserts past a deleted node from observing inconsistent state.

Up nextRange Queries & IterationDelete & Iterate

Discussion

Ask a question, share an insight, or help someone who’s stuck.

Sign in to post a comment or reply.

Loading…