Reading — step 1 of 5
Read
~1 min readDelete & Iterate
Delete Algorithm
Mirror of insert:
- Find predecessors at each level.
- If the next node's key matches, splice it OUT at every level it participates in.
- 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…