I finished talking about space efficient linked lists.
Here is my implementation: selist.cpp. A few notes:
In the code I have some comments about some of the specific choices I made in converting the psueudocode to C++.
I use a variable block_array_size instead of b+1 which the pseudocode uses. Also, instead of storing this in each block, I store it once in the entire List and then pass it to each block method.
In the code, I fix the block_array_size to 16. In a real implementation, we should keep the block_array_size around \(O(\sqrt{n})\). To do so, the add and remove methods would check if block_array_size is far away from \(O(\sqrt{n})\) and if so would allocate an entire new data structure with a new block_array_size and copy all elements from the old structure to the new one (similar to how the ArrayStack copied everything into a new array). How often should this occur? That is, how far away can block_array_size get from \(\sqrt{n}\) before a recreate becomes neccissary? Well, the answer is exactly as soon as you can get away with amortizing the cost. We want this recreate to happen only once
To my selist.cpp implementation, put in the gather and remove methods. You should be able to directly translate them from the pseudocode to C++. I have already implemented remove_node, so inside gather and remove you can just call the remove_node method on the block. Remember that b+1 is block_array_size, so during the translation of the pseudocode you need to change b.