按字母顺序实现双链表

Question

我正在尝试在 java 中构建一个按字母顺序组织的链表，但在插入和重新排列列表的逻辑方面遇到问题，到目前为止，我的实现看起来像，数据包含一个名称获取器，它是用来组织其在列表中的位置的：

class Node
{
private Data data;
private Node nextNode;
public Node (Data data, Node nextElement)
{
this.nextNode = nextElement;
this.data = data;
}
public Node getNextNode ()
{
return nextNode;
}
public void setNextNode (Node nextNode)
{
this.nextNode = nextNode;
}
public Data getData ()
{
return data;
}
public void setData (Data data)
{
this.data = data;
}
}

那么我的链接列表类如下：

public class LinkedList {
private Node head = null;
private int size = 0; 
public void addData(Data c){
this.size++;
//empty case
if(this.head == null){
this.head = new Node(c, null);
return;
}

Node current = this.head;
Node previous = null;
while(current.getNextNode()!=null&&previous.getData().getFirstName().compareTo(c.getFirstName())<=1){
previous = current; // hold last element 
current = current.getNextNode(); //move to next element
}
//insert into list
if(current.getNextNode()==null){
current.setNextNode(new Node(c,null)); //append end of List 
previous = new Node(current.getData(), current);
}else{
Node insert = new Node(c, current); //prepend infront
current.setNextNode(insert);
}

我尝试的所有内容似乎都给了我的空指针异常，但也许我在这里没有得到正确的概念。我首先检查我的列表是否为空，并在它前面添加一个指向 null 的节点。当给出新节点时，我遍历当前列表，直到找到一个点并将上一个指针设置为当前指针，当前成为指向列表中下一项的新节点(假设我们不在列表的末尾，它只指向 null(。

在这一点上我很迷茫，我的 this.head 去哪里了，还是我必须在所有边缘情况下执行此操作？任何帮助理解将不胜感激

Answer 1

您的实现是双链列表，它不包含对前一个节点的引用。

这里如何按顺序插入

public void addData(Data c) {
Node newNode = new Node(c, null);
if (head == null) {
head = newNode;
size++;
return;
}
Node current = head;
Node prev = null;
int comparison;
while (current != null) {
comparison = c.getFirstName().compareTo(current.getData().getFirstName());
if (comparison == 0) {
return;
} else if (comparison > 0) { /// greater than
if (current.nextNode == null) { // check if reach tail of the linked list add and break
current.nextNode = newNode;
break;
}
} else { // less then
if (prev == null) { // check if it should be first then put and break
Node oldHead = head;
head = newNode;
head.nextNode = oldHead;
break;
}
prev.nextNode = newNode;
newNode.nextNode = current;
break;
}
prev = current;
current = current.nextNode;
}
size++;
}

Answer 2

public void addData(Data c) {
this.size++;
//empty case
if (this.head == null) {
this.head = new Node(c, null);
return;
}

Node current = this.head;
Node previous = null;
//change in Code
while (current.getNextNode() != null && current.getData().getFirstName().compareTo(c.getFirstName()) <= 1) {
previous = current; // hold last element
current = current.getNextNode(); //move to next element
}
//insert into list
if (current.getNextNode() == null) {
current.setNextNode(new Node(c, null)); //append end of List
previous = new Node(current.getData(), current);
} else {
Node insert = new Node(c, current); //prepend infront
current.setNextNode(insert);
}
}