Need info about skip-lists

Question

In a skip-list such as this one:

Does the element 4 have access to itself in the second and third list? The reason I ask is because I'm trying to figure out how to implement the delete operation for a skip list. Thank you

Answer 1

Yes, in a skip list, each of the pointers has some way of getting you to the actual entries. Typically, you'd implement this by having each of the pointers point not to a linked list cell in some entry, but to the entry itself. As long as you remember the current depth that you're at, you can then continue along the linked list by indexing into the array of pointers stored at the next cell.

For example:

struct Cell {
    Cell* pointers[]; // Each points to the root of a new Cell
    Type data;
};

Hope this helps!