Поддержка абстрактного списка

Связные списки

Непрерывные списки

Списки

Списки это набор записей, выстроенных в определенной последовательности. Списки могут быть как статическими, так и динамическими.

Переменные могут храниться в памяти в виде непрерывного списка. Для этого они записываются друг за другом, заполняя непрерывно выделенную для этого область памяти. Это удобно для статического списка, но неудобно для динамического.

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

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

Блоки связного списка могут быть расположены в разных частях памяти. Это упрощает поиск места для расположения списка, особенно если он длинный. Удаление К-й по порядку переменной осуществляется изменением соответствующего указателя, который, находясь в (К-1) блоке списка, теперь будет указывать на (К+1) блок. Аналогично осуществляется добавление в конец списка нового блока. Указатель в прежнем последнем блоке теперь будет содержать адрес добавленного в конец списка блока.

Также можно вставить новый блок внутрь списка на К-ю позицию. Теперь указатель в (К-1) блоке будет указывать на К-й блок, а указатель в К-м блоке будет указывать на (К+1) блок. Такими приемами удобно пользоваться для перестановки местами элементов списка.

Программа должна быть сделана так, чтобы к списку и, соответственно, элементам списка можно было бы обратиться без учета технических подробностей его реализации, то есть указать, например, имя списка и номер элемента A(i).

Для этого программное обеспечение может самостоятельно решать вопрос о том, как разместить элементы списка в памяти. Если есть области памяти длиной в несколько переменных—элементов списка, то можно разместить в них по несколько переменных подряд, как в непрерывном списке. При этом последняя переменная сопровождается расположенным после нее указателем на другой адрес, где находится продолжение списка.

Таким образом, список может быть комбинированным, сочетая черты как связного, так и непрерывного списка.

Такая организация хранения и обработки данных позволяет хранить широко используемые в программировании массивы как списки.

При обращении к списку, программа обращается в ячейку, где хранится указатель на список. Указатель на список содержит адрес первой ячейки списка (адрес его первого элемента).