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

huangapple
go评论90阅读模式
英文:

Problem when alphabetically inserting a node into a doubly linked list

问题

我正试图为双向链表编写一个插入方法，在将节点放入链表时，节点将按字母顺序插入。我的想法是，我将使用当前节点（curnode）遍历列表，如果新节点（newNode）出现在当前节点之前，我将简单地将新节点放在当前节点之前。到目前为止，我编写的代码可以将一个节点插入到列表中，但是我在需要检查顺序并进行插入的第二部分遇到问题。我应该如何更改程序以使其正常工作？使用我现在的代码，只会插入一个元素（头部）。

  1. void insert(String x){
  2.     node curnode = head;
  3.     node newNode = new node(x);
  5.     //列表为空，所以正常插入 - [工作正常]
  6.     if (head == null){
  7.         head = newNode;
  8.         head.prev = null;
  9.         head.next = null;
  10.         tail = newNode;
  11.     }
  12.     //现在根据字母顺序插入节点 - [问题区域]
  13.     else {
  14.        
  15.         // 当列表不为空时
  16.         while (curnode != null){
  18.             // 如果新节点按字母顺序位于当前节点之前，则将其放在之前
  19.             if (curnode.data.compareTo(newNode.data) > 0){
  20.                 node temp = curnode.prev;
  21.                 curnode.prev = newNode;
  22.                 newNode.next = curnode;
  23.                 newNode.prev = temp;
  24.                 break;
  25.             }
  26.             // 移动到下一个节点
  27.             curnode = curnode.next;
  28.         }
  29.        
  30.     }
  31. }
英文:

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.

  1. void insert(String x){
  2.         node curnode = head;
  3.         node newNode = new node(x);
  5.         //list is empty so insert as normal - [works fine]
  6.         if (head == null){
  7.             head = newNode;
  8.             head.prev = null;
  9.             head.next = null;
  10.             tail = newNode;
  11.         }
  12.         //Now insert node with respect to alphabetical order - [problem area]
  13.         else {
  14.            
  15.             // while the list isn't empty 
  16.             while (curnode != null){
  18.                 // if newNode alphabetically comes before the curnode then place before
  19.                 if (curnode.data.compareTo(newNode.data) > 0){
  20.                     node temp = curnode.prev;
  21.                     curnode.prev = newNode;
  22.                     newNode.next = curnode;
  23.                     newNode.prev = temp;
  24.                     break;
  25.                 }
  26.             }
  27.            
  28.         }
  29.     }

答案1

得分: 1

有几个问题在你的实现中缺失。将其与这个有效的解决方案进行比较：

  1. void insert(String x){
  2.     node curnode = head;
  3.     node lastnode = null;
  4.     node newNode = new node(x);
  5.     
  6.     //如果链表为空，则正常插入 - [运行良好]
  7.     if (head == null){
  8.         head = newNode;
  9.         head.prev = null;
  10.         head.next = null;
  11.         tail = newNode;
  12.     }
  13.     //根据字母顺序插入节点 - [问题区域]
  14.     else {
  15.         // 当链表不为空时
  16.         while (curnode != null){
  17.             // 如果新节点在字母上位于当前节点之前，则放在其前面
  18.             if (curnode.data.compareTo(newNode.data) > 0){
  19.                 
  20.                 node temp = curnode.prev;
  21.                 curnode.prev = newNode;
  22.                 newNode.next = curnode;
  23.                 newNode.prev = temp;
  24.                 if(temp != null) {
  25.                     temp.next = newNode;
  26.                 } else {
  27.                     // 如果新节点插入到头部
  28.                     head = newNode;
  29.                 }
  30.                 break;
  31.             }
  32.             
  33.             lastnode = curnode;
  34.             curnode = curnode.next;
  35.         }
  36.         if (curnode == null) {
  37.             // 插入到末尾
  38.             lastnode.next = newNode;
  39.             newNode.prev = lastnode;
  40.             tail = newNode;
  41.         }
  42.        
  43.     }
  44. }

注意：由于你要求只返回翻译好的部分，我已经按照你的要求将翻译后的代码部分提供给你。如果有任何问题，请随时询问。

英文:

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

  1. void insert(String x){
  2.     node curnode = head;
  3.     node lastnode = null;
  4.     node newNode = new node(x);
  5.     
  6.     //list is empty so insert as normal - [works fine]
  7.     if (head == null){
  8.         head = newNode;
  9.         head.prev = null;
  10.         head.next = null;
  11.         tail = newNode;
  12.     }
  13.     //Now insert node with respect to alphabetical order - [problem area]
  14.     else {
  15.         // while the list isn't empty 
  16.         while (curnode != null){
  17.             // if newNode alphabetically comes before the curnode then place before
  18.             if (curnode.data.compareTo(newNode.data) > 0){
  19.                 
  20.                 node temp = curnode.prev;
  21.                 curnode.prev = newNode;
  22.                 newNode.next = curnode;
  23.                 newNode.prev = temp;
  24.                 if(temp != null) {
  25.                     temp.next = newNode;
  26.                 } else {
  27.                     // If newnode gets inserted in the head
  28.                     head = newNode;
  29.                 }
  30.                 break;
  31.             }
  32.             
  33.             lastnode = curnode;
  34.             curnode = curnode.next;
  35.         }
  36.         if (curnode == null) {
  37.             // insert to the last
  38.             lastnode.next = newNode;
  39.             newNode.prev = lastnode;
  40.             tail = newNode;
  41.         }
  42.        
  43.     }
  44. }

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

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定