Двусвязные списки

Двусвязные списки

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

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

Необходимые условия:

Односвязные списки — Ссылка

Приступаем!

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

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

Однако двусвязные списки устраняют это ограничение, поскольку они вводят второй указатель с именем «Prev», сокращение от «Previous». Подобно тому, как next указывает на следующий узел в последовательности, prev указывает на узел, предшествующий нашему текущему узлу.

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

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

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

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

Если хвост не нулевой, мы можем объявить узел tempHead и назначить ему наш хвостовой узел. Оттуда мы можем использовать указатель prev для перехода, пока не достигнем нуля (prev of head node).

public void DisplayReverse(){
    if(tail == null){
        System.out.println("List is Empty");
    }

    ListNode tempHead = tail;

    while(tempHead != null){
        System.out.print(tempHead.value + "->");
        tempHead = tempHead.prev;
    }
    System.out.println("End");
}

Вставка с самого начала!

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

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

Проверьте, если голова пуста, объявите новый узел как голову

Наведите новый узел рядом с головой.

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

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

public void insertFirst(int num){
    ListNode node = new ListNode(num);

    if(head == null){
        head = node;
        tail = node;
        size--;
        return;
    }
    node.next = head;
    head.prev = node;
    head = node;
    head.prev = null;

    size++;
}

Наконец-то вставка!

Проверяем, является ли заголовок нулевым, это указывает на то, что список пуст, в этом случае мы можем просто вызвать функцию insertFirst(), которую мы написали выше.

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

Направьте prev нового узла на хвост, это поместит наш новый узел в конец списка.

Направьте следующий хвостовой узел на наш «узел». Это укрепляет положение нашего нового узла в конце.

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

public void insertLast(int num) {
    ListNode node = new ListNode(num);
    if(head == null){
        insertFirst(num);
        return;
    }
    if(tail != null){
        node.prev = tail;
        tail.next = node;
        node.next = null;
        tail = node;
    }
    size++;
}

Удаление узлов Head или Tail

Функции удаления для DeleteFirst и DeleteLast одинаковые и самые простые, поскольку вам нужно только проверить, являются ли они нулевыми, и повторно объявить головной или хвостовой узел соответственно.

public void DeleteFirst(){
    if(head == null){
        System.out.println("The List is Empty");
        return;
    }
    head = head.next;
    size--;
}

В DeleteLast вместо обхода всей функции мы можем использовать указатель prev для повторного объявления хвостового узла.

public void DeleteLast(){
    if(tail == null){
        System.out.println("The List is Empty");
        return;
    }
    tail = tail.prev;
    size--;
}

Удаление узла на основе значения

Мы запустим цикл do-while и на каждой итерации будем сравнивать «число» со значением tempHead.

Если приведенное выше условие верно, мы и наша tempHead такая же, как голова, тогда мы можем вызвать функцию DeleteFirst. То же самое относится и к случаю, когда tempHead совпадает с хвостовым узлом, мы можем вызвать функцию DeleteLast.

Если два приведенных выше случая ложны и мы встречаем узел со значением, которое нужно удалить, в середине последовательности, что означает

tempHead.value == число.

Мы можем назначить,

следующий из предыдущего tempHead к следующему из tempHead и

от предыдущего следующего tempHead до предыдущего tempHead. (наоборот).

public void Delete(int num){
    if(head == null){
        System.out.println("The List is Empty");
    }
    ListNode tempHead = head;

    do{
        if(tempHead.value == num){
            if(tempHead == head){
                DeleteFirst();
                size--;
                return;
            }
            if(tempHead == tail){
                DeleteLast();
                size--;
                return;
            }
            tempHead.prev.next = tempHead.next;
            tempHead.next.prev = tempHead.prev;
        }
        tempHead = tempHead.next;
    }
    while(tempHead != null);
    size--;
}

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

Далее мы рассмотрим круговые связанные списки!

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