Перемещение элемента с двойной связью в конец Java

Question

Я нашел этот код для добавления элемента в начало связанного списка, но, поскольку у меня есть последний узел, он работает не совсем правильно, поэтому я немного его изменил:

    public void moveToFront(String node) {

    DoubleNode previous = first;
    temp = first;

    while (temp != null) {
        if (node.equals(temp.item)) {
            //Found the item
            previous.next = temp.next;
            temp.next = first;
            first = temp;

            if (last.next != null) {
                last = last.prev;
                last.prev = previous;
            }

            return;
        }
        previous = temp;
        temp = temp.next;
    }

if (last.next != null) спрашивает, был ли перемещен последний последний оригинал, и проверяет, есть ли у последнего последнего правильные ссылки.Теперь я думаю, что он работает правильно для моего кода.

Я хотел бы реализовать этот код, но для добавления элемента в конец.Однако последний просто не сейчас.При вызове last.prev он получает только один элемент позади него, но last.prev.prev до бесконечности - это тот же элемент.

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

public void moveToEnd(String node) {

DoubleNode previous = last;
    temp = last;
    System.out.println("last = " + last.prev.item);
    System.out.println("temp = " + temp.item);

    while (!temp.item.equals(first.item)) {

        if(node.equals(temp.item)){
            System.out.println("previous.prev = " + previous.prev.item);
        }

        previous = temp;
        temp = temp.prev;

        System.out.println("temp.prev = " + temp.prev.prev.prev.prev.prev.prev.prev.prev.prev.prev.prev.item);
    }

Вот как я реализую свой связанный список:

public class LinkedListDeque {

public DoubleNode first = new DoubleNode(null);
public DoubleNode last = new DoubleNode(null);
public DoubleNode temp;
public int N;

LinkedListDeque() {
    first.next = last;
    last.prev = first;
}

private class DoubleNode {

    String item;
    int counter = 0;
    DoubleNode next;
    DoubleNode prev;

    DoubleNode(String i) {
        this.item = i;
    }
}

Answer 1

Я нашел этот пример полного двусвязного списка.У него нет метода add to front, но он добавляется в конец связанного списка каждый раз.Надеемся, что это поможет и даст вам лучшее представление о том, как эта структура данных должна работать и функционировать.Я бы определенно проверил это в первую очередь, так как в readme для этого GitHub говорится, что ни один из кодов не был протестирован. Сорс

/*******************************************************
 *  DoublyLinkedList.java
 *  Created by Stephen Hall on 9/22/17.
 *  Copyright (c) 2017 Stephen Hall. All rights reserved.
 *  A Linked List implementation in Java
 ********************************************************/
package Lists.Doubly_Linked_List;

/**
 * Doubly linked list class
 * @param <T> Generic type
 */
public class DoublyLinkedList<T extends Comparable<T>> {
    /**
     * Node class for singly linked list
     */
    public class Node{
        /**
         * private Members
         */
        private T data;
        private Node next;
        private Node previous;

        /**
         * Node Class Constructor
         * @param data Data to be held in the Node
         */
        public Node(T data){
            this.data = data;
            next = previous = null;
        }
    }

    /**
     * Private Members
     */
    private Node head;
    private Node tail;
    private int count;

    /**
     * Linked List Constructor
     */
    public DoublyLinkedList(){
        head = tail = null;
        count = 0;
    }

    /**
     * Adds a new node into the list with the given data
     * @param data Data to add into the list
     * @return Node added into the list
     */
    public Node add(T data){
        // No data to insert into list
        if (data != null) {
            Node node = new Node(data);
            // The Linked list is empty
            if (head == null) {
                head = node;
                tail = head;
                count++;
                return node;
            }
            // Add to the end of the list
            tail.next = node;
            node.previous = tail;
            tail = node;
            count++;
            return node;
        }
        return null;
    }

    /**
     * Removes the first node in the list matching the data
     * @param data Data to remove from the list
     * @return Node removed from the list
     */
    public Node remove(T data){
        // List is empty or no data to remove
        if (head == null || data == null)
            return null;

        Node tmp = head;
        // The data to remove what found in the first Node in the list
        if(equalTo(tmp.data, data)) {
            head = head.next;
            count--;
            return tmp;
        }

        // Try to find the node in the list
        while (tmp.next != null) {
            // Node was found, Remove it from the list
            if (equalTo(tmp.next.data, data)) {
                if(tmp.next == tail){
                    tail = tmp;
                    tmp = tmp.next;
                    tail.next = null;
                    count--;
                    return tmp;
                }
                else {
                    Node node = tmp.next;
                    tmp.next = tmp.next.next;
                    tmp.next.next.previous = tmp;
                    node.next = node.previous = null;
                    count--;
                    return node;
                }
            }
            tmp = tmp.next;
        }
        // The data was not found in the list
        return null;
    }

    /**
     * Gets the first node that has the given data
     * @param data Data to find in the list
     * @return Node First node with matching data or null if no node was found
     */
    public Node find(T data){
        // No list or data to find
        if (head == null || data == null)
            return null;

        Node tmp = head;
        // Try to find the data in the list
        while(tmp != null) {
            // Data was found
            if (equalTo(tmp.data, data))
                return tmp;
            tmp = tmp.next;
        }
        // Data was not found in the list
        return null;
    }

    /**
     * Gets the node at the given index
     * @param index Index of the Node to get
     * @return Node at passed in index
     */
    public Node indexAt(int index){
        //Index was negative or larger then the amount of Nodes in the list
        if (index < 0 || index > size())
            return null;

        Node tmp = head;
        // Move to index
        for (int i = 0; i < index; i++)
            tmp = tmp.next;
        // return the node at the index position
        return tmp;
    }

    /**
     * Gets the current count of the array
     * @return Number of items in the array
     */
    public int size(){
        return count;
    }

    /**
     * Determines if a is equal to b
     * @param a: generic type to test
     * @param b: generic type to test
     * @return boolean: true|false
     */
    private boolean equalTo(T a, T b) {
        return a.compareTo(b) == 0;
    }
}

Answer 2

Проблема с вашим методом moveToFront().Это не работает, если node == first.Если узел, который необходимо переместить, является первым узлом, вы в конечном итоге устанавливаете first.next = first, что неверно.Приведенный ниже код должен работать

    public void moveToFront(DoubleNode node) {

    DoubleNode previous = first;
    temp = first;

    while (temp != null && node != first) {
        if (node.equals(temp.item)) {
            //Found the item
            previous.next = temp.next;
            temp.next = first;
            first = temp;

            if (last.next != null) {
                last = last.prev;
                last.prev = previous;
            }

            return;
        }
        previous = temp;
        temp = temp.next;
    }

Теперь перейдем к moveToLast() следующий код должен работать

public void moveToLast(DoubleNode node) {
    DoubleNode temp = first;
    DoubleNode prev = new DoubleNode(null);   //dummy sentinel node

    while (temp != null && node != last) {
         if (temp == node) {
              if (temp == first) first = temp.next;

              prev.next = temp.next;
              if (temp.next != null) temp.next.prev = prev;
              last.next = temp;
              temp.prev = last;
              last = temp;
              last.next = null;
              break;
         }

         prev = temp;
         temp = temp.next;
    }
}