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

Question

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

空的已排序双向链表应如下所示:{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

不太清楚你的代码在做什么，所以我修改了一下，做了更多的面向对象的风格，所以这里是:

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