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

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

Все фрагменты кода в этой статье доступны в моем репозитории: Github: Saaaaaad3

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

Предпосылки:

Односвязные списки: Link

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

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

Функция отображения, но с ограничениями!

В нециклическом связанном списке выполнение функции отображения происходит следующим образом:

· Проверьте, является ли заголовок нулевым или нет.

· Сделать временный головной узел.

· Итерировать до тех пор, пока не встретится нуль (следующий хвост).

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

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

· Переменная count будет хранить количество итераций

· Добавить размер списка и max (принимается как параметр). Это гарантирует, что, ПО КРАЙНЕЙ МЕРЕ, полный список повторен.

Запускайте цикл while до тех пор, пока не встретится нуль (в случае, если список не круговой) и значение счетчика не станет меньше size+max.

    public void DisplayWithLimit(int max){
        if(head == null){
            System.out.println("List is Empty");
            return;
        }
        Node tempNode = head;
        int count = 0;

        while(tempNode != null && size + max > count){
            if(tempNode == tail){
                System.out.print("'"+tempNode.value+"'" + "->");
            }
            else {
                System.out.print(tempNode.value + "->");
            }
            tempNode = tempNode.next;
            count++;
        }
        System.out.print("End");
        System.out.println();
    }

Проверка цикла

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

Для этого мы можем использовать алгоритм поиска цикла Флойда или известный как алгоритм зайца-черепахи.

· В этом подходе у нас есть два указателя, скажем, FastPntr и SlowPntr

· FastPntr перемещается, пропуская 1 узел, а SlowPntr перемещается от узла к узлу.

· Если существует цикл, то обе точки со временем встретятся в общем узле.

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

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

    public boolean CycleExists() {
        if (head == null) {
            System.out.println("List is Empty");
            return false;
        }
        return PointersMeet(head) != null;
    }
    private Node PointersMeet(Node head) {
        Node fastPtnr = head;
        Node slowPtnr = head;

        do {
            if (fastPtnr.next == null || fastPtnr.next.next == null) {
                return null;
            }

            slowPtnr = slowPtnr.next;
            fastPtnr = fastPtnr.next.next;
        }
        while (slowPtnr != fastPtnr);

        return slowPtnr;
    }

Создать цикл в нециклическом связанном списке

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

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

    public void makeCycleAt(int index){
        if(head == null){
            System.out.println("List is Empty");
            return;
        }
        if(CycleExists()){
            System.out.println("Cycle Already Exists");
            return;
        }
        int count = 0;
        Node tempNode = head;

        while(count < index){
            tempNode = tempNode.next;
            count++;
        }
        tail.next = tempNode;
        cycleHead = tempNode;
    }

Небольшой совет: точно так же, как мы поддерживаем указатели на начало и конец, мы также можем добавить CycleHead, который будет содержать узел, с которого начинается цикл. Это улучшит временную сложность функций, которым может потребоваться начало цикла, поскольку нам не нужно будет запускать другую функцию с циклом, чтобы определить начало цикла.

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

tail.next = null;

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

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

Все фрагменты кода в этой статье доступны в моем репозитории: Github: Saaaaaad3