# Связные списки для самоваров
## 1. Списки
Список — это абстрактная структура данных. Структура данных — значит, набор какой-то инфы, как-то организованной. Вот список хранит **последовательность** элементов. И мы можем получить энный элемент с начала.

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

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

Как реализовать список? Можно хранить элементы последовательно в непрерывном куске памяти. Такой тип данных (уже не абстрактный) называется **вектором** или **массивом**. Ну, в C его уже по-любому юзали: `int[] array` какой-нибудь там.

Другой способ — сделать **связный список**. Вот о нём и поговорим.

## 2. Связные списки
Вот код.

struct list {
    int value;
    struct list *next;
}

Здесь мы объявили структуру `struct list`, в который запихали 2 поля:

- `value` — это значение.
- `next` — указатель на следующий элемент. Если элемент последний в списке, то сюда пишем `NULL`.

Последняя хрень творит магию: мы из одного элемента можем получить следующий! А затем следующий за ним! И идти так до конца — пока `next` не `NULL`. Такая реализация называется **связным списком**, потому что элементы связаны через указатель.

Проверим, что это вообще список.

- [x] Храним последовательность элементов.
- [x] Можем получить энный элемент.

  size_t i = 0;

  for (struct list *l = start; l != NULL; l = l->next) {
    if (i == n) {
      printf("Нашли энный элемент: %d\n", l->value);
      break;
    }

    i++;
  }

- [x] Можно добавить новый элемент.

  // Добавить `value` на место под номером `pos` в списке `l`.
  void insert(struct list **l, size_t pos, int value) {
    if (pos == 0 || *l == NULL) {
      // Добавляем элемент в начало списка:
      // - Создаём новый стракт
      struct list *head = malloc(sizeof(struct list));
      // - Сетим поля, следующим элементом будет *l
      head->value = value;
      head->next = *l;
      // - А то, что было на месте *l, мы заменяем нашим новым первым элементом
      *l = head;
    } else if ((*l)->next != NULL) {
      // Отрежем голову списка и уйдём в рекурсию.
      insert(&(*l)->next, pos - 1, value);
    } else {
      // У нас pos больше или равен длине списка.
      // Добавляем в конец и не мучаемся.
      struct list *tail = malloc(sizeof(struct list));
      tail->value = value;
      tail->next = NULL;
      (*l)->next = tail;
    }
  }

Здесь я заюзал рекурсию. Лучше это делать циклом, конечно. Но мне лень.

- [x] Можно удалить элемент какой-то.

  // Удалить элемент под номером `pos` из списка `l`.
  void remove(struct list **l, size_t pos) {
    if (*l == NULL) {
      // Список пуст. Бывает и такое.
      return;
    }

    if (pos == 0) {
      // Удаляем первый элемент списка:
      // - Выдёргиваем следующий элемент
      struct list *next = (*l)->next;
      // - Освобождаем память из-под удалённого элемента
      free(*l);
      // - Ставим `next` в главу списка
      *l = next;
      // - Профит
    } else if ((*l)->next != NULL) {
      // Ну, тут тоже рекурсией смотрим следующий элемент.
      remove(&(*l)->next, pos - 1);
    } else {
      // Мы дошли до конца списка, но pos всё ещё не 0!
      // Чутка зашкалил, значит, pos.
      // Ничего не делаем.

      return;
    }
  }

- [x] И можно проходиться по всем элементам.

  size_t i = 0;

  for (struct list *l; l != NULL; l = l->next) {
    printf("Элемент номер %zu: %d\n", i, l->value);
    i++;
  }

Все галочки помечены, то есть связный список — это список. Как неожиданно.

## 3. Зачем
Ну да, действительно, зачем вообще такая дрянь, когда есть обычный массив?

Плюсы:

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

Но есть другие!

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

- **Добавление и удаление элементов** на самом деле — **долгая операция**.
Как минимум, пока у нас в списке не десятки тысяч значений. Потому что мы юзаем `malloc`. Нужно тыкать в операционную систему, чтобы она нам скачала ещё немного памяти. А тыкать — это долго и больно.

Массив, если он сделан добротно хорошим программистом, просит большие куски памяти, сразу на несколько элементов. Поэтому `malloc` юзается реже. А двигать память — это дело десятое, делается быстро.

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

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

В массиве же просто множим индекс на размер элемента и получаем адрес в памяти. Быстро, удобно, меньше кода писать.

- **На `next` расходуется память.**
Ладно там, если значение занимает байт сотню. Восемь байт цеплять дополнительно — мелочь. Но инты так хранить — это уже в 2 раза больше памяти требуется, чем массиву. А чары какие-нибудь — вообще в 9.

Короче говоря, незачем. Связные списки можно отправить в топку. Почти всегда массивы справляются лучше или так же.

## P. S. Про двусвязные списки
Есть такие штуки — двусвязные списки. Это значит, что они тратят память ещё и на указатель на предыдущий элемент. С его помощью можно бегать против всех, в сторону начала, по списочку. Может быть полезно.