структурные свойства которого связаны только
Линейный список – это множество n>0 объектов (узлов) Х[1], Х[2], ..., Х[п], структурные свойства которого связаны только с линейным (одномерным) относительным расположением узлов. Если п>0, то Х[1] является первым узлом; для 1<i<n узел Х[i-1] предшествует узлу X[i], а узел X[i+l] следует за ним, Х[п] является последним узлом, т.е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных [17].
Линейный список X рассматривают как последовательность Х[1], Х[2], ..., Х[i], ..., Х[п], компоненты которой идентифицированы порядковым номером, указывающим их относительное расположение в X.
Одномерный линейный список, используемый для хранения данных в памяти машины, называют еще вектором данных или физической структурой хранения данных. Использование линейного списка в качестве физической структуры хранения данных определяется свойствами памяти вычислительной машины. Так, оперативная память ЭВМ представляет вектор, в котором байты упорядочены по возрастанию их адресов от 0 до наивысшего, т.е. проидентифицирова-ны адресом.
Проблема представления логических структур данных в памяти ЭВМ заключается в нахождении эффективных методов отображения логической структуры данных на физическую структуру хранения. Такое отображение называют адресной функцией.
При реализации адресной функции используют два основных метода [17]:
– последовательное распределение памяти;
– в связанное распределение памяти.
