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

• Массивы: одномерные(их ещё называют векторами) и двумерные (их еще называют матрицами)
• Указатели (Pointers). Важно знать про Типизированные указатели.
  Динамическая память (Dynamic memory или Heap Memory)
• Тип данных - Запись (Record)

Рассмотрим реальный случай из жизни:

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

И вы решили организовать это так:

Завести большой массив из строк. Каждая строка с 1 по N-ную в этом массиве будет содержать соответствующую строку из файла. И все бы хорошо, и можно было бы такой массив сделать, но как же быть.. Ведь мы в начале не знаем, сколько строк будет в файле, и не знаем, сколько элементов объявить в массиве.

Как обычно новички поступают в таком случае? Они создают массив по принципу "ШОБ ХВАТИЛО" скажем из 500 элементов:
, и таким образом получается, что наша программа сможет редактировать файлы из пятисот строк. Но, скажу я вам, это ламерский способ! %) Настоящий программист никогда не позволит себе такой вольности: выделять заранее оговоренное количество строк, и тем самым ограничивать пользователя. Настоящий программист непременно воспользуется связанным списком.

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

Давайте рассмотрим такую аналогию: Представьте себе толпу людей. Пусть это будет куча элементов с данными в памяти. В толпе людей все люди стоят перемешано, как и элементы в памяти. Один там, другой тут ... А теперь представьте себе, что каждый человек указывает пальцем на какого либо другого человека в этой толпе. Тогда Я могу сказать, что эти люди образуют друг между другом связь.

Представьте себе: один человек в толпе указывает на другого. Тот в свою очередь указывает на еще кого-то, тот еще на кого-то, и так до какого либо человека, который ни на кого не указывает. Вот точно так же в памяти устроены связанные списки. Каждый элемент в памяти кроме своего значения еще "знает", где в памяти находится элемент, следующий за ним. А самый последний элемент в последовательности "знает", что за ним никого нет.

Теперь на секундочку допустим, что все люди знают по одной строке... ну ... стиха "Буревестник" %) Ну там (буря мглою небо кроет... бла-бла-бла). Но только по одной. Так вот тот человек, который знает первую строку стиха указывает пальцем на человека, который знает вторую строку. Тот в свою очередь указывает на человека, который знает 3 строку. И так до человека, который знает самую последнюю ... как ее там "Пусть сильнее грянет буря!.. ". А этот самый последний уже не указывает ни на кого, давая нам понять, что цепочка людей закончилась.

Так вот точно так же работают связанные списки.

Вернемся к нашей задаче о строках в файле.

Когда у нас есть связанный список, то в первом элементе этого списка нужно поместить первую строку файла, и так-же указать им на второй, чтобы было понятно, где находится следующая строка. Во втором элементе - вторая строка файла, и информация о том, где находится третий элемент. И так далее. Последний элемент не указывает ни на что. Осмыслите как следует и переварите эту информацию, потому что я дальше покажу, как реализуется такой связанный список на Pascal'е.

Каждый элемент связанного списка принято называть нодой (Node).

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

Надеюсь вы понимаете, что это только описание типов данных. Самих данных на самом деле еще нет.
Так вот. Теперь о том что я говорил - а я говорил, что связанный список нельзя описать как массив данных, одной переменной. Зато можно в одной из переменных содержать адрес, где будет находиться самый первый элемент последовательности (ну списка, список еще называют последовательностью). И тогда, зная адрес первого элемента последовательности, можно найти, где находится второй элемент, и потом где находится 3 элемент, и так далее.
Вот пример:
Тут следует сказать, что последний элемент не должен ни на что не указывать. Как это делается на Паскале? Так как указываем на следующий элемент мы при помощи указателей, то указатель, который ни на что не указывает всегда равен NIL. И следовательно если в элементе поле Next=NIL, то это последний элемент в цепочке.
Ну хорошо. Примерно уяснили, как следует описывать элементы списка. А как его вообще создать?
Для того чтобы создать связанный список мы должны в памяти выделять память под динамические ячейки, и для каждого элемента списка настроить значения параметра Next так, чтобы там действительно адрес следующей ячейки, либо же значение NIL (пусто) если это последняя ячейка в последовательности.
Вот простейшая реализация такого связанного списка:

Таким вот образом мы вручную создали связанный список из 4 элементов. Фактически его можно использовать как массив.
Но для доступа к определенному элементу уже нельзя будет использовать его порядковый номер. Нужно будет последовательно начиная с элемента, на который указывает переменная First искать нужный нам.
Зато такой связанный список может содержать в себе сколько угодно (а точнее на сколько хватит памяти) элементов.
А давай-те ка я это продемонстрирую. Автоматизируем процесс. Позволим пользователю вводить сколько угодно элементов, а потом все их выведем на экран:

Только что мы рассмотрели принцип создания простого связанного списка. Но я ничего не сказал об удалении. Хотя компилятор Borland Pascal вставляет в код программы автоматически код, который высвобождает всю память, которая была отведена командой New под новые элементы, но все же хорошим тоном считается удалить все элементы из памяти.
Поэтому нам нужно реализовать цикл, подобный тому, когда мы выводили элементы на экран, но при этом мы должны удалять элементы командой Dispose.
Вот так:


Ну что ж. Основные сведения я уже изложил.
Теперь основные прикладные функции. Их 3: Поиск элемента в списке по значению, Вставка нового элемента, Удаление существующего элемента.

