# 在将节点按字母顺序插入双向链表时出现的问题

go评论62阅读模式

Problem when alphabetically inserting a node into a doubly linked list

# 问题

``````void insert(String x){
node newNode = new node(x);

//列表为空，所以正常插入 - [工作正常]
tail = newNode;
}
//现在根据字母顺序插入节点 - [问题区域]
else {

// 当列表不为空时
while (curnode != null){

// 如果新节点按字母顺序位于当前节点之前，则将其放在之前
if (curnode.data.compareTo(newNode.data) > 0){
node temp = curnode.prev;
curnode.prev = newNode;
newNode.next = curnode;
newNode.prev = temp;
break;
}
// 移动到下一个节点
curnode = curnode.next;
}

}
}
``````

Im trying to write an insertion method for a doubly linked list where as i'm placing the node into the list it is being inserted in alphabetical order. This idea is I will traverse through the list with a curnode and if the newNode comes before the curnode, I will simply place the newNode before the curnode. The code I have written so far works for inserting 1 node into the list, but i'm having problems with the second part that requires checking the order and placing before. How should I change the program to make it work properly? With the code I have now only 1 element (head) will be inserted.

``````void insert(String x){
node newNode = new node(x);

//list is empty so insert as normal - [works fine]
tail = newNode;
}
//Now insert node with respect to alphabetical order - [problem area]
else {

// while the list isn&#39;t empty
while (curnode != null){

// if newNode alphabetically comes before the curnode then place before
if (curnode.data.compareTo(newNode.data) &gt; 0){
node temp = curnode.prev;
curnode.prev = newNode;
newNode.next = curnode;
newNode.prev = temp;
break;
}
}

}
}
``````

# 答案1

``````void insert(String x){
node lastnode = null;
node newNode = new node(x);

//如果链表为空，则正常插入 - [运行良好]
tail = newNode;
}
//根据字母顺序插入节点 - [问题区域]
else {
// 当链表不为空时
while (curnode != null){
// 如果新节点在字母上位于当前节点之前，则放在其前面
if (curnode.data.compareTo(newNode.data) > 0){

node temp = curnode.prev;
curnode.prev = newNode;
newNode.next = curnode;
newNode.prev = temp;
if(temp != null) {
temp.next = newNode;
} else {
// 如果新节点插入到头部
}
break;
}

lastnode = curnode;
curnode = curnode.next;
}
if (curnode == null) {
// 插入到末尾
lastnode.next = newNode;
newNode.prev = lastnode;
tail = newNode;
}

}
}
``````

There are a few things missing with your implementation. Compare it with this working solution:

``````void insert(String x){
node lastnode = null;
node newNode = new node(x);

//list is empty so insert as normal - [works fine]
tail = newNode;
}
//Now insert node with respect to alphabetical order - [problem area]
else {
// while the list isn&#39;t empty
while (curnode != null){
// if newNode alphabetically comes before the curnode then place before
if (curnode.data.compareTo(newNode.data) &gt; 0){

node temp = curnode.prev;
curnode.prev = newNode;
newNode.next = curnode;
newNode.prev = temp;
if(temp != null) {
temp.next = newNode;
} else {
// If newnode gets inserted in the head
}
break;
}

lastnode = curnode;
curnode = curnode.next;
}
if (curnode == null) {
// insert to the last
lastnode.next = newNode;
newNode.prev = lastnode;
tail = newNode;
}

}
}
``````

• 本文由 发表于 2020年10月6日 06:31:25
• 转载请务必保留本文链接：https://go.coder-hub.com/64217065.html
• algorithm
• java
• sorting

go 80

go 55

go 61

go 57