英文:
Problem when alphabetically inserting a node into a doubly linked list
问题
我正试图为双向链表编写一个插入方法，在将节点放入链表时，节点将按字母顺序插入。我的想法是，我将使用当前节点（curnode）遍历列表，如果新节点（newNode）出现在当前节点之前，我将简单地将新节点放在当前节点之前。到目前为止，我编写的代码可以将一个节点插入到列表中，但是我在需要检查顺序并进行插入的第二部分遇到问题。我应该如何更改程序以使其正常工作？使用我现在的代码，只会插入一个元素（头部）。
void insert(String x){
node curnode = head;
node newNode = new node(x);
//列表为空，所以正常插入 - [工作正常]
if (head == null){
head = newNode;
head.prev = null;
head.next = null;
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 curnode = head;
node newNode = new node(x);
//list is empty so insert as normal - [works fine]
if (head == null){
head = newNode;
head.prev = null;
head.next = null;
tail = newNode;
}
//Now insert node with respect to alphabetical order - [problem area]
else {
// while the list isn't empty
while (curnode != null){
// if newNode alphabetically comes before the curnode then place before
if (curnode.data.compareTo(newNode.data) > 0){
node temp = curnode.prev;
curnode.prev = newNode;
newNode.next = curnode;
newNode.prev = temp;
break;
}
}
}
}
答案1
得分: 1
有几个问题在你的实现中缺失。将其与这个有效的解决方案进行比较：
void insert(String x){
node curnode = head;
node lastnode = null;
node newNode = new node(x);
//如果链表为空，则正常插入 - [运行良好]
if (head == null){
head = newNode;
head.prev = null;
head.next = null;
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 {
// 如果新节点插入到头部
head = newNode;
}
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 curnode = head;
node lastnode = null;
node newNode = new node(x);
//list is empty so insert as normal - [works fine]
if (head == null){
head = newNode;
head.prev = null;
head.next = null;
tail = newNode;
}
//Now insert node with respect to alphabetical order - [problem area]
else {
// while the list isn't empty
while (curnode != null){
// if newNode alphabetically comes before the curnode then place before
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 {
// If newnode gets inserted in the head
head = newNode;
}
break;
}
lastnode = curnode;
curnode = curnode.next;
}
if (curnode == null) {
// insert to the last
lastnode.next = newNode;
newNode.prev = lastnode;
tail = newNode;
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论