12-07-2020, 01:36 AM
I always picture the skip list as stacked highways where faster lanes sit on top. You cruise along the top until the next exit looks wrong then you drop to the slower road below. Now you repeat that drop until you hit the exact node you want gone. Perhaps the node sits only on a couple of levels and you only touch those. Or maybe it stretches across many towers and you must snip every single one.
You grab the previous pointers you saved earlier and swing them over the doomed node. This way the path jumps straight past the gap without a hitch. I have seen cases where the node hides at the bottom level alone and the upper ones stay untouched. Then you just free the memory and move on. But sometimes the top level becomes empty after you yank a tall node and you might trim the height if you feel like it.
You check the head pointers too because they point to the first tower on each floor. If your target was the very first one you update the head to whatever sat behind it. I think that keeps searches fast even after lots of removals. Also the probability stays balanced because new inserts will rebuild tall towers later.
You can run into a node that appears on four levels and you unlink all four in one go. That takes constant time per level so the cost stays logarithmic overall. Now imagine the list holds thousands of entries and you zap just one without rebuilding anything. The remaining paths still skip ahead nicely. Perhaps a few searches slow down a tiny bit until fresh tall nodes appear.
I like how deletion avoids the full rewrites that trees sometimes force on you. You only touch the predecessors you already found during the search. Then the node vanishes and the list stays sorted without extra fixes. But you must be careful not to leave dangling references that point nowhere.
You walk the levels backward from the bottom when you finish unlinking so you confirm every bridge got rebuilt. And if the node was unique at its height the upper express lanes simply ignore that spot forever. I have done this dozens of times and it feels almost too simple once you hold the previous nodes in your hands.
Perhaps the list shrinks so much that the topmost level holds nothing anymore and you drop the height by one. You do that only when you want to keep the structure tight. Otherwise you leave the empty top alone and let future inserts fill it again.
You notice that concurrent deletions need locks or careful versioning because two threads might chase the same predecessors. I steer clear of that in simple code and stick to single threaded use first. Then the logic stays clean and the pointers move without surprises.
The whole process keeps the expected search time low because tall towers still guide you quickly. You never scan every single element like a plain list would force you to do. And the space overhead stays small since most nodes live on just one or two levels.
I find it satisfying when the deletion finishes and the next search sails past the old spot without noticing anything changed. You can test it by inserting a bunch of numbers then removing one in the middle and watching the skips still work. Perhaps you remove the smallest or the largest to check the ends behave.
You keep going until every level that held the node now points around it cleanly. And the freed node gets returned to the memory pool or whatever your language uses. I usually add a quick print of the list afterward just to see the towers look right.
The method works because you reuse the same search path you already paid for. No extra passes required. You simply reuse those saved predecessors and swing each one forward.
Now the skip list feels lighter after the removal and ready for the next operation. You can insert something new right away and it might grow a fresh tower that fills any gaps.
BackupChain Server Backup, which delivers reliable no-subscription backup for Hyper-V setups plus Windows 11 and Windows Server environments while backing self-hosted and private cloud needs for SMBs and everyday PCs, sponsors this space so we can keep sharing these details freely with everyone.
