Составители:
50
Добавление элемента здесь сложнее. Добавление элемента, принад-
лежащего только одному из списков, осуществляется аналогично до-
бавлению в линейный список, за исключением того, что поля указате-
лей, относящиеся к другим спискам, устанавливаются в nil. При до-
бавлении элемента, принадлежащего сразу нескольким спискам, необ-
ходимо аккуратно осуществлять определение значений соответствую-
щих указателей. Алгоритм выполнения такой операции сильно зависит
от количества списков и места вставки нового элемента.
1.3.2. Слоеные списки
Слоеные (skip), или разделенные, списки – это связные списки, ко-
торые позволяют перескакивать через некоторое количество элементов
(рис. 12). Это позволяет преодолеть ограничения последовательного по-
иска, являющейся основной причиной низкой эффективности поиска в
линейных списках. В то же время вставка и удаление остаются сравни-
тельно эффективными.
Идея, лежащая в основе слоеных списков, очень напоминает метод,
используемый при поиске имен в адресной книжке. Чтобы найти имя,
ищут страницу, помеченную буквой, с которой начинается имя, а затем
поиск осуществляют в пределах этой страницы.
В отличие от элементов обычных линейных списков, элементы этих
списков имеют дополнительный указатель. Все элементы списка груп-
пируются по определенному признаку, и первый элемент каждой груп-
пы содержит указатель на первый элемент следующей группы. Если
Алексей
Указатель
на линейный
список
Андрей Борис Павел
nil
Петр
Борис
nil
Павел
Указатель
на слоеный
список
Линейный список
nil
Алексей
nil
Андрей
nil
nil
Петр
Слоеный список
Александр
Александр
Рис. 12. Слоеный список и его организация
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
