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