09.05.2021

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


Связный список — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Виды связных списков

Линейный связный список

Односвязный список (однонаправленный связный список)

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:

  • Операция, проверяющая список на пустоту.
  • Три операции добавления объекта в список (в начало, конец или внутрь после любого (n-го) элемента списка);
  • Операция, вычисляющая первый (головной) элемент списка;
  • Операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики

  • Длина списка. Количество элементов в списке.
  • Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Чаще списки типизированы.
  • Список может быть сортированным или несортированным.
  • В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Односвязный список в языках программирования

Си

struct list { int field; // поле данных struct list *next; // указатель на следующий элемент };

применение односвязного списка:

struct list* l1 = (struct list*)malloc(sizeof(struct list)); l1->field = 1; l1->next = (struct list*)malloc(sizeof(struct list)); l1->next->field = 2; l1->next->next = (struct list*)malloc(sizeof(struct list)); /* и т.д. */

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

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

XOR-связный список

Используется редко.

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

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

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

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

Список с пропусками

Развёрнутый связный список

Достоинства

  • эффективное (за константное время) добавление и удаление элементов
  • размер ограничен только объёмом памяти компьютера и разрядностью указателей
  • динамическое добавление и удаление элементов

Недостатки

Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:

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

Похожие новости:

Города Хайбер-Пахтунхвы

Города Хайбер-Пахтунхвы
Список городов Хайбер-Пахтунхвы — список наиболее крупных населённых пунктов пакистанской провинции Хайбер-Пахтунхва. В данном списке отображены крупнейшие города провинции, все данные

Библиографический указатель

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

Суффиксный массив

Суффиксный массив
Суффиксный массив — лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному

Структура (язык Си)

Структура (язык Си)
В языке Си, структура (struct) — композитный тип данных, инкапсулирующий без сокрытия набор значений различных типов. Порядок размещения значений в памяти задаётся при определении типа и сохраняется
Комментариев пока еще нет. Вы можете стать первым!

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

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Разновидности мебельных опор
Разновидности мебельных опор
Мебельные опоры, называемые также ножками, представляют собой фурнитуру, которая позволяет креслам,...
Ипотечное страхование: что это и зачем нужно
Ипотечное страхование: что это и зачем нужно
При оформлении ипотечного кредита договор страхования обезопасит как заемщика, так и финансовую...
Грязезащитные покрытия: чистота - залог здоровья
Грязезащитные покрытия: чистота - залог здоровья
Основная задача покрытия – максимальный сбор уличной грязи с обуви....
Все новости