21 Июн 2023

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

21 Июн 2023

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

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

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

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

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

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

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

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

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

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

int initialize_list(single_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 указатель на список list. Не забываем обновить указатель last в случае, если до вставки он был нулевым (вставляли в пустой список).

int add_item_to_begin(single_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->data = item;
  newNode->next = list->head;

  list->head = newNode;
  if (list->tail == NULL)
  {
    list->tail = newNode;
  }

  return 0;
}

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

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

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

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

  if (list->tail == NULL)
  {
    return add_item_to_begin(list, item);
  }

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

  list->tail->next = newNode;
  list->tail = newNode;
  return 0;
}

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

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

int add_item_after(single_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->data = item;
  
  newNode->next = pos->next;
  pos->next = newNode;

  return 0;
}

Обход

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

void print_list(single_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(single_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_after. Для удаления узла нужно обновить указатель next у узла:

int delete_item_after(single_linked_list_t *list, node_t *node)
{
  if (list == NULL || list->head == NULL) return -1;
  if (node == NULL)
  {
    list->head = list->head->next;
    free(list->head);
    return 0;
  };

  if (node->next == NULL) return -3;
  node_t* nodeToDelete = node->next;
  node->next = node->next->next;

  free(nodeToDelete);
  return 0;
}

Здесь есть один особый нюанс — удаление первого узла. У него нет предыдущего узла, поэтому данный случай обрабатываем отдельно.

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

int delete_list(forward_list_t list)
{
  if (list.head == NULL || list.tail == NULL) return -1;

  node_t *current = list.head;
  node_t *next;

  while (current)
  {
    next = current->next;
    free(current);
    current = next;
  }

  return 0;
}

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

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

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

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

node_t* find_item(DoubleLinkedList 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>:125:1: warning: V1044 Loop break conditions do not depend on the number of iterations.

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

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

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

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

Вывод

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

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