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

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

По своей сути связный список (linked list) представляет собой цепочку элементов или объектов с некоторыми описаниями (обычно называемых узлами). При этом каждый элемент содержит указатель, указывающий на следующий элемент в списке. Такая структура данных называется односвязным списком (singly linked list) - каждый элемент имеет только одну ссылку или указатель на следующий элемент. Сам список начинается с первого узла, от которого путем последовательных переходов по ссылкам можно обойти все остальные узлы. Обратите внимание, что определение связного списка отличается от определения массива, для которого следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.

Рисунок 3.1. Односвязный список

А каким образом помечается конец списка? Самый простой способ - установить указатель ссылки в последнем элементе списка равным nil. Это будет означать, что следующий элемент отсутствует. Второй способ - ввести специальный узел, называемый конечным узлом, и установить так, чтобы ссылка последнего узла указывала на этот узел. И третий способ - установить так, чтобы ссылка последнего узла указывала на первый элемент. В этом случае мы получим круговой связный список.

А теперь рассмотрим, чем же связный список отличается от массива. Первое, что нужно отметить, - размер связного списка можно не устанавливать. Для массива нам всегда было нужно заранее знать, сколько элементов будет в нем храниться (чтобы можно было статически распределить непрерывный участок памяти) или разработать некоторую схему расширения массива (или его сокращения), чтобы массив мог разместить большее (или меньшее) количество элементов. В связном списке каждый узел является отдельным элементом. И в простых случаях распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется память, а затем элемент просто на него устанавливается ссылка из списка. При удалении узла нужно всего лишь удалить ссылки на него и освободить занимаемую им память.

Хорошо. Если связный список настолько удобен, почему бы его не использовать вместо массива? В чем состоят его недостатки? Первый, хотя и незначительный, состоит в том, что каждый элемент связного списка должен содержать указатель на следующий элемент. Таким образом, чтобы вставить элемент в список, его реальный размер необходимо увеличить на размер указателя (в настоящее время это 4 байта).

Хуже то, что память под каждый узел распределяется отдельно. Сравним эту ситуацию с аналогичной ситуацией для массива. Распределение памяти под n элементов массива, фактически, представляет собой операцию класса O(1): все элементы должны находится в одном непрерывном блоке памяти, поэтому одновременно распределяется целый блок. (Нужно помнить, что память для элементов массивов не обязательно должна распределяться из кучи. Массивы могут представлять собой, например, локальные переменные в стеке.) Для связного списка память под узлы распределяется отдельно, следовательно, это операция класса O(n). Даже если не учитывать быстродействие, подобное поведение может привести к фрагментации кучи.

Самым большим недостатком связного списка является получение доступа к некоторому элементу n. В массиве доступ к n-ному элементу требует проведения простых арифметических вычислений, поскольку все элементы содержатся в одном непрерывном блоке памяти. С другой стороны, в списке получение доступа к элементу n требует прохождения по ссылкам от первого элемента до n-ного. Другого метода доступа не существует, мы всегда должны следовать по ссылкам. (Обратите внимание, что можно применить определенные хитрости, например, хранить элемент и его позицию в рамках списка в кэш-памяти. В таком случае можно определять целесообразность начала прохождения списка с его первого элемента или с элемента, хранящегося в кэш-памяти.)

Узлы связного списка

Перед началом описания операций со связным списком давайте рассмотрим, как каждый узел списка будет представляться в памяти. Знание структуры узла позволит нам более детально рассматривать основные операции со связными списком. Структура узла списка, не использующего классы и объекты, выглядит следующим образом:

type

PSimpleNode = ^TSimpleNode;

TSimpleNode = record

Next : PSimpleNode;

Data : SomeDataType;

end;

Тип PSimpleNode представляет собой указатель на запись TSimpleNode, поле Next которой содержит ссылку на точно такой же узел, а поле Data - сами данные. В приведенном примере тип данных узла задан как SomeDataType. Для перехода по ссылке нужно написать примерно следующий код:

var

NextNode, CurrentNode : PSimpleNode;

begin

• • •

