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

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

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

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

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

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

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

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

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

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

```cpp
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_ в случае, если до вставки он был нулевым \(вставляли в пустой список\)\.

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

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

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

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

### Поиск

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

```cpp
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_ у узла:

```cpp
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_\. Для этого надо проитерироваться по всему списку, начиная с головы, пока не достигнем нулевого указателя:

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

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

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

```cpp
node_t* find_item(DoubleLinkedList 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/6Mfx3ejKv):

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

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

Действительно, условие цикла _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/6682/)
* [Реализация двусвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6683/)
* [Реализация односвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6684/)