Связные списки: классификация, основные понятия

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

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

Каждый узел включает в себя в классическом варианте как минимум два поля:

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

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

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

Связный список

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

По количеству полей указателей различают списки:

  • однонаправленный (односвязный)
  • двунаправленный (двусвязный)

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

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

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

Линейный и циклический списки

Виды списков

Таким образом, различают 4 основных вида списков.

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

Сравнение массивов и связных списков

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

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

Прокрутить вверх