Связанные списки

В этой теме мы разберем:

• связанные списки;
• работу оптимизации Append;
• потоки данных.

Структуры данных и алгоритмы — это хлеб с маслом информатики. Хотя иногда они кажутся людям чем-то пугающим, разобраться с большинством из них не так сложно. При хорошем объяснении алгоритмы могут быть интересными для изучения и удобными для применения.

Связанные списки

Связанные списки — одна из самых простых структур данных. В статье «Википедии» о связанных списках говорится следующее:

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

Линейная структура данных — это структура, элементы которой образуют какую-то последовательность. Почему же физическое размещение в памяти не имеет значения? Давай разберемся. Допустим, у нас есть массив и объем памяти, который он занимает, фиксирован. Так, если массив состоит из 5 элементов, язык будет захватывать только 5 адресов памяти один за другим. Поскольку эти адреса создают последовательность, массив знает, в каком диапазоне памяти будут храниться его значения. Таким образом, именно физическое размещение в памяти этих значений создает последовательность.

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

Потоки данных

Наши чувства и разум умеют обрабатывать поступающие к нам данные и преобразовывать их в полезную информацию. Когда мы смотрим на что-то, чувствуем запахи или прикасаемся к чему-то, мы обрабатываем данные и находим в них смысл. Например, когда мы просматриваем социальные сети, то всегда прибегаем к потоку данных, упорядоченных в хронологическом порядке и не имеющих конца.

Как можно использовать связанные списки для моделирования такой новостной ленты? Давайте вдохновимся Twitter и в качестве примера создадим тип Post, состоящий из body, publishDate и ссылки на пост next:

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

Структура Feed будет иметь начало (или start), которое будет указывать на первый Post в ленте, и свойство length, которое будет хранить размер Feed в любой момент времени.

Допустим, мы хотим создать Feed с двумя сообщениями. Тогда наш первый шаг — создать функцию Append типа Feed:

Затем мы можем вызвать его дважды:

Итак, что делает этот код? Функция main создает указатель на структуру Feed, на две структуры Post с некоторым фиктивным содержимым и дважды вызывает функцию Append для Feed — это приводит к тому, что ее длина оказывается равна 2. Мы проверяем два значения, которые имеет Feed, обращаясь к start из Feed (который на самом деле является Post) и к элементу next после start, который является вторым Post.

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

Как видишь, после добавления первого Post к Feed длина равна 1, у первого Post есть body и publishDate (как временная метка Unix), а его значение next равно nil (потому что в Feed больше нет Post). Затем мы добавляем второй Post в Feed, и когда мы его проверяем, то видим, что первый имеет то же содержимое, что и раньше, но с указателем на next в списке Post. Второй также имеет body и publishDate, но без указателя на следующий Post в списке. Кроме того, длина Feed увеличивается по мере того, как мы добавляем к ней больше Post.

Теперь вернемся к Append и разберем ее, чтобы лучше понять, как работать со связанными списками. Во-первых, функция создает указатель на значение Post с аргументом body (это body Post), и publishDate устанавливается в виде временной метки Unix для текущего времени.

Затем мы проверяем, равна ли длина (length) Feed 0. Это означает, что в нем нет Post и первый добавленный должен быть установлен в качестве начального Post, удобно названного start.

Но если длина (length) больше 0, то наш алгоритм принимает другой оборот. Он начнется со start Feed и будет проходить через все Post, пока не найдет тот, у которого нет указателя на единицу next. Затем он прикрепит новое значение Post к next последнему Post из списка