концами»), позволяет добавлять и удалять элементы с обоих концов. Реализуйте дек на базе массива таким образом, чтобы операции добавления и удаления элемента с каждого из концов занимали время 0(1).

11.1-6 Объясните, как можно реализовать очередь на базе двух стеков. Каково время работы операций Enqueue и Dequeue при такой реализации?

11.1-7 Объясните, как реализовать стек на базе двух очередей. Каково время работы стековых операций?

11.2. Связанные списки

В связанном списке (или просто списке; по-английски linked list) элементы линейно упорядочены, но порядок определяется не номерами, как в массиве, а указателями, входящими в состав элементов списка. Списки являются удобным способом реализации динамических множеств, позволяющим реализовать все операции, перечисленные во введении к этой части (хотя и не всегда эффективно).

Если каждый стоящий в очереди запомнит, кто за ним стоит, после чего все в беспорядке рассядутся на лавочке, получится односторонне связанный список; если он запомнит ещё и впереди стоящего, будет двусторонне связанный список.

Другими словами, как показано на рис. 11.3, элемент двусторонне связанного списка (doubly linked list) - это запись, содержащая три поля: key (ключ) и два указателя next (следующий) и prev (от previous - предыдущий). Помимо этого, элементы списка могут содержать дополнительные данные. Если х - элемент списка, то next[x] указывает на следующий элемент списка, a prev[x] - на предшествующий. Если prev[x] = nil, то у элемента х нет предшествующего: это голова (head) списка. Если next[x] = nil, то ж - последний элемент списка или, как говорят, его хвост (tail).

Прежде чем двигаться по указателям, надо знать хотя бы один элемент списка; мы предполагаем, что для списка L известен указатель head[L] на его голову. Если head[L] = nil, то список пуст.

В различных ситуациях используются разные виды списков. В односторонне связанном (singly linked) списке отсутствуют поля prev. В упорядоченном (sorted) списке элементы расположены в порядке возрастания ключей, так что у головы списка ключ наименьший, а у хвоста списка - наибольший, в отличие от неупорядоченного (unsorted) списка. В кольцевом списке (circular list) поле prev головы списка указывает на хвост списка, а поле next хвоста списка указывает на голову списка.

Если иное не оговорено особо, под списком мы будем понимать

Рис. 11.3 (а) Двусторонне связанный список Г содержит числа 1,4,9, 16. Каждый элемент списка - это запись с полями для ключа и указателей на предыдущий и последующий элементы (эти указатели изображены стрелками). В поле next у хвоста списка и в поле prev у головы списка находится указатель nil (косая черта на рисунке); head[L\ указывает на голову списка, (б) В результате выполнения операции List-Insert(L, х), где кеу[х] = 25, в списке появился новый элемент с ключом 25; он стал новой головой списка, а его поле next указывает на бывшую голову - элемент с ключом 9. (в) Вслед за этим была выполнена операция List-Delete(L, х), где х - указатель на элемент с ключом 4.

неупорядоченный двусторонне связанный список. Поиск в списке

Процедура List-Search(L, к) находит в списке L (с помощью простого линейного поиска) первый элемент, имеющий ключ к. Точнее говоря, она возвращает указатель на этот элемент, или nil, если элемента с таким ключом в списке нет. Если, например, L - список рис. 11.3а, то вызов List-Search(L, 4) вернёт указатель на третий элемент списка, а вызов List-Search(L, 7) вернёт nil.

List-Search(L, к)

1х <- head[L]

2while х ф nil and key[x] ф к

3do x <- next[x]

4return x

Поиск в списке из п элементов требует в худшем случае (когда приходится просматривать весь список) О(га) операций.

Добавление элемента в список

Процедура List-Insert добавляет элемент х к списку L, помещая его в голову списка (рис. 11.36).

List-Insert(L, ж)

1next[x] <- head[L]

2if head[L] ф nil

3then prev[head[L]] <- x

4head[L] <- x

5ргеи[ж] <- nil

Процедура List-Insert выполняется за время 0(1) (не зависящее от длины списка).

Удаление элемента из списка

Процедура List-Delete удаляет элемент х из списка L, направляя указатели «в обход» этого элемента. При этом в качестве аргумента ей передаётся указатель на х. Если задан ключ элемента ж, то перед удалением надо найти его указатель с помощью процедуры List-Search.

List-Delete(L, ж)

1if prev[x] ф nil

2then next[prev[x]] <- next[x]

3else head[L] <- next[x]

4if next[x] ф nil

5then prev[next[x]] <- prev[x]

Удаление элемента из списка проиллюстрировано на рис. 11.Зв. Процедура List-Delete работает за время 0(1); однако для удаления элемента с заданным ключом его надо сначала найти, что потребует времени 0(га).

Фиктивные элементы

Если забыть об особых ситуациях на концах списка, процедуру List-Delete можно записать совсем просто:

List-Delete(L, ж)

1next[prev[x]] <- next[x]

2prev[next[x]] <- prev[x]

Такие упрощения станут законными, если добавить к списку L фиктивный элемент nil[L], который будет иметь поля next и prev наравне с прочими элементами списка. Этот элемент (называемый sentinel - часовой) не позволит нам выйти за пределы списка. Указатель на него играет роль значения nil. Замкнём список в кольцо: в поля next[nil[L]] и preu[m7[L]] запишем указатели на голову и хвост списка соответственно, а в поля prev у головы списка и next