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

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 {

  String data;

  Node next, previous;

}

public class SortedDLL {

  private Node first;

  private Node last;

  private int size = 0;

  public SortedDLL() {

    size = 0;

    first = new Node();

    last = new Node();

    first.next = last;

    last.previous = first;

  }

  public void addElement(String element) {

    Node newNode = new Node();

    newNode.data = element;

    if (size == 0) {

      first.next = newNode;

      newNode.previous = first;

      newNode.next = last;

      last.previous = newNode;

    } else {

      Node node = first;

      while (node.next.data != null && node.next.data.compareTo(newNode.data) < 0) {

        node = node.next;

      }

      newNode.next = node.next;

      node.next.previous = newNode;

      node.next = newNode;

      newNode.previous = node;

    }

    size++;

  }

  public void print() {

    Node node = first;

    while (node != null) {

      System.out.print(node.data != null ? node.data + " " : "null ");

      node = node.next;

    }

  }

  public void printReverse() {

    Node node = last;

    while (node != null) {

      System.out.print(node.data != null ? node.data + " " : "null ");

      node = node.previous;

    }

  }

  public static void main(String[] args) {

    SortedDLL sortedDLL = new SortedDLL();

    sortedDLL.addElement("c");

    sortedDLL.addElement("a");

    sortedDLL.addElement("b");

    sortedDLL.addElement("c");

    System.out.println("list: ");

    sortedDLL.print();

    System.out.println("\nlist reverse: ");

    sortedDLL.printReverse();

  }

输出：

list: 

null a b c c null 

list reverse: 

null c c b a null

Answer 2

当 size == 0 时，问题从第一次调用开始

您将第一个 null 推到最后.. 第一个节点成为新节点。

然后，如果您解决此问题，您将在该行获得空指针异常：

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

因为 current 将是 null 并且不会有数据。

您应该忽略第一个插入中的第一个 null 以及之后的每个插入。

Answer 3

根据实施情况，我认为您只是在错误的地方做正确的事。

        while (current != null) {

            if (current.next == null) {

                newNode.next = null;

                newNode.previous = current;

                current.next = newNode;

                break;

            }

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

                newNode.next = current.next;

                newNode.previous = current;

                current.next.previous = newNode;

                current.next = newNode;

                break;

            } else {

                current = current.next;

            }

        }

而不是检查当前选择的节点是否更小，您需要检查之后的节点是否更大，因为这样您就可以放置节点。并且检查 current.next 是否为 null 需要在该比较之外进行。