Skip to content
Delete Algorithm
step 1/5

Reading — step 1 of 5

Read

~1 min readDelete & 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.

Discussion

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

Sign in to post a comment or reply.

Loading…