logo
УП_САОД_2003

Слоеные списки

Слоеные (skip) или разделенные списки – это связные списки, которые позволяют перескакивать через некоторое количество элементов. Это позволяет преодолеть ограничения последовательного поиска, являющейся основной причиной низкой эффективности поиска в линейных списках. В то же время вставка и удаление остаются сравнительно эффективными.

Идея, лежащая в основе слоеных списков, очень напоминает метод, используемый при поиске имен в адресной книжке. Чтобы найти имя, ищется страница, помеченная буквой, с которой начинается имя, а затем поиск осуществляется в пределах этой страницы.

В отличие от элементов обычных линейных списков, элементы этих списков имеют дополнительный указатель. Все элементы списка группируются по определенному признаку, и первый элемент каждой группы содержит указатель на первый элемент следующей группы. Если следующая группа отсутствует или элемент не является первым в группе, то этот дополнительный указатель принимает значение nil.

Эта простая идея может быть расширена – можно добавлять нужное число дополнительных указателей, группируя группы элементов и т.д. на нужном количестве уровней.

Если реализован только один уровень, то это, фактически, обычный список и время поиска пропорционально O(n). Однако если имеется достаточное число уровней, то разделенный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска, как будет показано ниже, пропорционально O(log n).

Рисунок 12. Слоеный список и его организация

      1. Графы

        1.