NextNode := CurrentNode^.Next;

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Списки

Из книги автора

Списки Списки дают возможность расположить большое количество пунктов компактно. При создании списков вы сами можете определить количество видимых элементов. Можно настроить возможность выбора одного или нескольких пунктов. По функциям списки напоминают


Списки

Из книги автора

Списки Рассмотрим все возможности задания спискам различного визуального форматирования.Кстати, если вы с помощью display: marker укажете маркер вместе с элементом списка, созданным с помощью свойств списка, то маркер просто-напросто заменит стандартный элемент списка.


Списки

Из книги автора

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


Списки

Из книги автора

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


15.5.6. Списки ACL

Из книги автора

15.5.6. Списки ACL ACL (Access Control Lists) — списки контроля доступа. Довольно часто возникает потребность группировки однотипных параметров в единое целое для их последующей обработки. Для эффективного решения этой задачи используются списки контроля доступом (ACL). Например: acl SSL_ports


18.6. Списки ACL

Из книги автора

18.6. Списки ACL ACL (Access Control Lists) — списки контроля доступа. Довольно часто возникает необходимость группировки однотипных параметров в единое целое для их последующей обработки. Для эффективного решения этой задачи используются списки ACL. Например:acl SSL_ports port 443 563Эта запись


23.2.4. Списки

Из книги автора

23.2.4. Списки Библиотека Glib содержит средства для работы с одно- и двусвязными списками. Особенность двусвязного списка заключается в том, что по нему можно перемещаться в обоих направлениях — назад и вперед. В файле gslist.h (Glib Single List) описаны средства для работы с


Списки

Из книги автора

Списки Когда в тексте нужно что-то перечислить, это принято делать с помощью списков. Пока читаете книгу, обратили внимание, сколько в ней есть списков? Я их создавала в Word с помощью специальных инструментов. Сейчас расскажу вам о них.Остаемся в группе Абзац на вкладке


Маркированные списки

Из книги автора

Маркированные списки При создании маркированных списков можно использовать самые разные типы маркеров. Список кнопки Маркеры (см. рис. 4.30) и одноименная команда контекстного меню (см. рис. 4.32) позволяют выбрать один из семи наиболее применяемых маркеров. Кроме того, можно


Нумерованные списки

Из книги автора

Нумерованные списки При создании нумерованных списков можно использовать самые разные типы нумерации. Список кнопки Нумерация (рис. 4.36) и одноименная команда контекстного меню (см. рис. 4.31) позволяют выбрать один из семи наиболее часто используемых типов нумерации. Кроме


Многоуровневые списки

Из книги автора

Многоуровневые списки Microsoft Word позволяет создавать также многоуровневые списки, содержащие до девяти уровней различных списков. При этом каждый уровень может иметь собственный маркер или номер.Кнопка Многоуровневый список, которая находится в группе Абзац вкладки


5.1.8. Списки

Из книги автора

5.1.8. Списки Текстовый процессор Pages, как и MS Word, предлагает создавать списки следующих видов:? Маркированные. В качестве маркера могут быть использованы символы, готовые картинки, входящие в библиотеку, картинки пользователя;? Нумерованные. Перечень вариантов для


Списки

Из книги автора

Списки Чтобы акцентировать внимание на отдельных абзацах, их можно пронумеровать, создав так называемый нумерованный список. Другой способ выделения абзацев состоит в отметке их маркерами (маркированный список). Например, последовательность выполнения практических


Переадресующие списки САС

Из книги автора

Переадресующие списки САС Статичное разбиение полных списков САС и задание постоянного пункта распространения САС в дополнении CRL Distribution Point каждого сертификата возможно только тогда, когда выпускающий сертификаты УЦ заранее знает, как следует разбивать информацию об


Дельта-списки и косвенные дельта-списки САС

Из книги автора

Дельта-списки и косвенные дельта-списки САС Назначение дельта-списка - информировать об изменениях в САС, произошедших с момента его выпуска или с некоторого заданного момента времени, другими словами, о приращении САС (как известно, приращение обозначается символом ,