Основные виды списков

Линейные динамические структуры данных (списки)

Линейной динамической структурой (списком) называется множество объектов (элементов, узлов) S={s_i}, i=1,...,n, на котором определены отношения предшествования / следования, причем для любого объекта s_i, i=2,...,n-1 существует единственный “предшественник” s_i-1 и единственный “последователь” s_i+1. Объект s₁ не имеет предшественника и является первым элементом списка, объект s_n не имеет последователя и является “хвостом” списка. Ситуация n=0 определяет особое состояние: “список пуст”.

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

СТЕК – структура, у которой включение / исключение элементов и доступ к элементам производится на одном конце структуры, называемом верхушкой стека (рис. 19). Для стека характерна дисциплина обслуживания “последним пришел – первым обслужен” (LIFO – Last Input First Output).