Мы используем куки, чтобы пользоваться сайтом
было удобно.
Список — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности. Списки бывают односвязными и двусвязными. Списки, основные их методы, преимущества и недостатки разобраны в этой статье [теория]. В данной статье реализуем двусвязный список на 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: "Почему код не работает?".
0
0
0
Мы ответим вам на
Если вы так и не получили ответ, пожалуйста, проверьте, отфильтровано ли письмо в одну из следующих стандартных папок:
0