java - 双向链表移动项目以结束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到无穷大是同一项。

我的想法不是像 in 那样从第一个开始工作moveToFront()，而是从最后一个开始工作，然后向后逐步遍历每个节点，但是当 last 不再起作用时，显然这不起作用。

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;
    }
}

标签： javalist

Answer 1

我找到了一个完整的双向链表的这个例子。它没有添加到前面的方法，但每次都添加到链表的后面。希望它会有所帮助，并让您更好地了解该数据结构应该如何工作和运作。我肯定会首先测试它，因为它在这个 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;
    }
}