# Реализация двусвязного списка на C

[Список](https://pvs-studio.ru/ru/blog/terms/6681/) — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности\. Списки бывают односвязными и двусвязными\. Списки, основные их методы, преимущества и недостатки разобраны в этой статье \[теория\]\. В данной статье реализуем двусвязный список на C\. Полный код можно посмотреть [здесь](https://godbolt.org/z/11ePK7f5b)\.

## Структура списка

Двусвязный список состоит из узлов\. В каждом узле хранится указатель на следующий узел, указатель на предыдущий узел и сами данные:

```cpp
typedef struct node_t
{
  struct node_t *next;
  struct node_t *prev;
  int data;
} node_t;
```

Список — это просто указатель на первый и последний узлы:

```cpp
typedef struct double_linked_list_t
{
  node_t *head;
  node_t *tail;
} double_linked_list_t;
```

## Функции списка

### Инициализация

Для инициализации используем функцию _add\_item\_to\_end_, которая вставляет элемент в конец списка\. В инициализирующую функцию нужно передать указатель на список, количество элементов и сами элементы:

```cpp
int initialize_list(double_linked_list_t *list, int count, ...)
{
  list->head = list->tail = NULL;

  va_list number;
  va_start(number, count);
  for (int i = 0; i < count; ++i)
  {
    add_item_to_end(list, va_arg(number, int));
  }

  va_end(number);

  return 0;
}
```

### Вставка в начало

Для вставки элемента в начало списка создаём новый узел\. Следующим после него становится узел, бывший до вставки первым\. Также нужно обновить указатель на первый узел, поэтому передаем в функцию _add\_item\_to\_begin_ указатель на список\. Не забываем обновить указатель _last_ в случае вставки в пустой список\. 

```cpp
int add_item_to_begin(double_linked_list_t *list, int item)
{
  if (list == NULL) return -1;

  node_t *newNode = (node_t*) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;

  newNode->prev = newNode->next = NULL;
  newNode->data = item;

  if (list->head)
  {
    list->head->prev = newNode;
    newNode->next = list->head;
    list->head = newNode;
  }
  else 
  {
    list->head = list->tail = newNode;
  }

  return 0;
}
```



### Вставка в конец

Если исходный список пустой, то вставка в конец — это то же самое, что и вставка в начало, в таком случае вызываем уже реализованную ранее функцию _add\_item\_to\_begin_\.

В непустом списке вставляем новый узел после последнего узла, на него указывает _last\._ Создаём новый узел и вставляем его после последнего узла\.

```cpp
int add_item_to_end(double_linked_list_t *list, int item)
{
  if (list == NULL) return -1;

  node_t *newNode = (node_t *) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;
  
  newNode->prev = newNode->next = NULL;
  newNode->data = item;
  
  if (list->tail)
  {
    list->tail->next = newNode;
    newNode->prev = list->tail;
    list->tail = newNode;
  }
  else
  {
    list->head = list->tail = newNode;
  }

  return 0;
}
```

### Вставка в произвольное место списка

Для вставки в произвольное место списка используем функцию _add\_item\_before_\. Эта функция принимает в качестве аргументов указатель на список, указатель на узел, перед которым нужно выполнить вставку, и элемент, который нужно вставить:

```cpp
int add_item_before(double_linked_list_t *list, node_t *pos, int item)
{
  if (list == NULL) return -1;
  if (pos == NULL) return add_item_to_end(list, item);

  node_t *newNode = (node_t *) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;
  
  newNode->prev = newNode->next = NULL;
  newNode->data = item;
  
  newNode->next = pos;
  newNode->prev = pos->prev;

  if (pos->prev)
  {
    pos->prev->next = newNode;
  }
    
  pos->prev = newNode;

  return 0;
}
```

### Обход

Для примера обхода списка реализуем функцию _print\_list_, распечатывающую через пробел элементы списка:

```cpp
void print_list(double_linked_list_t list)
{
  node_t *current = list.head;

  fputs("[ ", stdout);

  while (current)
  {
    printf("%d ", current->data);
    current = current->next;
  }

  fputs("]\n", stdout);
  fflush(stdout);
}
```

### Поиск

Для поиска элемента просто проходим по узлам списка, пока элемент не будет найден или узлы не закончатся:

```cpp
node_t* find_item(double_linked_list_t list, int item)
{
  node_t *current = list.head;

  while (current)
  {
    if (current->data == item)
    {
      return current;
    }
    current = current->next;
  }

  return NULL;
}
```

### Удаление

Для удаления элементов реализуем функцию _delete\_item_\. Для удаления узла нужно обновить указатель _next_ у предыдущего узла списка и обновить указатель _prev_ у следующего узла:

```cpp
int delete_item(double_linked_list_t *list, node_t *node)
{
  if (node == NULL) return -1;
  if (list == NULL) return -2;

  if (node->prev)
  {
    node->prev->next = node->next;
  }
  else
  {
    list->head = node->next;
  }
  
  if (node->next)
  {
    node->next->prev = node->prev;
  }
  else
  {
    list->tail = node->prev;
  }

  free(node);
  return 0;
}
```

Здесь есть один особый нюанс — удаление первого узла\. Указатель prev у такого узла будет нулевым\. В этом случае выполнится _then_\-ветка условия _if \(node\-\>prev\)_ и будет обновлён указатель на первый узел списка _head_\.

## Потенциальные ошибки и как их избежать

Мы изучили сайт Stack Overflow, чтобы понять, с какими ошибками чаще всего сталкиваются люди при попытке реализовать списки\. Разберём несколько типовых ошибок\.

### Бесконечный цикл

Давайте рассмотрим пример ошибки:

```cpp
node_t* find_item(double_linked_list_t list, int item)
{
  node_t *current = list.head;

  while (current)
  {
    if (current->data == item)
    {
      return current;
    }
  }

  return NULL;
}
```

В данном фрагменте кода забыт переход на следующий узел списка:

```cpp
current = current->next;
```

Это достаточно частый случай, когда где\-то забывают перейти к следующему элементу списка\. Такие ошибки можно выявить более внимательным самостоятельным обзором кода\. Дополнительно для поиска этой и других ошибок вы можете использовать анализатор кода PVS\-Studio, встроенный в Compiler Explorer\. Вот что выдал анализатор на этом [примере](https://godbolt.org/z/xjfaasfcd):

<source\>:14:1: warning: V1044 Loop break conditions do not depend on the number of iterations\.

144 — это номер строки с ошибкой\.

Действительно, условие цикла _while_ будет истинным вне зависимости от количества итераций, и получится бесконечный цикл\.

### Отсутствие проверки после выделения памяти

Часто отсутствует проверка указателя, который возвращает функция _malloc_\. Функция может вернуть _NULL_ при недостатке свободной памяти\. В простых маленьких программах этого не происходит, поэтому кажется, что код написан правильно\. Однако при разработке больших программных решений проверками пренебрегать нельзя\. Подробнее эта тема рассматривается в статье "[Четыре причины проверять, что вернула функция malloc](https://pvs-studio.ru/ru/blog/posts/cpp/0938/)"\.

## Вывод

В данной статье мы разобрали, как реализовать двусвязный список на языке C\. Хорошим помощником при изучении программирования и выполнении лабораторных работ может стать сочетание [Compiler Explorer](https://godbolt.org/) и [PVS\-Studio](https://pvs-studio.ru/ru/pvs-studio/)\.

Compiler Explorer позволяет быстро проводить эксперименты с кодом прямо в браузере\. PVS\-Studio, встроенный в Compiler Explorer, поможет быстро найти многие ошибки\. См\. статью: [Тем, кто учится программировать и решил написать вопрос на Stack Overflow: "Почему код не работает?"](https://pvs-studio.ru/ru/blog/posts/cpp/0959/)\.

## Дополнительные ссылки

* [Список](https://pvs-studio.ru/ru/blog/terms/6681/)
* [Реализация двусвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6683/)
* [Реализация односвязного списка на C](https://pvs-studio.ru/ru/blog/terms/6680/)
* [Реализация односвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6684/)