Поиск элемента в списке по значению
Вернёмся к нашей аналогии с толпой людей. Как бы мы искали в толпе людей, знающих по одной строчке из стиха определенного человека, который знает определенную строчку?
Мы бы подошли к первому , узнали, какую строчку он знает. Если это не та, которая нам нужна, то узнали бы, куда он показывает, и пошли бы к тому человеку. После чего повторили бы действия. И повторяли бы их до тех пор, пока не нашли человека, знающего нужную нам строчку. Так в чем же проблема? реализуем этот принцип на Паскале ! %)
...Задание переменных и создание связанного списка в памяти...
...В переменной v находится число, с значением которого мы хотим найти элемент...
Эти же действия удобно оформить в виде функции:

Должен отметить, что результатом поиска будет не значение, а указатель на элемент с искомым значением.

Вставка нового элемента в список
По уже отработанному принципу переносим воображение на толпу людей. Как мы добавим нового человека, который бы знал новую строку стиха?
Для начала мы должны определиться, после какой строки будем вставлять новую строку. Логично? Потом мы по принципу поиска найдем человека, который знает ту строку, после которой мы будем вставлять нового человека. Потом мы возьмем нового человека, скажем ему строку. Затем мы узнаем, на какого человека указывает найденный нами. И скажем новому человеку, чтобы он тоже на него указывал. И в конце концов мы скажем найденному нами человеку, чтобы он указывал на нового человека.
Я понимаю что это запутано, но возможно в реализации будет проще понять. Обдумайте сами представив алгоритм в голове, по ходу дела сравнивая с вот таким кодом:
...Задали связаный список, хотим вставить строку NewStr после строки PrevStr. Тип данных в списке - String...
Таким образом мы ИМЕННО ВСТАВЛЯЕМ между двумя элементами Temp и Temp^.Next новый элемент Temp2, и подправляем указатели, чтобы они составляли правильную последовательность.
Тут нужно отметить то, что если строка PrevStr была в самом последнем элементе, то в списке появится новый элемент, который будет корректно последним. То есть предпоследний будет указывать на него, а новый последний элемент будет будет указывать на "ничто" (Next=NIL).
Естественно и эти действия удобно организовать в отдельную процедуру:

При вставке нового элемента часто бывает удобно вставлять не после определенного значения элемента, а явно указывать, после какого элемента вставлять:


Удаление существующего элемента из списка
Принцип: Ищем в списке элемент с заданным значением. После чего удаляем его, корректируя ссылку предыдущего элемента, чтобы он ссылался не на удаляемый элемент, а на следующий после удаляемого.
Вот реализация:

Так же приведу текст функции, которая удаляет элемент из списка не по значению, а по указателю на него:

---

Итак я рассмотрел простые связанные списки, и три основных операции с ними. Остальные операции могут быть сформированы на основе этих трех.
Теперь я не могу не сказать об теории списков более подробно, и не описать их классификации:
Рассмотренные мной списки называются односвязными. Название такое они получили, потому что связь между элементами таких списков является односторонней - один элемент указывает на следующей, тот в свою очередь на еще один и так далее. То есть каждый элемент указывает только в одном направлении (я принял за норму - указывать на следующий элемент).
Представьте себе список, в котором каждый элемент указывает не только на следующий за ним идущий, а еще и на тот, который был перед ним - на предыдущий. Если сравнивать с толпой людей, то каждый человеку указывает не на одного, а на двух сразу. Тогда одно направление указывания (последовательность людей, которые указывают друг на друга правой рукой) можно условно назвать "направление вперед". А другое направление (указываемое левой рукой) - "направление назад. Таким образом я смог бы перемещаться в последовательности людей не только вперед (как во всех вышеописанных примерах), а и назад. Поскольку каждый человек знает не только своего "потомка" но и "предка".

На самом деле эти направления (вперед/назад) - лишь названия, и ничего больше. Поскольку на самом деле все эти люди всего лишь куча людей. И то, в какой последовательности они друг на друга указывают руками просто определят, какого человека следует брать за каким.
Вот представьте себе, что у вас есть куча переменных, организованных как ячейка связанного списка в памяти. Они все находятся в ней хаотично и не связаны друг с другом. И допустим эти переменные числа. Тогда чисто теоретически их можно взять в такой последовательности, что каждое следующее значение будет больше предыдущего. И тогда такая последовательность будет представлять собой отсортированный по возрастанию массив. И в то же время это будут оставаться хаотичные данные в памяти.
А представьте себе, что у каждой из этих переменных не один параметр Next, а два. И допустим выстроены две цепочки (для одного Next и для другого) так, чтобы по одной цепочки брались элементы по возрастанию, а для другой - по убыванию. Тогда получится что у нас одни и те же данные отсортированы и по возрастанию и по убыванию. В зависимости от того, какое направление взять (Next1, или Next2). А ведь может быть и направление Next3, в котором они отсортированы в порядке их создания, и тогда для одних и тех же данных будет три направления последовательностей.
Поэтому можно утверждать, что списки могут быть не только однонаправленными, а и двунаправленными, трехнаправленными, словом N-направленными. Причем сколько бы не было направлений, все они будут сделаны для одних и тех же данных. Представьте себе, если бы вам нужно было отсортировать массив по возрастанию, и по убыванию, вам бы пришлось создать два массива - один с данными по возрастанию, а другой с данными по убыванию. А тут у вас получатся ЕДИНЫЕ данные, но с двумя направлениями сортировки. Это имеет большую перспективу в том случае, к примеру, если объем данных для каждого элемента последовательности - значительный, поскольку даст существенную экономию памяти.

Так-же списки бывают цикличными (замкнутыми). Это когда последний элемент списка указывает на первый элемент списка (а если список двунаправленный, то и первый может указывать на последний). У такого списка нет начала и конца, он замкнут как бы по кольцу. И по нему можно перемещаться в том или ином направлении до бесконечности, по кругу.

УУФФФФ.. ну вроде-бы все на данный момент.