Skip lists

As we discussed in the previous chapter, when studying data structures, it’s important to evaluate their performance in three key operations: insertion, deletion, and search. Arrays excel in searching, particularly when the data is already sorted, thanks to their direct (or random) access capabilities, which allow for sublinear time complexity. However, due to their static nature, arrays can present challenges when it comes to inserting new data or deleting existing data. On the other hand, linked lists exhibit the opposite behavior. Their dynamic allocation allows for easy insertion and deletion, but the lack of direct access means that searching, even in sorted data, becomes a sequential process with linear time complexity.

This question then arises: Is it possible to combine the benefits of both arrays and linked lists? In other words, can we achieve faster-than-sequential access, similar to arrays, while also enjoying the dynamic memory allocation of linked...