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

Question

我正在尝试创建一个排序的链表。 addElement 和removeElement 方法几乎按其应有的方式工作，只是addElement 方法并不总是以正确的顺序插入元素。

这是我到目前为止的代码:

public class SortedLinkedList {

// Node class
class Node {
    public String data;
    public Node next;
}

// attributes
private Node first;
private int size;

public SortedLinkedList() {
    first = null;
}

public void addElement(String element) {
    if (first == null) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = null;
        first = newNode;

        size++;

    } else if (first.toString().compareTo(element) > 0) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = first;
        first = newNode;

        size++;

    } else {
        Node before = first;
        Node after = first.next;

        while (first.next != null) {
            Node newNode = new Node();
            newNode.data = element;

            if (after.toString().compareTo(element) > 0) {

                before.next = newNode;
                newNode.next = after;
            }

            before = after;
            after = after.next;
        }

        size++;
    }
}

public boolean removeElement(String element) {
    boolean removed = false;

    try {
        if (first.data.toString().equals(element)) {
            first = first.next;
            removed = true;

        } else {
            Node before = first;
            Node after = first.next;

            while (first.next != null) {
                if (after.data.toString().compareTo(element) == 0) {

                    before.next = after.next;
                    break;
                }

                before = after;
                after = after.next;
            }

            size--;
            removed = true;
        }
    } catch (NullPointerException e) {
        removed = false;
    }
    return removed;
}

public int countElements() {
    return size;
}

@Override
public String toString() {

String result = "{";
Node current = this.first;

while (current != null) {
    if (current.next != null) {
        result = result + current.data.toString() + ", ";
    } else {
        result = result + current.data.toString();
    }
    current = current.next;
}

result = result + "}";

return result;
}

例如，我尝试插入值:'b，a，d，c'，输出为:'c，d，a，b'，但它应该是'a，b，c，d' 。我真的看不出我做错了什么。

如有任何帮助，我们将不胜感激!

Answer 1

您有各种小问题。

1. 您正在比较 Node 而不是 Node 的数据。
2. 您的 while 循环正在循环 while (first.next != null)。这不应该检查之前或之后吗？
3. 为什么要在 while 循环中创建新的 Node？

您可以像这样更改节点:

class Node implements Comparable<Node> {
    private final String data; //once initialised shouldn't change
    private Node next; //this can change

    public Node(String data) {
       this.data = data;
    }

    public Node getNext() {
      return next;
    }

    public void setNext(Node next) {
      this.next = next;
    }

    public int  compareTo(Node that) {
      return this.data.compareTo(that.data);
    }
}

在您的 addElement(String element) 中，我会在 if 条件之前立即执行以下操作，它们都是相同的:

Node newNode = new Node(element);
size++;

最后一种情况下的 while 循环可以是:

 Node after = first;

 while ((after != null) && (after.compareTo(newNode) <= 0)) {
     //we traverse to the next 
     before = after;
     after = after.getNext();
 }

 //either we found the spot, or it is the last element in the list
 before.setNext(newNode);
 newNode.setNext(after);

您可能还可以包括新节点也应插入列表头部的情况...但我将其留给您。