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

Односвязный список – это динамическая структура данных, элементы которой содержат ссылку на следующий элемент. Последний элемент имеет в качестве ссылки NULL. Для доступа к списку используется указатель на первый элемент.

1. Работа со списком занимает гораздо меньше времени, чем с массивом
2. Списки можно нарисовать на бумаге, тем самым наглядно понять механизм работы
3. Списки можно определить рекурсивно

Односвязный список состоит из узлов. Каждый узел содержит в себе указатель на следующий узел (элемент списка) и хранимое значение. Узлы представляются в качестве структуры:

typedef struct Node
{
int value;
struct Node *next;
} Spisok;

• Используем typedef для создания нового типа, чтобы в дальнейшем не писать слово struct.
• int value — хранимое значение, может быть любого типа.
• struct Node *next —  указатель на следующий узел списка.
• Spisok — название структуры.

Инициализируем список

Spisok *create(int data)
{
// Выделение памяти под корень списка
Spisok *tmp = (Spisok*)malloc(sizeof(Spisok));
// Присваивание значения узлу
tmp -> value = data;
// Присваивание указателю на следующий элемент значения NULL
tmp -> next = NULL;
return(tmp);
}

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

Добавим узел в начало списка

Spisok *add_element_start(int data, Spisok *head)
{
// Выделение памяти под узел списка
Spisok *tmp = (Spisok*)malloc(sizeof(Spisok));
// Присваивание значения узлу
tmp -> value = data;
// Присваивание указателю на следующий элемент значения указателя на «голову» 
// первоначального списка
tmp -> next = head;
return(tmp);
}

Добавим узел в конец списка

void add_element_end(int data, Spisok *head)
{
// Выделение памяти под корень списка
Spisok *tmp = (Spisok*)malloc(sizeof(Spisok));
// Присваивание значения узлу
tmp -> value = data;
// Присваивание указателю на следующий элемент значения NULL
tmp -> next = NULL;
// Присваивание новому указателю указателя head. 
// Присваивание выполняется для того, чтобы не потерять указатель на «голову» списка
Spisok *p = head;
// Сдвиг указателя p в самый конец первоначального списка
while (p -> next != NULL)
p = p -> next;
// Присваивание указателю p -> next значения указателя tmp (созданный новый узел)
p -> next = tmp;
}

• p -> next имеет значение NULL, так как указатель p расположен в конце списка. Указатель tmp ссылается на только что созданный узел, который мы хотим добавить в конец списка. Следовательно, нужно сделать так, чтобы последний элемент текущего списка ссылался на добавляемый узел (а не на NULL). Именно для этого используется строчка p -> next = tmp.
• Мы не проверяем список на пустоту, так как ранее список был инициализирован (имеется заглавное звено).

Добавим узел в определенное место списка

Spisok *add_element_n_position(int data, int n, Spisok *head)
{
// Присваивание новому указателю указателя head. 
// Присваивание выполняется для того, чтобы не потерять указатель на «голову» списка
Spisok *p = head;
// Счетчик
int count = 1;
// Поиск позиции n
while (count < n - 1 && p -> next != NULL)
{
p = p -> next;
count++;
}
// Выделение памяти под узел списка
Spisok *tmp = (Spisok*)malloc(sizeof(Spisok));
// Присваивание значения узлу
tmp -> value = data;
// Присваивание указателю tmp -> next значения указателя p -> next 
// (созданный новый узел)
tmp -> next = p -> next;
// Присваивание указателю p -> next значения указателя tmp (созданный новый узел)
p -> next = tmp;
return head;
}

• Рассмотрим пример для того, чтобы лучше понять принцип работы данной функции. Имеем следующий список: 1 2 3 4 5 6 7 8 9. Например, нам нужно в пятую позицию добавить элемент 10. Сдвигаем указатель p до 4 элемента (это выполняется в цикле while). Указателю на следующий элемент для нового узла присваиваем значение p -> next [строчка tmp -> next = p -> next] (после четвертого элемента идет пятый, но мы на 5 позицию вставляем новый узел списка, он должен ссылаться на «старый» пятый элемент, чтобы «цепочка» из указателей не прерывалась после вставки нового элемента).
• Мы «соединили» новый узел с элементами, которые следуют после пятой позиции, то есть имеем следующие: 10 5 6 7 8 9. Однако нам нужно «присоединить» предшествующие элементы. Для этого указателю на следующий элемент для четвертого узла присваиваем значение tmp. То есть теперь p -> next [строчка p -> next = tmp] ссылается не на элемент со значением 5, а на новый узел с параметром 10. А узел со значением 10 (то есть узел, который мы добавляем в список), в свою очередь, ссылается на элемент c параметром 5, который ссылается на элемент со значением 6 и так далее.

Удалим весь список

Spisok *remove_all(Spisok *head)
{
// Сдвиг указателя head в самый конец первоначального списка
while (head != NULL)
{
// Присваивание новому указателю указателя head
Spisok *p = head;
head = head -> next;
// Освобождение памяти для указателя p
free(p);
}
return NULL;
}

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

Удалим определенный узел списка

Spisok *remove_element(int data, Spisok *head)
{
// Присваивание новому указателю  tmp указателя head, p - NULL
Spisok *tmp = head, *p = NULL;
// Проверка списка на пустоту
if (head == NULL)
return NULL;
// Если список не пуст, поиск указателя на искомый элемент
while (tmp && tmp -> value != data)
{
p = tmp;
tmp = tmp -> next;
}
// Если удаляемый элемент первый
if (tmp == head)
{
free(head);
return tmp -> next;
}
// Если в списке нет искомого элемента, то возвращаем первоначальный список
if (!tmp)
return head;
// Присваивание новому указателю указателя tmp
p -> next = tmp -> next;
// Освобождение памяти для указателя tmp
free(tmp);
return head;
}

В данной функции используется принцип функции удаления всего списка и добавления нового элемента в n-ую позицию (конечно, никакого добавления нового узла нет, но здесь мы связываем элемент до удаляемого узла с элементом, расположенным после удаляемого узла).

Вывод элементов списка

Рассмотрим простейший способ вывода элементов списка:

while (tmp != NULL)
{
// Вывод значения узла
printf("%d ", tmp -> value);
// Сдвиг указателя к следующему узлу
tmp = tmp -> next;
}

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