Java双向链表循环

Question

我的目标是通过我创建的列表向后循环，如果一个元素小于我选择的数字 t 一个值为 t 的节点将被插入到较小的元素。此外，如果列表中的每个元素都大于 t，则值为 t 的节点将放在列表的开头。示例：

DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

list.addAtFirstSmaller(4);
System.out.println("Nodelist: " + list.toString());

我应该期待这样的结果： [1, 2, 4, 3, 4, 5] 但是我得到： [1, 2, 3, 4, 4, 5]

到目前为止，这是我的代码：

public void addAtFirstSmaller(T t)
{
    ListNode<T> node = tail;
    ListNode<T> newNode = new ListNode<T>(t);
    while(node.previous != null)
    {
        int compared = node.previous.element.compareTo(t);
        node = node.previous;
        if(compared < 0)
        {
            ListNode<T> temp = node.next;
            node.next = newNode;
            newNode.next = temp;
            newNode.next.previous = newNode;
            node.previous = null;
            size++;
        }
        else if(compared > 0 && node.previous == null)
        {
            addFirst(t);
            size++;
        }
    }
}

对我来说似乎一切都被推到了右边。知道该怎么做吗？

Answer 1

我刚刚收到导师的答复，看来我的输出是正确的（[1, 2, 3, 4, 4, 5] 即）。当代码运行时，我会将此线程标记为已关闭。

Answer 2

正如您已经验证的那样：示例输出是正确的，因为其想法是保持列表排序。这种误解是可以理解的，因为 "在前面有点含糊不清。

但是，您的代码仍然存在一些问题：

虽然赋值 node.previous = null 会使循环在您插入新节点后结束，但这会破坏 previous link，而实际上应该保持不变。只有头节点应该 previous 等于 null，而通常 node 可以有一个前驱，它必须保持其前驱。
newNode.previous 永远不会收到值。它应该设置为 node.
当要插入的值大于尾节点中的值时，该节点将被插入到错误的位置——您的代码中永远不会出现新节点变为新的尾巴，但这是应该预见到的可能性。
我假设 addFirst 已经增加了 size，因此在调用此函数后再次增加它是错误的。这确实应该是 addFirst.
的责任

假设您已经实现了 addLast，更正后的代码可能是这样的：

public void addAtFirstSmaller(T t) {
    ListNode<T> node = tail;
    ListNode<T> newNode = new ListNode<T>(t);
    while (node != null && node.element.compareTo(t) >= 0) {
        node = node.previous;
    }
    if (node == null) {
        addFirst(t);
    } else if (node == tail) {
        addLast(t);
    } else {
        ListNode<T> temp = node.next;
        node.next = newNode;
        newNode.next = temp;
        newNode.previous = node;
        temp.previous = newNode;
        size++;
    }
}

如果您还没有，addLast 可能如下所示：

public void addLast(T t) {
    ListNode<T> newNode = new ListNode<T>(t);
    tail.next = t;
    t.previous = tail;
    tail = t;
    size++;
}

Java双向链表循环

Java doubly linked list looping

java

element

linked-list

nodes

doubly-linked-list