Структура данных и алгоритмы - связанный список
Связанный список - это последовательность структур данных, которые связаны между собой ссылками.
Связанный список - это последовательность ссылок, которая содержит элементы. Каждая ссылка содержит соединение с другой ссылкой. Связанный список - вторая по популярности структура данных после массива. Ниже приведены важные термины для понимания концепции связанного списка.
Link - Каждая ссылка связанного списка может хранить данные, называемые элементом.
Next - Каждая ссылка связанного списка содержит ссылку на следующую ссылку под названием «Далее».
LinkedList - Связанный список содержит ссылку для подключения к первой ссылке под названием «Первая».
Представление в виде связанного списка
Связанный список можно представить в виде цепочки узлов, где каждый узел указывает на следующий узел.
В соответствии с приведенной выше иллюстрацией следует учитывать следующие важные моменты.
Связанный список содержит элемент ссылки, называемый первым.
Каждая ссылка содержит поле (поля) данных и поле связи с именем next.
Каждая ссылка связана со своей следующей ссылкой с помощью следующей ссылки.
Последняя ссылка содержит нулевую ссылку, обозначающую конец списка.
Типы связанных списков
Ниже приведены различные типы связанного списка.
Simple Linked List - Перемещение по пунктам только вперед.
Doubly Linked List - Элементы можно перемещать вперед и назад.
Circular Linked List - Последний элемент содержит ссылку на первый элемент как следующий, а первый элемент имеет ссылку на последний элемент как предыдущий.
Основные операции
Ниже приведены основные операции, поддерживаемые списком.
Insertion - Добавляет элемент в начало списка.
Deletion - Удаляет элемент в начале списка.
Display - Отображает полный список.
Search - Ищет элемент по заданному ключу.
Delete - Удаляет элемент по заданному ключу.
Операция вставки
Добавление нового узла в связанный список - это действие, состоящее из нескольких шагов. Мы узнаем это с помощью диаграмм здесь. Сначала создайте узел, используя ту же структуру, и найдите место, в которое он должен быть вставлен.
Представьте, что мы вставляем узел B (NewNode), между A (LeftNode) и C(Правый узел). Затем точка B. рядом с C -
NewNode.next −> RightNode;Это должно выглядеть так -
Теперь следующий узел слева должен указывать на новый узел.
LeftNode.next −> NewNode;
Это поместит новый узел посередине двух. Новый список должен выглядеть так -
Аналогичные шаги следует предпринять, если узел вставляется в начало списка. При вставке его в конец второй последний узел списка должен указывать на новый узел, а новый узел указывать на NULL.
Операция удаления
Удаление также представляет собой более чем одноэтапный процесс. Мы будем учиться с наглядным изображением. Сначала найдите целевой узел, который нужно удалить, используя алгоритмы поиска.
Левый (предыдущий) узел целевого узла теперь должен указывать на следующий узел целевого узла -
LeftNode.next −> TargetNode.next;
Это удалит ссылку, указывающую на целевой узел. Теперь, используя следующий код, мы удалим то, на что указывает целевой узел.
TargetNode.next −> NULL;
Нам нужно использовать удаленный узел. Мы можем сохранить это в памяти, иначе мы можем просто освободить память и полностью стереть целевой узел.
Обратная операция
Это тщательная операция. Нам нужно сделать так, чтобы последний узел указывал на головной узел и перевернул весь связанный список.
Сначала мы переходим к концу списка. Он должен указывать на NULL. Теперь мы укажем на предыдущий узел -
Мы должны убедиться, что последний узел не последний. Итак, у нас будет некоторый временный узел, который выглядит как головной узел, указывающий на последний узел. Теперь мы заставим все левые узлы указывать на свои предыдущие узлы один за другим.
За исключением узла (первого узла), на который указывает головной узел, все узлы должны указывать на своего предшественника, что делает их их новым преемником. Первый узел будет указывать на NULL.
Мы сделаем так, чтобы головной узел указывал на новый первый узел, используя временный узел.
Связанный список теперь перевернут. Чтобы увидеть реализацию связанного списка на языке программирования C, щелкните здесь .