Алгоритм инверсии двусвязного списка

8 мая 2023

Содержание

Структура элемента
Структура списка
Вспомогательные методы
Реализация алгоритма
Проверяем работу алгоритма

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

Структура элемента

Класс Node, представляющий собой один элемент списка, выглядит следующим образом:

class Node {
    int value;
    Node next; // всегда null у последнего элемента
    Node prev; // всегда null у первого элемента

    Node(int value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

Он содержит само значение элемента (в данном случае целое число) и указатели на предыдущий и следующий элемент. У первого и последнего элемента один из соответствующих указателей равен null.

Структура списка

Теперь создадим класс двусвязного списка DoublyLinkedList. Он содержит указатель на первый элемент head и на последний tail.

class DoublyLinkedList {
    private Node head;
    private Node tail;
    // ...
}

Вспомогательные методы

В этот класс добавим ряд вспомогательных методов.

public void printList() {
    Node current = head;
    while (current != null) {
        System.out.print(current.value);
        System.out.print(' ');
        current = current.next;
    }
    System.out.println();
}

Метод printList() последовательно проходится по всем элементам, начиная с head. На каждой итерации он выводит числовое значение текущего элемента.

public void insert(int value) {
    var node = new Node(value);
    if (head == null) {
        head = node;
    } else {
        tail.next = node;
        node.prev = tail;
    }
    tail = node;
}

Метод insert() создаёт новый элемент, инициализирует его указанным значением и добавляет в конец списка. Также мы выполняем проверку, не является ли список пустым? Если он пустой, то также надо инициализировать head. Но в любом случае в конце меняем указатель tail на новый элемент.

Реализация алгоритма

Теперь перейдём к реализации метода reverse(). Он должен изменить порядок следования элементов в исходном списке. То есть последний должен стать первым, предпоследний – вторым и т.п.

public void reverse() {
    Node current = head;
    Node temp;

    while (current != null) {
        temp = current.next;
        current.next = current.prev;
        if (temp != null) {
            current.prev = temp;
            current = temp;
        } else {
            current.prev = null;
            current = null;
        }
    }

    temp = head;
    head = tail;
    tail = temp;
}

Алгоритм инверсии двусвязного списка состоит из нескольких шагов.

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

После выхода из цикла head становится равным tail, затем tail становится равным текущему элементу, который окажется во временной переменной.

Проверяем работу алгоритма

Теперь мы можем проверить, насколько корректно инвертируется наш список. Напишем простенький код для демонстрации:

public static void main(String[] args) {
    var list = new DoublyLinkedList();
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.printList();

    list.reverse(); // инвертируется исходный список
    list.printList();
}

В результате в консоли увидим следующее:

1 2 3 4
4 3 2 1

То есть наш список из четырёх элементов инвертируется корректно.

P.S. Сравните этот алгоритм с Алгоритм инвертирования массива.

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.