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

belle
  • 2021-07-16
  • 1

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

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

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

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

Разновидность связного списка — односвязный список, содержащий 3 элемента

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на 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 не встречается.

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

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

Основная статья: Список с пропусками

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

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

Преимущества

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

Недостатки

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

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

См. также

Примечания

  1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7
  2. Выравнивание данных
Источник —

belle
  • 2021-07-16
  • 1
  • Tags:

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

The title for the last searches