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

Связный список (linked list) — это структура данных, в которой элементы линейно упорядочены, но порядок определяется не номерами элементов (как в массивах), а указателями, входящих в состав элементов списка и указывают на следующий элемент. У списка должна быть «голова» (первый элемент) и «хвост» (последний элемент).

Преимущества и недостатки по сравнению с массивами

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

Недостатком связных списков необходимость проходить весь список, чтобы найти элемент (то есть время доступа к элементу списка = О (n)).

Элемент связанного списка (узел)

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

В коде на картинке приведен код структуры, который реализует элемент связанного списка (и собственно список). Данные представлены числовым значением.

Иными словами, мы используем синтаксис структуры для создания нашего собственного типа данных для инкапсуляции узла.

int n — это данные, которые мы хотим сохранить в узле.
struct node * next — указатель на следующий узел в связанном списке.

Помните, что узел не будет typedef-ed до тех пор, пока все эти строки не будут выполнены. Таким образом, мы должны написать узел struct вместо простого узла, как перед фигурными скобками, так и внутри фигурных скобок. В самой последней строке мы предоставляем node для typedef как имя, которое мы хотим использовать для этого нового типа данных для остальной части нашей программы.

Поиск по списку

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

В этом примере для того, чтобы найти элемент «9», необходимо прежде всего с головы списка перейти на элемент «2». Затем перейти по ссылке на элемент «3». Только после этого можно по ссылке найти элемент «9».

По сути — это линейный поиск и асимптотическое время такого алгоритма равно O(n).

Ниже — код функции, которая ищет заданный элемент в списке и возвращает true, если элемент есть в списке, или false, если элемента нет в списке.

bool search (node * list, int n)
{
  node * ptr = list;
  while (ptr! = NULL)
  {
    if (ptr -> n == n)
    {
      return true;
    }
    ptr = ptr -> next;
  }
  return false;
}

Вначале ptr указывает на первый узел списка. Пока ptr! = NULL, мы будем разыменовывать его и проверять, является ли ptr-> n значением, которое мы ищем. Если это так, функция возвращает true.

Если мы еще не нашли искомое значение, ptr должен перейти к следующему узлу в списке. Чтобы направить ptr на следующий узел в списке, мы не можем просто написать ptr ++. Память в связанном списке не является непрерывной, поэтому следующий узел в списке не обязательно находится справа от того, куда указывает ptr. Вместо этого, ptr должен указывать куда указывает ptr-> next.

Если ptr достиг конца списка без поиска значения, которое мы ищем, функция возвращает false.

Вставка элемента в список

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

Рассмотрим вставку в начало списка (так как это наиболее часто используемый вариант вставки).

1. Создадим новый элемент. Он пока не ссылается на другие элементы, и на него никакой другой элемент не ссылается.
2. Переназначим указатель нового элемента так, чтобы он указывал на тот же элемент, на который указывает head.
3. Переназначим указатель head на новый элемент.

Очень важно, чтобы шаги 2 и 3 были проведены именно в таком порядке. Если сначала установить head на новый элемент, мы потеряем часть списка.

Ниже приведён код функции для вставки нового элемента в начало списка:

void insert (int n)
{
  // создать новый элемент
  node * new = malloc (sizeof (node))

  // проверка на NULL
  if (new == NULL)
  {
    exit (1);
  }

  // инициализировать новый элемент
  new-> n = n;
  new-> next = NULL;

  // вставить новый элемент в голову списка
  new-> next = head;
  head = new;
}

Таким образом, для вставки в начало связанного списка нужно:

4. Применить malloc для создания нового узла и инициализировать его данными.
5. Установить следующее поле следующего узла, чтобы указать на первый узел в списке.
6. Заставить головной элемент указывать на новый узел.

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

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

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

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

typedef struct node
{
  int n;
  struct node * next;
  struct node * prev;
} Node;