Всем привет!!! Мы обсуждали основные проблемы связанных списков и концепцию двойных связанных списков в предыдущем рассказе этой серии.
Переходя к следующему шагу подготовки связанного списка, у нас есть несколько основных концепций и проблем.
Круговой связанный список
Круговой связанный список — это связанный список, в котором все узлы соединены в круг. В конце нет NULL. Циклический связанный список может быть одинарным циклическим списком или дважды циклическим связанным списком.
Преимущества круговых связанных списков:
- Любой узел может быть отправной точкой. Мы можем пройти весь список, начиная с любой точки. Нам просто нужно остановиться, когда первый посещенный узел будет снова посещен.
- Полезно для реализации очереди. В отличие от этой реализации, нам не нужно поддерживать два указателя на передний и задний, если мы используем кольцевой связанный список. Мы можем поддерживать указатель на последний вставленный узел, и фронт всегда можно получить как следующий за последним.
- Циклические списки полезны в приложениях для повторного обхода списка. Например, когда на ПК запущено несколько приложений, операционная система обычно помещает запущенные приложения в список, а затем циклически перебирает их, давая каждому из них отрезок времени для выполнения, а затем заставляя их ждать. в то время как ЦП отдается другому приложению. Для операционной системы удобно использовать круговой список, чтобы, достигнув конца списка, она могла циклически перемещаться в начало списка.
- Циклические двусвязные списки используются для реализации расширенных структур данных, таких как куча Фибоначчи.
Поскольку мы выполнили задачи легкого уровня для связанного списка, мы перейдем к вопросам среднего уровня:
- https://leetcode.com/problems/rotate-list/
- https://leetcode.com/problems/intersection-of-two-linked-lists/
- https://leetcode.com/problems/linked-list-cycle-ii/
- https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Предстоящие сообщения: размещение за пределами кампуса, DSA Day -16
