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

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

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

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

然后，如果您修复此问题，您将在该行出现空指针异常：

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

因为current将为null，不会有数据。

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

Answer 2

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

        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 需要在该比较之外完成。

Answer 3

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

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

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

How to insert String data in a sorted doubly linked list?

java

doubly-linked-list