Программирование Тимур 0

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии к коду
  • Рассмотрим пример для того, чтобы лучше понять принцип работы данной функции. Имеем следующий список: 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 и так далее.

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

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

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

Комментарий к коду

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

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

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

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

 

Вход
Apple Microsoft Google Samsung
  • Показать ещё
  • Сообщить об опечатке

    Текст, который будет отправлен нашим редакторам: