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

• Структура списка
• Функции списка
  • Инициализация
  • Вставка в начало
  • Вставка в конец
  • Вставка в произвольное место списка
  • Обход
  • Поиск
  • Удаление
• Потенциальные ошибки и как их избежать
  • Бесконечный цикл
  • Отсутствие проверки после выделения памяти
• Вывод
• Дополнительные ссылки

Список — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности. Списки бывают односвязными и двусвязными. Списки, основные их методы, преимущества и недостатки разобраны в этой статье [теория]. В данной статье реализуем двусвязный список на C. Полный код можно посмотреть здесь.

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

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

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

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

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

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

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

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

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 в случае вставки в пустой список.

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. Создаём новый узел и вставляем его после последнего узла.

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. Эта функция принимает в качестве аргументов указатель на список, указатель на узел, перед которым нужно выполнить вставку, и элемент, который нужно вставить:

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, распечатывающую через пробел элементы списка:

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);
}

Поиск

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

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 у следующего узла:

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, чтобы понять, с какими ошибками чаще всего сталкиваются люди при попытке реализовать списки. Разберём несколько типовых ошибок.

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

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

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;
}

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

current = current->next;

Это достаточно частый случай, когда где-то забывают перейти к следующему элементу списка. Такие ошибки можно выявить более внимательным самостоятельным обзором кода. Дополнительно для поиска этой и других ошибок вы можете использовать анализатор кода PVS-Studio, встроенный в Compiler Explorer. Вот что выдал анализатор на этом примере:

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

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

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

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

Часто отсутствует проверка указателя, который возвращает функция malloc. Функция может вернуть NULL при недостатке свободной памяти. В простых маленьких программах этого не происходит, поэтому кажется, что код написан правильно. Однако при разработке больших программных решений проверками пренебрегать нельзя. Подробнее эта тема рассматривается в статье "Четыре причины проверять, что вернула функция malloc".

Вывод

В данной статье мы разобрали, как реализовать двусвязный список на языке C. Хорошим помощником при изучении программирования и выполнении лабораторных работ может стать сочетание Compiler Explorer и PVS-Studio.

Compiler Explorer позволяет быстро проводить эксперименты с кодом прямо в браузере. PVS-Studio, встроенный в Compiler Explorer, поможет быстро найти многие ошибки. См. статью: Тем, кто учится программировать и решил написать вопрос на Stack Overflow: "Почему код не работает?".

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

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

0

0

0

0

ПОДЕЛИТЬСЯ

Присылаем лучшие статьи раз в месяц