Связный список — классическая структура данных, которая позволяет быстрые вставки/удаления, но при этом просаживает другие операции (случайный доступ к элементу). Мы пройдёмся от базовой реализации до других возможных вариаций этой структуры данных и, надеюсь, вместе узнаем что-то новое. Краем глаза увидим возможные применения связных списков. И в конце, для любителей C++, бонус: использование связного списка для сбора диагностики использования динамической памяти в вашем коде.

Односвязный список

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

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

Есть маленький интересный факт про реализацию односвязного списка в стандартной библиотеке C++ (std::forward_list). В отличие от других контейнеров у него нет метода size(). Поинт (насколько я понимаю) такой: если вы используете односвязный список, вы пытаетесь экономить, потому экономьте максимально. А делать метод, который будет выполняться за O(n) вместо привычного O(1) может быть очень деструктивно (т.к. это выбивается из общей схемы работы других контейнеров).

Двусвязный список

Двусвязный список отличается от односвязного лишь тем, что в каждой ноде есть указатель не только на следующего соседа, но и на предыдущего:

Это конечно несёт чуть больше накладных расходов по памяти, но теперь вы можете делать некоторые операции проще. Или вообще выполнять новые (обход из конца в начало).

Sparse List

Про sparse list я уже писал в посте про разреженные структуры данных, но для полноты картины мы повторимся.

Давайте посмотрим на двусвязный список. Мы можем делать модифицирующие операции (вставка, удаление) за O(1) и не модифицирующие (обход в любую сторону) за O(n). И для всего этого нам нужна одна лишь нода списка (не нужно искать соседнюю, как в случае односвязного списка). С другой стороны, мы вынуждены хранить по два указателя на каждую ноду (в современных реалиях это чаще всего целых 16 байт!). Можно ли как-то не сильно ухудшить скорость работы, при этом уменьшив потребление памяти?

Да! А что, если мы сделаем полторасвязный список? Ну то есть связность у него что-то между единицей и двойкой. Достичь этого мы можем имея в среднем односвязный список, в котором некоторые ноды будут двусвязными.

То есть у нас есть некоторое подмножество нод с двумя указателями, один из которых указывает на предыдущую двусвязную ноду, а другой — на следующую в списке ноду. Т.к. размер односвязного «подсписка» (последовательность нод от одной двусвязной ноды до другой) конечен и фиксирован заранее, любая операция всё ещё занимает O(1), так же как и у двусвязного списка (конечно, с выросшей константой). Вдумчивый читатель может заметить, что можно наделать вставок в один односвязный подсписок, и все наши асимптотики сломаются! Но никто не мешает нам поддерживать размеры этих подсписков не больше некоторого заранее заданного числа (на картинке 3, если считать двусвязные ноды на концах). То есть, если вы уже вставили односвязную ноду после односвязной, то сделайте её двусвязной и поправьте ссылки у двусвязных соседей.

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

Собственно из‑за того, что у вас двусвязные ноды находятся на некотором расстоянии друг от друга, он и называется разреженным.

Как подобрать этот самый «коэффициент разреженности»? Хорошего ответа нет. Эмпирическим путём можно понять, что писать подобную структуру сильно проще (да и константа меньше), если ноды просто чередуются. Особенно обходить список в обратном порядке будет сильно дешевле, если двусвязные ноды встречаются чаще.

А как память экономить? С точки зрения написания кода может возникнуть желание использовать что-то вроде union/std::variant, но такие типы будут иметь размер максимального из объектов. То есть в итоге мы всё ещё имеем решение, сравнимое с двусвязным списком.

К сожалению, красиво никак. Вам в любом случае нужно уметь работать с нодами различного размера (тут может помочь type-erasure в каком-то виде). Плюс нужно располагать указатель на предыдущую ноду последним в структуре, чтобы брать указатель на следующую ноду/значение из списка было удобнее. Но зато задача определить, какой тип у ноды, несложная. Т.к. указатели имеют нулевые старшие биты, их можно свободно использовать для этих нужд. Как раз у указателя на следующий элемент можно забрать один из этих битов и установить в 1, если нода имеет ещё и обратный указатель (важно не забыть установить бит в ноль перед тем, как обращаться по этому указателю к следующей ноде). А ещё начинаются проблемы, когда вы хотите переместить ноду из одного списка в другой: раз она может поменять свой тип, вам необходимо будет заново освободить/выделить память. Можно при желании в двусвязных нодах вообще не хранить значения, но проблемы почти никуда не уходят + непонятно, насколько мы тут вообще что-то экономим.

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

