Линейный список

Линейный список представляет собой последовательность \(n \geq 0\) узлов \(X_{1}, X_{2}, ... , X_{n}\), важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если \(n > 0\) и \(X_{1}\) является первым узлом, а \(X_{n}\) — последним, то k-й узел \(X_{k}\) следует за \(X_{k − 1}\) и предшествует узлу \(X_{k + 1}\) для всех \(1 < k < n\).

С линейными списками могут выполняться следующие операции.

1. Получение доступа к k-му узлу списка для проверки и/или изменения содержимого его полей.
2. Вставка нового узла сразу после или до k-го узла.
3. Удаление k-го узла.
4. Объединение в одном списке двух (или более) линейных списков.
5. Разбиение линейного списка на два (или более) списка.
6. Создание копии линейного списка.
7. Определение количества узлов в списке.
8. Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
9. Поиск узла с заданным значением в некотором поле.

Ссылки:

• Donald E. Knuth - The Art of Computer Programming, section 2.2.1