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

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

• конструктор для создания пустого списка;
• операция определения пустоты списка;
• операция для добавления элемента в начало списка (cons в Лиспе);
• операция получения первого элемента списка (или «головы») списка (car в Лиспе);
• операция для определения списка, состоящего из всех элементов списка кроме первого (или его «хвоста») (cdr в Лиспе).

Характеристики

По определению, список - это последовательность из N ? 0 элементов X [1], X [2], ... X [n], для которой выполняется следующее условие: если n 0 и X [1] - первый элемент в списке, а X [n] - последний, то k -й элемент расположен между X [k-1] и X [k +1] элементами для всех 1 k n.

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

• получения k-го элемента списка для чтения или записи в него нового значения;
• добавление нового элемента в любую позицию в списке;
• удаление элемента списка;
• поиск элемента, удовлетворяет определенным критериям;
• и многое другое.

Важными частными случаями линейных списков, в которых операции сложения и изъятия определенных значений могут быть выполнены только для первого или последнего элемента, являются:

стек - линейный список, в котором операции сложения и удаления выполняются только на одном конце списка (верхушке стека). Принцип построения стека называют LIFO (англ. last in, first out).

очередь (односторонняя очередь) - линейный список, где операции сложения выполняются на одном конце (в голове очереди), а операции изъятия - на другом конце списка (в хвосте очереди). Принцип построения очереди называют FIFO (англ. first in, first out).

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