Вот ссылка на реализацию, если очень интересно повтыкать.

XOR list

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

...  A       B         C         D         E  ...
         –>  next  –>  next  –>  next  –>
         <–  prev  <–  prev  <–  prev  <–

То xor-список будет выглядеть так:

...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

Теперь мы:

• сократили накладные расходы на указатели соседей в два раза;

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

In-memory linked list

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

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

Для начала опишем концепцию. Есть три момента, которые хочется отметить заранее:

1. Будем считать, что размер списка ограничен сверху заранее. Конечно, легко навернуть сверху динамическую реаллокацию, когда выделенной памяти недостаточно (из-за чего некоторые асимптотики становятся амортизированными), но задача эта понятна и не представляет особого интереса. Отвлекаться не будем. 

2. Т.к. память для листа выделяется заранее (ведь мы сразу знаем максимальный размер), а объект может быть довольно тяжёлым по дефолту/не иметь конструктора по умолчанию, нужно каким-то образом не создавать объекты в нодах при аллокации листа. Для этого можно использовать корректно выравненный массив std::byte. При наличии таких ограничений даже не обязательно выделять память в рантайме. Если вы знаете максимальный размер в compile time, вы можете выделить необходимую память на стеке. Для некоторых случаев LRU кешей и freelist это подходящее решений (про них см. ниже).

3. Рассматривать будем двусвязный список, хотя всё описанное будет валидно и для односвязного.

Т.к. мы теперь оперируем не областью памяти, а элементами массива, указатели на соседние ноды заменятся на индексы соседей в нашем массиве. Т.е. наша нода принимает вид:

template <typename T>
struct Node {
  alignas(T) std::byte value[sizeof(T)];
  uint32_t prev;
  uint32_t next;  // тут можно выбрать более подходящий тип в зависимости 
                  // от потенциального размера вашего списка
};

Рядом ещё встаёт вопрос про то, как сохранить асимптотики оригинальной структуры данных, а именно O(1) на вставку/удаление/перемещение элемента. Надо же быстро понимать, где взять новую свободную ноду! Решается это очень просто: весь наш массив будет делиться на два подсписка — для пользовательских данных и для хранения свободных элементов:

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

Понятно, как создавать подобный список за O(N): проинициализируем список с пустыми ячейками при создании листа и готово. Но это можно делать быстрее!

Предположим, мы выделили нужный кусок памяти. Пока у нас нет ни списка заполненных, ни списка пустых ячеек. Будем поддерживать указатель на самую левую неинициализированную ячейку. Когда мы хотим вставить элемент, мы будем добавлять её в список заполненных элементов и сдвигать указатель вправо. Как только происходит удаление элемента из уже инициализированной ячейки, перекладываем её в список свободных. При новых вставках можем сначала полностью вычистить список пустых ячеек, а потом только вернуться к смещению указателя на неинициализированные ячейки. В конце концов у вас останется просто два списка: для пустых и заполненных ячеек. И в итоге мы умеем создавать такой список за O(1).

Такой подход несёт некоторый оверхед: теперь имеем две лишние unit32_t переменные, но за предполагаемый профит в эффективности можно и потерпеть.

А в чём суть-то такой реализации? Во-первых, мы не будем больше тратить время на выделение памяти при каждой новой вставке (конечно, предвыделить память можно и в стандартной реализации с отдельными нодами). Во-вторых, мы можем словить профит при итерации по всем элементам листа в случае, если соседние элементы лежат достаточно близко.

А что делать, если данные лежат плохо? Например вот так (для простоты понимания указатели на предыдущих соседей опустим):

По-хорошему их стоит переупорядочить:

Но когда делать такое переупорядочивание? Можно, например, когда разница между позицией текущей ноды и позицией её соседа большего некоторого значения K, где K означает, что две соседние ноды точно не помещаются в одну кешлинию. Конечно, критерий довольно нестойкий и может привести к слишком большому замедлению обычных операций. Можно критерий этот проверять раз в какое-то количество операций. А можно в целом поддерживать кол-во пар соседей, для которых это условие ломается, и когда их становится слишком много, выполнять уплотнение (это конечно дополнительные расходы).

