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

Всем доброго времени суток.

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

Из название легко видно ( привет матану:) ), что сабж представляет из себя список ( набор каких-то отдельных элементов) и все эти элементы как-то между собой связаны (а теперь привет уже Кэпу).

Итак, что требуется от любой структуры данных? Правильно! Хранить данные. А значит мы в первую очередь выделяем память под хранение какой-то особенно полезной информации( числа, символа, строки и еще over 9000 вариантов), но из предыдущего абзаца вы помните, уважаемые читатели, что нам еще нужна память для хранения связи( а именно для хранения адреса предыдущего элемента).

Что мы имеем в итоге? Правильно, для хранения одного элемента списка нам нужны две ячейки памяти (иногда даже три, но об этом ниже). У нас вырисовывается вот такая картина:

 

element

Допустим, создали мы такой элемент списка, заполнили ячейку с информацией. «Но что же писать в ячейке адреса следующего, ведь элемент пока только один?» — спросите вы. А ничего туда писать не надо, т.е. там будет хранится простой ноль — адрес который никуда не ведет.

И вот мы решили создать еще один элемент списка (пусть первый элемент зовется «А1″, а второй «А2″) :

 

element two-element

Теперь ячейка адреса элемента А2 хранит не ноль, как А1, а адрес ячейки А1.

Добавим еще один элемент:

 

3-element

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

В данном случае А3 называется головой списка(вершиной), а элемент А1 — хвостом. Т.е. самый левый элемент всегда является вершиной, а это значит, что, если мы добавим еще один элемент в перед вершиной, то станет новой вершиной. Соответственно, если добавить элемент после хвоста списка, то он стане новым хвостом.

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

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

twolist

 

А3 снова называется головой, а А1 — хвостом списка.

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

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

 

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

Пример двусвязного кольцевого списка:

 

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

Последняя слегка смахивает на абстракцию, но что поделаешь… Думаю, что по рисункам все ясно и пояснять здесь нечего.

На этой доброй ноте я завершаю свой эпос.

Всем спасибо, что потратили время на прочтение моей статейки, надеюсь, что она вам принесла хоть какую-то пользу.

До скорой встречи в новых статьях. Засим позвольте откланяться.

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Связные списки #2: 3 комментария

  1. Уведомление: Стек #3 | Всего наилучшего — 73!

  2. Уведомление: Указатели? Это просто! С++ #1 | Всего наилучшего — 73!

  3. Уведомление: Введение в динамические структуры данных #1 | Всего наилучшего — 73!

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