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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

См. также

• Стек
• Очередь
• Дерево
• Сортировка связного списка

Отрывок, характеризующий Связный список

А Мавра Кузминишна еще долго с мокрыми глазами стояла перед затворенной калиткой, задумчиво покачивая головой и чувствуя неожиданный прилив материнской нежности и жалости к неизвестному ей офицерику.


В недостроенном доме на Варварке, внизу которого был питейный дом, слышались пьяные крики и песни. На лавках у столов в небольшой грязной комнате сидело человек десять фабричных. Все они, пьяные, потные, с мутными глазами, напруживаясь и широко разевая рты, пели какую то песню. Они пели врозь, с трудом, с усилием, очевидно, не для того, что им хотелось петь, но для того только, чтобы доказать, что они пьяны и гуляют. Один из них, высокий белокурый малый в чистой синей чуйке, стоял над ними. Лицо его с тонким прямым носом было бы красиво, ежели бы не тонкие, поджатые, беспрестанно двигающиеся губы и мутные и нахмуренные, неподвижные глаза. Он стоял над теми, которые пели, и, видимо воображая себе что то, торжественно и угловато размахивал над их головами засученной по локоть белой рукой, грязные пальцы которой он неестественно старался растопыривать. Рукав его чуйки беспрестанно спускался, и малый старательно левой рукой опять засучивал его, как будто что то было особенно важное в том, чтобы эта белая жилистая махавшая рука была непременно голая. В середине песни в сенях и на крыльце послышались крики драки и удары. Высокий малый махнул рукой.
– Шабаш! – крикнул он повелительно. – Драка, ребята! – И он, не переставая засучивать рукав, вышел на крыльцо.
Фабричные пошли за ним. Фабричные, пившие в кабаке в это утро под предводительством высокого малого, принесли целовальнику кожи с фабрики, и за это им было дано вино. Кузнецы из соседних кузень, услыхав гульбу в кабаке и полагая, что кабак разбит, силой хотели ворваться в него. На крыльце завязалась драка.
Целовальник в дверях дрался с кузнецом, и в то время как выходили фабричные, кузнец оторвался от целовальника и упал лицом на мостовую.
Другой кузнец рвался в дверь, грудью наваливаясь на целовальника.
Малый с засученным рукавом на ходу еще ударил в лицо рвавшегося в дверь кузнеца и дико закричал:
– Ребята! наших бьют!
В это время первый кузнец поднялся с земли и, расцарапывая кровь на разбитом лице, закричал плачущим голосом:
– Караул! Убили!.. Человека убили! Братцы!..
– Ой, батюшки, убили до смерти, убили человека! – завизжала баба, вышедшая из соседних ворот. Толпа народа собралась около окровавленного кузнеца.
– Мало ты народ то грабил, рубахи снимал, – сказал чей то голос, обращаясь к целовальнику, – что ж ты человека убил? Разбойник!
Высокий малый, стоя на крыльце, мутными глазами водил то на целовальника, то на кузнецов, как бы соображая, с кем теперь следует драться.
– Душегуб! – вдруг крикнул он на целовальника. – Вяжи его, ребята!
– Как же, связал одного такого то! – крикнул целовальник, отмахнувшись от набросившихся на него людей, и, сорвав с себя шапку, он бросил ее на землю. Как будто действие это имело какое то таинственно угрожающее значение, фабричные, обступившие целовальника, остановились в нерешительности.
– Порядок то я, брат, знаю очень прекрасно. Я до частного дойду. Ты думаешь, не дойду? Разбойничать то нонче никому не велят! – прокричал целовальник, поднимая шапку.
– И пойдем, ишь ты! И пойдем… ишь ты! – повторяли друг за другом целовальник и высокий малый, и оба вместе двинулись вперед по улице. Окровавленный кузнец шел рядом с ними. Фабричные и посторонний народ с говором и криком шли за ними.
У угла Маросейки, против большого с запертыми ставнями дома, на котором была вывеска сапожного мастера, стояли с унылыми лицами человек двадцать сапожников, худых, истомленных людей в халатах и оборванных чуйках.
– Он народ разочти как следует! – говорил худой мастеровой с жидкой бородйой и нахмуренными бровями. – А что ж, он нашу кровь сосал – да и квит. Он нас водил, водил – всю неделю. А теперь довел до последнего конца, а сам уехал.
Увидав народ и окровавленного человека, говоривший мастеровой замолчал, и все сапожники с поспешным любопытством присоединились к двигавшейся толпе.
– Куда идет народ то?
– Известно куда, к начальству идет.
– Что ж, али взаправду наша не взяла сила?
– А ты думал как! Гляди ко, что народ говорит.
Слышались вопросы и ответы. Целовальник, воспользовавшись увеличением толпы, отстал от народа и вернулся к своему кабаку.
Высокий малый, не замечая исчезновения своего врага целовальника, размахивая оголенной рукой, не переставал говорить, обращая тем на себя общее внимание. На него то преимущественно жался народ, предполагая от него получить разрешение занимавших всех вопросов.
– Он покажи порядок, закон покажи, на то начальство поставлено! Так ли я говорю, православные? – говорил высокий малый, чуть заметно улыбаясь.
– Он думает, и начальства нет? Разве без начальства можно? А то грабить то мало ли их.
– Что пустое говорить! – отзывалось в толпе. – Как же, так и бросят Москву то! Тебе на смех сказали, а ты и поверил. Мало ли войсков наших идет. Так его и пустили! На то начальство. Вон послушай, что народ то бает, – говорили, указывая на высокого малого.