Базовые структуры данных. Деки, списки и хеш-таблицы, страница 2

Всё земное конечно. Поэтому у каждого списка есть свой предел. Даже два предела. Обычно у списка различают элементы голова и хвост. Голова списка – элемент, которому не предшествует ни один другой элемент, т. е. ссылка на предыдущий элемент у головы списка равна ничему (скажем, нулю). Хвост – та же голова, только наоборот. Это верно, если список не является кольцевым

Кольцевым называется список, у которого за хвостом следует голова, а перед головой идёт хвост. Иногда удобней использовать именно такие списки. Тогда голову (или хвост) отмечают каким-либо флажком, и от любого элемента к любому можно прийти, двигаясь только вперёд (или только назад).

2.2  Операции над списком

Над списком обычно выполняются следующие основные операции:

§  insert(L, x) – добавить элемент x в список L.

§  insertAfter(L, x, a) – добавить элемент x в список L после элемента, на который указывает a.

§  delete(L, a) – удалить из списка L элемент, на который указывает a.

§  find(L, x) – найти элемент x в списке L и вернуть указатель на этот элемент.

Естественно, в операциях добавления и удаления можно оперировать индексами элементов, но это не принципиально.

То есть, в наше распоряжение отданы операции добавления, удаления и поиска элементов. При этом можно оперировать всеми элементами, а не только крайними, как в случае с деком.

2.3  Обсуждение эффективности операций

Начнём с операции вставки. Если элемент нужно просто вставить в список, его вставляют перед головой или после хвоста списка. Поскольку доступ к голове или хвосту списка прост, время выполнения такой операции – Θ(1).

Операция вставки после определённого элемента также не составляет труда. В случае, если нам дана ссылка на тот элемент, после которого надо вставлять, она также выполняется за время Θ(1) (создаётся новый элемент, у которого ссылка на следующий элемент равна соответствующей ссылке у элемента, после которого вставляем, а ссылка на предыдущий элемент указывает на этот элемент). В случае, если дан только индекс i элемента, после которого должна быть осуществлена вставка, нам надо пройти i - 1 элементов, прежде чем мы вставим нужный. Поскольку число i изменяется от 1 до n (где n – длина списка), мы получаем, что время такой вставки уже равно O(n).

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

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

2.4  Замечания

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

3  Хеш-таблицы

Мы все знакомы с массивами. Массив можно представить как набор записей, которые адресуются по ключу – индексу массива. Такой метод адресации элементов называется прямой адресацией. И он довольно хорошо работает в случае, если ключи лежат в разумном диапазоне. А если нет?