Линейный список. Функциональная спецификация: операции в произвольном месте

Модуль "Линейные списки" • урок 1 из 9 • ~6 минут

Что это такое

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

Зачем это нужно

Линейные списки необходимы там, где принцип очереди "первым пришел - первым ушел" недостаточно гибок. Например, в операционных системах очередь процессов может зависеть от приоритета: если приходит высокоприоритетная задача, она должна быть вставлена не в конец очереди, а в ее середину или даже в начало. Списки решают задачу произвольной вставки без разрушения структуры.

Линейный список. Функциональная спецификация: восемь операций

Математически список - это упорядоченная последовательность (в которой элементы могут повторяться). Порядок определяется не жесткими индексами, как в векторе, а отношениями "предыдущий-следующий".

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

• СОЗДАТЬ - порождает пустой список.
• ПУСТО - проверка на пустоту.
• ДЛИНА - количество элементов в списке.
• ПЕРВЫЙ / ПОСЛЕДНИЙ - получение доступа к краям списка.
• СЛЕДУЮЩИЙ / ПРЕДЫДУЩИЙ - переход от одного элемента к соседнему.
• ВСТАВКА - добавление нового элемента ДО или ПОСЛЕ конкретного заданного элемента.
• УДАЛЕНИЕ - изъятие конкретного элемента с сохранением связи его соседей.
• УНИЧТОЖИТЬ - удаление всего списка из памяти.

Важное логическое свойство списка: ПРЕДЫДУЩИЙ(СЛЕДУЮЩИЙ(x)) = x (каждый элемент является предыдущим для следующего за ним). Для кольцевых списков также выполняется условие СЛЕДУЮЩИЙ(ПОСЛЕДНИЙ) = ПЕРВЫЙ.

Цена свободы (Сложность доступа)

В отличие от вектора, где доступ к i-му элементу занимает время O(1) по индексу, элементы линейного списка не пронумерованы. Чтобы найти нужный элемент, необходимо стартовать с головы и перебирать их один за другим. Поэтому поиск в списке занимает время O(N). Зато сама физическая вставка между уже найденными соседями обходится очень дешево.

Абстрактный интерфейс на C

Поскольку физическое устройство списка может быть разным, его спецификация в C выражается через интерфейс с использованием абстрактного итератора для указания позиции:

#include <stdbool.h>

typedef int T;
typedef struct List List;
typedef struct Iterator Iterator;

void Create(List* l);
bool Empty(List* l);
int Length(List* l);
Iterator First(List* l);
Iterator Last(List* l);
Iterator Next(Iterator i);
Iterator Prev(Iterator i);

/* Вставка и удаление требуют указания КОНКРЕТНОЙ позиции */
void Insert(List* l, Iterator pos, T value); 
void Delete(List* l, Iterator pos);
void Destroy(List* l);