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

Структуры данных / Связные списки

Связный список является простейшим типом данных динамической структуры, состоящей из элементов (узлов). Каждый узел включает в себя в классическом варианте два поля:

  • данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.)
  • указатель на следующий узел в списке.

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

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

Классификация списков

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

Связный список, содержащий два поля указателя – на следующий элемент и на предыдущий, называется двусвязным.

По способу связи элементов различают линейные и циклические списки.
Линейные и циклические списки

Связный список, в котором, последний элемент указывает на NULL, называется линейным.

Связный список, в котором последний элемент связан с первым, называется циклическим.

Виды списков

Таким образом, различают 4 основных вида списков.
Односвязный линейный список (ОЛС).
Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Односвязный линейный список
Односвязный циклический список (ОЦС).
Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
Односвязный циклический список
Двусвязный линейный список (ДЛС).
Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
Двусвязный линейный список
Двусвязный циклический список (ДЦС).
Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.
Двусвязный циклический список

Сравнение массивов и связных списков
Массив Список
Выделение памяти осуществляется единовременно под весь массив до начала его использования Выделение памяти осуществляется по мере ввода новых элементов
При удалении/добавлении элемента требуется копирование всех последующих элементов для осуществления их сдвига Удаление/добавление элемента осуществляется переустановкой указателей, при этом сами данные не копируются
Для хранения элемента требуется объем памяти, необходимый только для хранения данных этого элемента Для хранения элемента требуется объем памяти, достаточный для хранения данных этого элемента и указателей (1 или 2) на другие элементы списка
Доступ к элементам может осуществляться в произвольном порядке Возможен только последовательный доступ к элементам

Назад

Комментариев к записи: 2

  • nikerav.com.ua

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


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


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *