Основы реализации списковых структур

Структуры данных типа «линейный список»

Линейный список — это набор связанных однотипных элементов, в котором каждый элемент каким-то образом определяет следующий за ним элемент. В отличие от стека и очереди, добавление нового элемента возможно в любом месте списка, также можно удалить любой элемент списка. Ясно, что списковые структуры являются более гибкими, но и немного более сложными в реализации. Фактически, стеки и очереди можно считать частными случаями списков, в которых добавление и удаление элементов может выполняться только на концах.

Стандартный набор операций со списком включает:

• · добавление нового элемента после заданного или перед заданным элементом с проверкой возможности добавления элемента
• · удаление заданного элемента
• · проход по списку от первого элемента к последнему с выполнением заданных действий
• · поиск в списке заданного элемента.

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

Первый способ статической реализации списка

Он основан на том, что логический номер элемента списка полностью соответствует номеру ячейки массива, где этот элемент хранится: первый элемент списка — в первой ячейке массива, второй — во второй, третий — в третьей и т. д.

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

Как выполнить вставку нового элемента внутри списка, например — в ячейку с номером i < N? Для освобождения ячейки i все элементы списка начиная с номера i и до N надо сдвинуть вправо на одну ячейку (конечно, если в массиве есть еще хотя бы одна свободная ячейка). Копирование надо начинать с последней ячейки, т. е. N — на место N+1, N-1 — на место N, и т. д. i — на место i+1. В освободившуюся ячейку i записывается новый элемент.

Аналогично (с точностью до наоборот) выполняется удаление любого внутреннего элемента: освобождается ячейка i и все последующие элементы сдвигаются влево на одну ячейку, т. е. i+1 — на место i, i+2 — на место i+1, и т. д., элемент N — в ячейку N-1.

Возникает вопрос о трудоемкости выполнения подобных операций перемещения ячеек массива. Если каждый элемент списка, размещенный в одной ячейке массива представляет собой запись с большим числом объемистых полей, то затраты на подобное перемещение могут стать слишком большими. Здесь выходом может быть изменение структуры элемента списка: в массиве хранятся ТОЛЬКО УКАЗАТЕЛИ (АДРЕСА) информационных частей и перемещение производится только этих указателей, сами информационные части остаются на своих местах. Учитывая все возрастающие скорости работы современных процессоров и наличие в их архитектуре быстрых команд группового копирования байтов, можно считать данный метод реализации списков вполне работоспособным.