Функция initList вызывается в самом начале. Она отводит память под заголовок списка и инициализирует его поля. Признаком того, что список пуст, Функция insertNode создает новый узел и вставляет его в список. Конечно, insertNode сначала отыскивает место в списке, куда узел должен быть вставлен. В массиве update функция учитывает встретившиеся ссылки на узлы верхних уровней. Эта информация в дальнейшем используется для корректной установки ссылок нового узла. Для этого узла, с помощью генератора случайных чисел, определяется значение newLevel, после чего отводится память для узла. Ссылки вперед устанавливаются по информации, содержащей в массиве update. Функция deleteNode удаляет узлы из списка и освобождает занимаемую ими память. Она реализована аналогично функции findNode и так же ищет в списке удаляемый узел.
// Коды для разделенных списков
typedef int T; /* type of item to be sorted */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
/*
* levels range from (0 .. MAXLEVEL)
*/
#define MAXLEVEL 15
typedef struct Node_ {
T data; /* user's data */
struct Node_ *forward[1]; /* skip list forward pointer */
} Node;
typedef struct {
Node *hdr; /* list Header */
int listLevel; /* current level of list */
} SkipList;
SkipList list; /* skip list information */
#define NIL list.hdr
Node *insertNode(T data) {
int i, newLevel;
Node *update[MAXLEVEL+1];
Node *x;
/***********************************************
* allocate node for data and insert in list *
***********************************************/
/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x != NIL && compEQ(x->data, data)) return(x);
/* determine level */
newLevel = 0;
while (rand() < RAND_MAX/2) newLevel++;
if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}
/* make new node */
if ((x = malloc(sizeof(Node) +
newLevel*sizeof(Node *))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
/* update forward links */
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return(x);
}
void deleteNode(T data) {
int i;
Node *update[MAXLEVEL+1], *x;
/*******************************************
* delete node containing data from list *
*******************************************/
/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NIL || !compEQ(x->data, data)) return;
/* adjust forward pointers */
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
free (x);
/* adjust header level */
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == NIL))
list.listLevel--;
}
Node *findNode(T data) {
int i;
Node *x = list.hdr;
/*******************************
* find node containing data *
*******************************/
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->data, data)) return (x);
return(0);
}
void initList() {
int i;
/**************************
* initialize skip list *
**************************/
if ((list.hdr = malloc(sizeof(Node) + MAXLEVEL*sizeof(Node *))) == 0) {
printf ("insufficient memory (initList)\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list.hdr->forward[i] = NIL;
list.listLevel = 0;
}