Автор оригинала: Pankaj Kumar.

Круговые связанные списки в Python

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

Предварительный реквизит: понимание связанного списка

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

Связанный список – это список, в котором элементы списка связаны с другими элементами списка определенным образом. Различные формы связанных списков имеют разные способы связывания объектов.

«Одно связанный список» или просто «связанный список» – самый популярный связанный список, в котором каждый элемент ссылается на следующий элемент в списке. Итак, чтобы добраться до десятого предмета, мы должны сначала добраться до девятого предмета, который связан с десятым предметом. И как только мы добрались до десятого предмета, мы сможем получить доступ к одиннадцатому пункту через соединение десятого предмета.

Узел – это имя, данное каждому объекту в связанном списке. Каждый узел в одиночном списке имеет два компонента. Первая часть содержит данные узла, а вторая содержит ссылку на следующий узел.

Давайте посмотрим на круговые связанные списки сейчас.

Круговые связанные списки в Python

Круговой связанный список аналогичен связанному списку, в том, что узлы подключаются к ссылкам, но последний узел также связан с первым узлом вместо того, чтобы просто связаться с ним. Итак, после того, как мы добрались до последнего узла, мы можем получить доступ к первому узлу через последний узел.

Способ сделать это просто вместо того, чтобы держать ссылку последнего узла как Нет вместо этого сделайте его указывать на первый узел.

Преимущество этого заключается в том, что это облегчает реализацию алгоритмов, которые имеют список предметов, которые входят круговой способ. Например, алгоритм планирования Round-Robin или игрок включает в себя многопользовательскую игру, являются круговыми в природе.

Визуализировать, круговой связанный список выглядит что-то подобное:

В приведенном выше примере вы можете увидеть, что в списке есть четыре узла. Каждый узел имеет некоторые данные, и каждый узел ссылается на следующий узел списка, кроме последнего узла, который ссылается на первый узел списка.

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

Рекомендуется прочитать – Вдвойне связанные списки

Реализация циркулярных связанных списков в Python

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

Класс: узел

Для класса узла у нас есть два члена. Один для хранения данных и другой для хранения ссылки на следующий узел. Определение класса будет:

class Node:
    def __init__(self, data = None):
        self.data = data
        self.next = self

Таким образом, изначально каждый новый созданный узел будет иметь или не будет иметь значение данных в зависимости от того, как оно было создано, но он будет указывать на себя по умолчанию, чтобы он был как единый элемент круговой связанный список.

Класс: круговой связанный список

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

class CLL:
    def __init__(self):
        self.head = None
        self.count = 0
    
    def __repr__(self):
        string = ""
         
        if(self.head == None):
            string += "Circular Linked List Empty"
            return string
         
        string += f"Circular Linked List:\n{self.head.data}"       
        temp = self.head.next
        while(temp != self.head):
            string += f" -> {temp.data}"
            temp = temp.next
        return string
    
    def append(self, data):
        self.insert(data, self.count)
        return
    
    def insert(self, data, index):
        if (index > self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
            
        if self.head == None:
            self.head = Node(data)
            self.count += 1
            return
        
        temp = self.head
        for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
            temp = temp.next
            
        aftertemp = temp.next #New node goes between temp and aftertemp
        temp.next = Node(data)
        temp.next.next = aftertemp
        if(index == 0):
            self.head = temp.next
        self.count += 1
        return
    
    def remove(self, index):
        if (index >= self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
        
        if self.count == 1:
            self.head = None
            self.count = 0
            return
        
        before = self.head
        for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
            before = before.next
        after = before.next.next
        
        before.next = after
        if(index == 0):
            self.head = after
        self.count -= 1
        return
    
    def index(self, data):
        temp = self.head
        for i in range(self.count):
            if(temp.data == data):
                return i
            temp = temp.next
        return None
    
    def size(self):
        return self.count
    
    def display(self):
        print(self)

Давайте обсудим методы, написанные выше.

То __в этом__ метод

В конструкторе мы инициализируем два члена, мы устанавливаем голова как Нет Потому что в списке нет узлов, и мы устанавливаем Считать как 0 по той же причине.

То __repr__ метод

Строка, которая распечатает связанный список, будет возвращена __repr__ процесс. Таким образом, либо список пусто, в этом случае мы распечатаем это, либо список не пусто, в этом случае мы распечатаем данные каждого узла один за другим.

То присоединиться к а также вставлять метод

Узлы могут быть добавлены или вставлены в указанное положение в этой реализации. Чтобы добавить, мы просто называем Вставить Способ и отправьте размер списка как индекс Отказ

В Вставить Способ, мы сначала проверяем, если указанный индекс действителен или нет, если нет, мы бросаем ValueError Отказ После прохождения проверки, если список пуст, мы просто назначаем новый узел для голова , увеличить Считать и вернуться из способа.

Если список не пусто, мы сначала добраться до узла до указанного индекса. Например, если данный индекс 5, то мы достигаем узла в 4-м индексе, и поскольку список является круговым, если данный индекс равен 0, то мы достигаем последнего узла списка.

Теперь мы назначаем новый узел Следующий из узла до указанного индекса, и мы делаем новый узел Следующий Ссылка на узел по указанному индексу. Это удостоверится, что новый узел вставлен перед узлом, который был в указанном индексе, и, следовательно, принял свой индекс и подтолкнул его вперед.

Теперь, если данный индекс был 0, мы вставили узел после последнего узла списка, поэтому мы просто делаем голова Укажите на новый узел, что делает его новым главой списка.

То Удалить метод

Чтобы удалить элемент, который мы должны указывать, где элемент должен быть удален. Если указанный индекс вне диапазона, мы поднимаем ValueError Отказ Если в списке есть только один элемент, мы просто делаем голова Нет и Считать 0 и вернуться из способа.

В противном случае мы должны добраться до узла до указанного индекса и узла после указанного индекса. Например, если указанный индекс 4, то нам нужно добраться до 3-го узла и 5-го узла, и поскольку список является круговым, если указанный индекс равен 0, нам нужно добраться до последнего узла (до него) и 1-й узел (после этого).

После этого мы просто назначаем узел после указанного индекса для Следующий у узла до указанного индекса. Это будет пропустить узел по указанному индексу, поэтому удаляет его из списка. Если указанный индекс 0, то голова Был удален из списка, поэтому мы просто должны назначить узел, который был после указанного индекса для голова И список будет восстановлен. Не забудьте уменьшить Считать списка.

Индекс, размер и метод отображения

индекс Метод поиска элемента в списке. Если найдено, он возвращает свой индекс, в противном случае он возвращает Нет Отказ Размер Метод возвращает количество узлов в списке, а Дисплей Метод печатает список.

Выход

Заключение

Мы узнали о круговых связанных списках и как их использовать в Python. Мы начали, посмотрев на то, как работает по отдельно связанным списком, затем перемещается к тому, как круговой связанный список отличается. Мы написали код структуры данных в Python, обсудили, как работает каждый метод, а затем рассматривает результаты кода.

Я надеюсь, что у вас было отличное время обучения, и увидимся в следующем руководстве.