我有一个已排序的双向链表,其中第一个和最后一个元素为空。这意味着当我插入值 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++;
}
}
最佳答案
不太清楚你的代码在做什么,所以我修改了一下,做了更多的面向对象的风格,所以这里是:
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
关于java - 如何在已排序的双向链表中插入字符串数据?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53289347/