java - 反转双向链表

Question

嘿，我目前卡在我的 DoublyLinkedList 的反向方法上。除了反向方法外，一切都工作正常(不知何故)。我没有收到任何错误 - System.out.println(list.reverse()) 只是没有输出。

有什么建议吗？非常感谢你提前。 :)

好的:我现在已经编辑了我的代码。到目前为止一切正常。然而，递归方法只是简单地以相同的顺序打印列表，而不是实际颠倒它。

更新代码:

public class DoublyLinkedStringList {

private String content;
private DoublyLinkedStringList prev;
private DoublyLinkedStringList next;

public DoublyLinkedStringList(String info) {
    content = info;
    prev = null;
    next = null;
}

private DoublyLinkedStringList(String content, DoublyLinkedStringList prev, DoublyLinkedStringList next) {
    this.content = content;
    this.prev = prev;
    this.next = next;
}

public DoublyLinkedStringList prepend(String info) {
    DoublyLinkedStringList newNode = new DoublyLinkedStringList(info);
    prev = newNode;
    newNode.next = this;

    return newNode;
}

public DoublyLinkedStringList delete(int index) {
    DoublyLinkedStringList curr = this;

    if (index == 0) {
        next.prev = null;
        return next;
    }

    for (int i = 0; i < index; i++) {
        curr = curr.next;
    }

    curr.prev.next = curr.next;
    if (curr.prev.next != null) {              
        curr.prev.next.prev = curr.prev;
    }
    return this;
}

public DoublyLinkedStringList reverse() {
    DoublyLinkedStringList currNode = this;

    while (currNode != null) {
        DoublyLinkedStringList temp = currNode.next;
        currNode.next = currNode.prev;
        currNode.prev = temp;

        if (currNode.prev != null) {
            currNode = currNode.prev;
        }
    }

    return this;
}

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();

    for (DoublyLinkedStringList currNode = this; currNode != null; currNode = currNode.next) {
        sb.append(currNode.content);
        if (currNode.next != null) {
            sb.append(", ");
        }
    }
    return sb.toString();
}

public static void main(String argv[]) {
    DoublyLinkedStringList list = new DoublyLinkedStringList("Testliste");
    list = list.prepend("6");
    list = list.prepend("5");
    list = list.prepend("4");
    list = list.prepend("3");
    list = list.prepend("2");
    list = list.prepend("1");
    list = list.prepend("0");

    list = list.delete(1);
    System.out.println(list);

    list = list.reverse();
    System.out.println(list);
}

Answer 1

您的设计将遇到的一个问题是，当您反转列表时，头部变成尾部，尾部变成头部。但是客户指向的是头部，而不是尾部。即使您 100% 正确地执行了此操作，您也无法更改客户端拥有的引用。您要做的是将 List 作为对象的概念与构成该对象的节点的概念分开(目前您已将这两个概念组合在一起，因为节点是列表，反之亦然)。通过将它们分开，对列表的引用总是相同的，无论列表中的内容、顺序等如何。列表包含头和尾引用，节点仅包含下一个/上一个。现在您在列表中的每个节点中都有头部和尾部，如果您不在头部/尾部更改(即添加、删除或反转)时不替换每个引用，就会弹出讨厌的错误。如果您将这两个实例移出每个节点，那么您就不必对更改列表进行太多维护。我认为，如果您这样做，您会发现实现反向操作要容易得多。

您的错误正是我要说的问题。最后你返回这个，客户的引用是头部(即这个)。但是，在遍历并反转所有内容之后，头部现在变成了尾部，因此您通过返回它返回了新的尾部。尾部的 toString() 什么也不是。