4.3 : An Efficient Random-Access

A implements the interface using a skiplist structure. In a , contains the elements of the list in the order in which they appear in the list. As in a , elements can be added, removed, and accessed in time.

For this to be possible, we need a way to follow the search path for the th element in . The easiest way to do this is to define the notion of the length of an edge in some list, . We define the length of every edge in as 1. The length of an edge, , in , , is defined as the sum of the lengths of the edges below in . Equivalently, the length of is the number of edges in below . See Figure 4.5 for an example of a skiplist with the lengths of its edges shown. Since the edges of skiplists are stored in arrays, the lengths can be stored the same way:

struct Node { T x; int height; // length of next int *length; Node **next; };

The useful property of this definition of length is that, if we are currently at a node that is at position in and we follow an edge of length , then we move to a node whose position, in , is . In this way, while following a search path, we can keep track of the position, , of the current node in . When at a node, , in , we go right if plus the length of the edge is less than . Otherwise, we go down into .

Node* findPred(int i) { Node *u = sentinel; int r = h; int j = -1; // the index of the current node in list 0 while (r >= 0) { while (u->next[r] != NULL && j + u->length[r] < i) { j += u->length[r]; u = u->next[r]; } r--; } return u; }

T get(int i) { return findPred(i)->next[0]->x; } T set(int i, T x) { Node *u = findPred(i)->next[0]; T y = u->x; u->x = x; return y; }

Since the hardest part of the operations and is finding the th node in , these operations run in time.

Adding an element to a at a position, , is fairly simple. Unlike in a , we are sure that a new node will actually be added, so we can do the addition at the same time as we search for the new node's location. We first pick the height, , of the newly inserted node, , and then follow the search path for . Any time the search path moves down from with , we splice into . The only extra care needed is to ensure that the lengths of edges are updated properly. See Figure 4.6.

Note that, each time the search path goes down at a node, , in , the length of the edge increases by one, since we are adding an element below that edge at position . Splicing the node between two nodes, and , works as shown in Figure 4.7. While following the search path we are already keeping track of the position, , of in . Therefore, we know that the length of the edge from to is . We can also deduce the length of the edge from to from the length, , of the edge from to . Therefore, we can splice in and update the lengths of the edges in constant time.

This sounds more complicated than it is, for the code is actually quite simple:

void add(int i, T x) { Node *w = newNode(x, pickHeight()); if (w->height > h) h = w->height; add(i, w); }

Node* add(int i, Node *w) { Node *u = sentinel; int k = w->height; int r = h; int j = -1; // index of u while (r >= 0) { while (u->next[r] != NULL && j + u->length[r] < i) { j += u->length[r]; u = u->next[r]; } u->length[r]++; // to account for new node in list 0 if (r <= k) { w->next[r] = u->next[r]; u->next[r] = w; w->length[r] = u->length[r] - (i - j); u->length[r] = i - j; } r--; } n++; return u; }

By now, the implementation of the operation in a should be obvious. We follow the search path for the node at position . Each time the search path takes a step down from a node, , at level we decrement the length of the edge leaving at that level. We also check if is the element of rank and, if so, splice it out of the list at that level. An example is shown in Figure 4.8.

T remove(int i) { T x = null; Node *u = sentinel, *del; int r = h; int j = -1; // index of node u while (r >= 0) { while (u->next[r] != NULL && j + u->length[r] < i) { j += u->length[r]; u = u->next[r]; } u->length[r]--; // for the node we are removing if (j + u->length[r] + 1 == i && u->next[r] != NULL) { x = u->next[r]->x; u->length[r] += u->next[r]->length[r]; del = u->next[r]; u->next[r] = u->next[r]->next[r]; if (u == sentinel && u->next[r] == NULL) h--; } r--; } deleteNode(del); n--; return x; }

The following theorem summarizes the performance of the data structure:

opendatastructures.org