Приложение А Связанные списки

Приложение А

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

Связанный список — это структура хранения информации (контейнер), которая может содержать переменное количество элементов данных, часто называемых узлами, и позволяет манипулировать этими данными. В отличие от статического массива, элементы связанного списка можно создавать динамически. Это дает возможность создавать переменное количество элементов списка, причем указанное количество может быть неизвестно на этапе компиляции. Так как элементы связанных списков создаются в разные моменты времени, они не обязательно будут находиться в смежных областях оперативной памяти. Поэтому элементы списка должны быть связаны друг с другом таким образом, чтобы каждый элемент содержал указатель на следующий за ним элемент (next). Вставка или удаление элементов списка выполняется простым изменением указателей на следующий элемент. Структура связанного списка показана на рис. А.1.

Рис. A.1. Односвязный список

В. некоторых связанных списках содержится указатель не только на следующий, но и на предыдущий элемент (prev). Эти списки называются двухсвязными (doubly linked), потому что они связаны как вперед, так и назад. Связанные списки, аналогичные тем, что показаны на рис. А.1, называются односвязными (singly linked). Двухсвязный список показан на рис. А.2.

Рис. А.2. Двухсвязный список

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

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

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

Связанные документы

Из книги Реестр Windows автора Климов Александр

Связанные документы В последних версиях Windows появилось понятие сопоставленных файлов. Например, если вы собираетесь переместить или удалить html-документ, то будут также перемещены или удалены и сопоставленные с этим документом файлы, которые содержаться в папке


Базовые и связанные размеры

Из книги AutoCAD 2009 автора Орлов Андрей Александрович

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


Связанные текстовые фреймы

Из книги Adobe InDesign CS3 автора Завгородний Владимир

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


Связанные файлы

Из книги Человеческий фактор в программировании автора Константин Ларри Л

Связанные файлы В связи с тем что в профессиональной графике файлы изображений могут достигать большого размера – действительно большого, десятки и сотни мегабайт, – многие программы макетирования и верстки не включают файлы изображений в документ. Так поступает и


48 Связанные объекты

Из книги AutoCAD 2010 автора Орлов Андрей Александрович

48 Связанные объекты Что делает тот или иной предмет легким для понимания? Что делает тот или иной предмет простым в использовании? Что превращает совокупность объектов — не отдельных, а представленных в определенном контексте — в набор рабочих инструментов? Возьмем


Базовые и связанные размеры

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

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


У15.5 Связанные стеки

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

У15.5 Связанные стеки Основываясь на классах STACK и LINKED_LIST, постройте класс LINKED_STACK, описывающий реализацию стека как связного


1.7.4 Связанные документы

Из книги Инфраструктуры открытых ключей автора Полянская Ольга Юрьевна

1.7.4 Связанные документы Серия RFC не содержит спецификаций протоколов и была опубликована как отдельный набор документов For Your Information (FYI — К вашему сведению). Например: RFC 1325 Answers to commonly asked "new Internet user" questions (Ответы на наиболее распространенные вопросы новых пользователей


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

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

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


18.1.3. Ограничения, связанные со временем

Из книги MySQL 5.0. Библиотека программиста автора Гольцман Виктор Иосифович

18.1.3. Ограничения, связанные со временем В 32-разрядных системах Linux, как и в большинстве систем Unix, переменная time_t является целым числом со знаком длиной 32 бита. Это означает, что в 10:14:07 вечера 18 января (четверг) 2038 года она переполнится. Поэтому время 10:14:08 вечера 18 января


6.4. Проблемы, связанные с блокировками

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

6.4. Проблемы, связанные с блокировками В этом разделе мы рассмотрим только внутренние блокировки, используемые сервером MySQL при совместной работе нескольких потоков с одними и теми же данными, и не коснемся внешних блокировок, обеспечивающих координацию работы сервера


Параметры, связанные с ресурсами

Из книги Справочник по параметрам BIOS автора Вонг Адриан

Параметры, связанные с ресурсами CpuAffinityMaskВерсии 1.5 и выше под Windows.cpu_affinityВерсии до Firebird 1.5 под Windows.В Суперсервере Firebird под Windows могут быть проблемы с операционной системой, постоянно переключающей процесс Суперсервера туда и сюда между процессорами на машинах SMP. В списках


Параметры, связанные с коммуникацией

Из книги Оптимизация BIOS. Полный справочник по всем параметрам BIOS и их настройкам автора Вонг Адриан

Параметры, связанные с коммуникацией ConnectionTimeoutВерсия 1.5 и более поздние.connection_timeoutВерсии, предшествующие Firebird 1.5.Задает количество секунд ожидания до прекращения попытки соединения. Значение по умолчанию 180.DummyPacketlntervalВерсия 1.5 и более поздние.dummy_packet_intervalВерсии,


Неполадки, связанные с BIOS

Из книги Разработка ядра Linux автора Лав Роберт

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


Неполадки, связанные с BIOS

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

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


Кольцевые связанные списки

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

Кольцевые связанные списки Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя next последнего элемента обычно устанавливается равным специальному значению, обычно NULL, чтобы показать, что этот элемент списка является последним.