如何在排序的双向链表中插入字符串数据？

Question

我有一个排序的双向链表，其中第一个和最后一个元素为空。这意味着当我插入值 a、b、c 时。结果应如下所示： {null, a, b, c, null}

空的排序双向链表应如下所示： {null, null} 其中第一个和最后一个元素始终为空。

问题是当我在排序的双向链表中插入数据时，数据没有正确排序，2个空值总是在列表的末尾。我怎样才能解决这个问题？

这是我当前的插入方法：

    public void addElement(String element) {

    // new node which will be inserted in the list

    Node newNode = new Node();

    newNode.data = element;

    // if the list is empty

    if (size == 0) {

        last = newNode;

        newNode.next = first;

        first = newNode;

        size++;

    } else {

        Node current = first;

        // if the element should be at the beginning of the list

        if (current.data.compareTo(element) > 0) {

            newNode.next = current;

            newNode.previous = null;

            current.previous = newNode;

            first = newNode;

        } else {

            while (current != null) {

                if (current.data.compareTo(element) <= 0) {

                    if (current.next == null) {

                        newNode.next = current.next;

                        newNode.previous = current;

                        current.next = newNode;

                        break;

                    }

                    newNode.next = current.next;

                    newNode.previous = current;

                    current.next.previous = newNode;

                    current.next = newNode;

                    break;

                } else {

                    current = current.next;

                }

            }

        }

        size++;

    }

}

Answer 1

不清楚你在代码中做了什么，所以我对其进行了一些修改并制作了更多的 OO 风格，所以这里是：class Node {&nbsp; String data;&nbsp; Node next, previous;}public class SortedDLL {&nbsp; private Node first;&nbsp; private Node last;&nbsp; private int size = 0;&nbsp; public SortedDLL() {&nbsp; &nbsp; size = 0;&nbsp; &nbsp; first = new Node();&nbsp; &nbsp; last = new Node();&nbsp; &nbsp; first.next = last;&nbsp; &nbsp; last.previous = first;&nbsp; }&nbsp; public void addElement(String element) {&nbsp; &nbsp; Node newNode = new Node();&nbsp; &nbsp; newNode.data = element;&nbsp; &nbsp; if (size == 0) {&nbsp; &nbsp; &nbsp; first.next = newNode;&nbsp; &nbsp; &nbsp; newNode.previous = first;&nbsp; &nbsp; &nbsp; newNode.next = last;&nbsp; &nbsp; &nbsp; last.previous = newNode;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; Node node = first;&nbsp; &nbsp; &nbsp; while (node.next.data != null && node.next.data.compareTo(newNode.data) < 0) {&nbsp; &nbsp; &nbsp; &nbsp; node = node.next;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; newNode.next = node.next;&nbsp; &nbsp; &nbsp; node.next.previous = newNode;&nbsp; &nbsp; &nbsp; node.next = newNode;&nbsp; &nbsp; &nbsp; newNode.previous = node;&nbsp; &nbsp; }&nbsp; &nbsp; size++;&nbsp; }&nbsp; public void print() {&nbsp; &nbsp; Node node = first;&nbsp; &nbsp; while (node != null) {&nbsp; &nbsp; &nbsp; System.out.print(node.data != null ? node.data + " " : "null ");&nbsp; &nbsp; &nbsp; node = node.next;&nbsp; &nbsp; }&nbsp; }&nbsp; public void printReverse() {&nbsp; &nbsp; Node node = last;&nbsp; &nbsp; while (node != null) {&nbsp; &nbsp; &nbsp; System.out.print(node.data != null ? node.data + " " : "null ");&nbsp; &nbsp; &nbsp; node = node.previous;&nbsp; &nbsp; }&nbsp; }&nbsp; public static void main(String[] args) {&nbsp; &nbsp; SortedDLL sortedDLL = new SortedDLL();&nbsp; &nbsp; sortedDLL.addElement("c");&nbsp; &nbsp; sortedDLL.addElement("a");&nbsp; &nbsp; sortedDLL.addElement("b");&nbsp; &nbsp; sortedDLL.addElement("c");&nbsp; &nbsp; System.out.println("list: ");&nbsp; &nbsp; sortedDLL.print();&nbsp; &nbsp; System.out.println("\nlist reverse: ");&nbsp; &nbsp; sortedDLL.printReverse();&nbsp; }输出：list:&nbsp;null a b c c null&nbsp;list reverse:&nbsp;null c c b a null

Answer 2

当 size == 0 时，问题从第一次调用开始您将第一个 null 推到最后.. 第一个节点成为新节点。然后，如果您解决此问题，您将在该行获得空指针异常：if&nbsp;(current.data.compareTo(element)&nbsp;>&nbsp;0)&nbsp;{因为 current 将是 null 并且不会有数据。您应该忽略第一个插入中的第一个 null 以及之后的每个插入。

Answer 3

根据实施情况，我认为您只是在错误的地方做正确的事。&nbsp; &nbsp; &nbsp; &nbsp; while (current != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (current.next == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.next = null;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.previous = current;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = newNode;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (current.next.data.compareTo(element) > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.next = current.next;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newNode.previous = current;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next.previous = newNode;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = newNode;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }而不是检查当前选择的节点是否更小，您需要检查之后的节点是否更大，因为这样您就可以放置节点。并且检查 current.next 是否为 null 需要在该比较之外进行。