В итоге такой подход тоже выглядит мутновато. Часть с уплотнениями является самой важной в реализации, но адекватных критериев для её выполнения не особо видно. Ну и ладно.

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

Есть другой способ получить какой‑то профит от последовательной памяти — развёрнутый список. Тут всё просто: в каждой ноде вы храните не один элемент, а несколько:

Так некоторые элементы лежат рядом, и потому вы будете тратить меньше памяти на указатели (не 1–2 указателя на одно значение, а 1–2 указателя на M значений (на картинке M=4)).

Конечно, с размером блока нужно быть аккуратным, ведь при вставке в середину блока вы получаете всё те же проблемы, что и в обычных последовательных контейнерах: придётся сдвигать все данные. Обычно рекомендуется брать размер одного блока так, чтобы он полностью попадал в кешлинию.

Интрузивный список

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

В базовой реализации интрузивный список обычно имеет некоторый тип ListHook (некоторый минимальный интерфейс без деталей реализации логики):

struct ListHook {
    ListHook* prev_;
    ListHook* next_;
};

Если вы хотите научиться класть некоторые данные в некоторый List, то необходимо отнаследовать ваш тип от ListHook.

struct MyType : ListHook { int x; };

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

struct ListHook2 { 
  ListHook2* prev;
  ListHook2* next;
};

struct MyType : ListHook, ListHook2 { int x; };

Конечно, писать так может быть не очень удобно, потому обычно ListHook делают шаблонным и пихают в этот шаблон некоторый тег:

template <typename T>
struct ListHook {
  ListHook* prev;
  ListHook* next;
};

struct OrdinaryListTag {};
struct LockfreeListTag {};

struct MyType : ListHook<OrdinaryListTag>, ListHook<LockfreeListTag> { 
  int x; 
};

Теперь при создании вашего листа вы можете явно указать тег, который поможет вам привести экземпляры MyType к ListHook с нужным тегом и достать указатели на соседей:

List<MyType, OrdinaryListTag> list;

// где-то в реализации List
auto prev = static_cast<ListHook<Tag>*>(cur_node_ptr)->prev;

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

Конечно, этот подход обобщается и на другие структуры. Так вы можете хранить данные одновременно и в списке, и в дереве. Или в двух разных деревьях, которые сортируют по различным ключам. Я ранее писал про bimap [1] — так же один из примеров интрузивных контейнеров.

Но раз мы тут уже разговариваем про списки, то вот вам статья про то, как интрузивные списки использовались при исправлении крашей в Starcraft.

Персистентный список

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

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

Предположим изначально у нас есть следующий список:

где v=1 говорит нам, что это первая версия списка. Теперь давайте изменим значение у ноды с двойкой. Для этого нам нужно создать новую ноду и сохранить указатели на неё:

Таким образом, в каждой ноде будем хранить не просто указатели на следующую ноду, а массив пар (версия, указатель). Когда мы хотим получить версию k нашего списка, мы пройдёмся от головы до хвоста и в каждой ноде бинарным поиском найдём нужный указатель. Готово!

Не сложнее выглядит операция вставки ноды (v=3) и её удаления (v=4):

Подобный подход реализации персистентности (когда мы храним в ноде не одно её состояние, а несколько) называется методом толстой ноды (fat node method).

Конечно, при большом количестве операций в нодах будет лежать слишком много пар (версия, указатель), из-за чего операции по асимптотике ухудшатся до O(log v), где v — количество версий. Если развивать эту идею, то можно улучшить реализацию до O(1) на операцию амортизировано. Но заниматься мы этим не будем :)

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

Применения связных списков

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

LRU кеш

Last Recently Used кеш — кеш, который при достижении ограничения на количество элементов вытесняет элемент, который использовался наиболее давно. В простейшей форме его реализация это список для поддержания порядка обращения к элементам и ассоциативный массив, который позволяет к этим элементам быстро обращаться. С точки зрения C++ базово сигнатура выглядит так:

template <typename Key, typename Value>
class LRUCache {
  public:
    LRUCache(std::size_t max_capacity);
  
    void SetValue(const Key& key, const Value& value);
    void GetValue(const Key& key);

  private:
    std::unordered_map<Key, std::list<std::pair<Key, Value>>::iterator> map_;
    std::list<std::pair<Key, Value>> list_;
    std::size_t max_capacity_;
};

Тут списки используются для того, чтобы эффективно поддерживать порядок обращения к элементам кеша (например от самых недавних до самых давних обращений). Тогда при обращении к некоторому элементу с помощью map_ мы быстро можем достать итератор на соответствующую пару (ключ, значение) в списке и за O(1) переставить её в начало списка. Вот и всё! Польза нанесена.

Внимательный читатель скажет, что может быть неэффективно хранить ключ дважды (в map_ и list_). И это так. На помощь нам приходит интрузивный список! Подробнее можно посмотреть в докладе Антона Полухина: Ещё чуть быстрее делаем свой контейнер.

Про другие кеши я когда-то писал в [2].

Freelist

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

Одной из оптимизаций freelist также является хранение не одного объекта в блоке, а нескольких. А это как раз наш развёрнутый список.

Другие структуры данных

Связные списки используются для реализации таких сд как skiplist (можно почитать тут) или, например, персистентный стек. 

Рядом ещё могу упомянуть доклад с последнего CppCon: Designing Fast and Efficient List-like Data Structures.

Та самая загадка про 100 заключённых

Без лишних пояснений отправлю вас смотреть видос :)

Бонус: статический список для сбора информации о динамических аллокациях

Сначала посмотрим на то, как это выглядит, а потом почему это круто.

Заведём структурку, в которую будем складывать необходимую информацию:

struct AllocationInfo {
    const char* function;
    unsigned int line;
    unsigned long count;
    unsigned long bytes;
    AllocationInfo* next;
};

Это базовая нода списка, в которой будем хранить всю необходимую информацию об аллокации. Ну и заведём голову списка:

static AllocationInfo root;

Теперь напишем макрос, который будет служить базой для функции аллокации:

#define MYALLOCATE(n, name)                          \
   [name_data = name] (size_t bts) {                 \
       static AllocationInfo here;                   \
       static bool firstCall = [name_data]() {       \
           /*first call, initialize the struct*/     \
           here.function = name_data;                \
           here.line = __LINE__;                     \
           here.next = root.next;                    \
           root.next = &here;                        \
           return true;                              \
       }();                                          \
       /* Cool, now deposit info about calls */      \
       ++here.count;                                 \
       here.bytes += (bts);                          \
       return malloc(bts);                           \
   }(n)

Создаём новую ноду, которую инициализируем при первом появлении в строчке, после чего обновляем информацию, если надо. Ну и макрос-обёртка:

#define ALLOC(n) MYALLOCATE(n, __PRETTY_FUNCTION__)

Теперь везде, где хочется выделять память, будем использовать макрос ALLOC. И в конце можем обойти список для получения результата:

auto p = &root;
p = p->next;
while (p) {
    std::cout << "Func: " << p->function << std::endl;
    std::cout << "Line: " << p->line << std::endl;
    std::cout << "Times: " << p->count << std::endl;
    std::cout << "Bytes: " << p->bytes << std::endl;
    p = p->next;
}

Демо на godbolt.

Видим какие-то такие результаты:

Func: int main()
Line: 46
Times: 1
Bytes: 128

Func: void some_func(size_t)
Line: 36
Times: 2
Bytes: 48

Func: int main()
Line: 40
Times: 1
Bytes: 8

В main в строке 46 за один раз было выделено 128 байт; в some_func в строке 36 за два раза 48 байт и в main в строке 40 за раз 8 байт.

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

И самый сок, что весь список у вас static, т.е. нет динамических аллокаций на него. Только те, которые лежат под вызовом ALLOC.

Можно немножко зарефакторить код с использованием std::source_location. Оставим как упражнение любознательному читателю.

А можно подписаться на мой бложик в тг, где я иногда пишу про программирование и C++ (t.me/thisnotes). Ну и ссылочки на отдельные посты, упоминавшиеся выше:

[1] Bimap: t.me/thisnotes/275;

[2] Про различные кеши: t.me/thisnotes/156.