Циркулярные связанные списки – это интересный вариант структуры данных традиционного связанного списка. В циклическом связанном списке последний узел указывает на первый узел, образуя цикл. Эта уникальная характеристика открывает новые возможности для эффективного обхода и манипулирования данными. В этой статье мы погрузимся в мир циклических связанных списков, изучим их свойства, преимущества и различные методы работы с ними.

1. Создание циклического связанного списка.
   Чтобы создать циклический связанный список, мы начинаем с определения структуры узла, которая содержит элемент данных и указатель на следующий узел. Указатель последнего узла устанавливается на первый узел, завершая циклическое соединение.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class CircularLinkedList:
    def __init__(self):
        self.head = None
    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

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

def traverse(self):
    if self.head is None:
        print("Circular Linked List is empty.")
        return
    temp = self.head
    while True:
        print(temp.data, end=" ")
        temp = temp.next
        if temp == self.head:
            break

3. Вставка узла в начало.
   Чтобы вставить узел в начало циклического связанного списка, мы создаем новый узел и соответствующим образом корректируем указатели.

def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        self.head.next = self.head
    else:
        temp = self.head
        while temp.next != self.head:
            temp = temp.next
        temp.next = new_node
        new_node.next = self.head
        self.head = new_node

4. Удаление узла.
   Удаление узла из циклического связанного списка включает в себя поиск узла, подлежащего удалению, и обновление указателей окружающих узлов.

def delete_node(self, key):
    if self.head is None:
        print("Circular Linked List is empty.")
        return
    if self.head.data == key:
        temp = self.head
        while temp.next != self.head:
            temp = temp.next
        temp.next = self.head.next
        self.head = self.head.next
        return
    prev = None
    curr = self.head
    while curr.next != self.head:
        if curr.data == key:
            prev.next = curr.next
            return
        prev = curr
        curr = curr.next
    if curr.data == key:
        prev.next = self.head

<ол старт="5">

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

def get_length(self):
    if self.head is None:
        return 0
    count = 0
    temp = self.head
    while True:
        count += 1
        temp = temp.next
        if temp == self.head:
            break
    return count

Циркулярные связанные списки предлагают уникальные преимущества по сравнению с традиционными связанными списками, особенно в сценариях, где требуются циклические операции. В этой статье мы рассмотрели несколько методов создания, перемещения, вставки и удаления узлов в циклическом связанном списке. Поняв эти методы, вы будете хорошо подготовлены к использованию циклических связанных списков в своих проектах по программированию, повышая эффективность и оптимизируя структуры данных.