Линейный список
Линейный список представляет собой последовательность \(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\).
С линейными списками могут выполняться следующие операции.
- Получение доступа к k-му узлу списка для проверки и/или изменения содержимого его полей.
- Вставка нового узла сразу после или до k-го узла.
- Удаление k-го узла.
- Объединение в одном списке двух (или более) линейных списков.
- Разбиение линейного списка на два (или более) списка.
- Создание копии линейного списка.
- Определение количества узлов в списке.
- Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
- Поиск узла с заданным значением в некотором поле.
Ссылки: