java—根据键从链表中删除节点

0sgqnhkj 于 2021-07-13 发布在 Java

关注(0)|答案(3)|浏览(470)

你好，我正试图删除一个基于密钥的节点。我正在学习字典实现，并决定从头开始实现它，以充分理解这个概念。我成功地使用两个节点引用（一个头指针和一个尾指针）添加和返回值。但是我很难用这个键从列表中删除一个节点。下面是我要从列表中删除的代码

public V remove(K key) {
   V result = null;
   if(!this.isEmpty()&&head==tail){ //if head and tail are only nodes in the list
       if(tail.getKey().equals(key)){
       result = tail.getValue();
       head=null;
       tail = null;
       count--; //decrements the count in the list
       }
   }
   else {
        boolean found = false;
        Node current = head;
        Node previous = null;
        while(current!=null&&!found){
            if(current.getKey().equals(key)){
                previous = current;
                result = current.getValue();
                previous.setNextNode(current.getNextNode());
                previous.setNextNode(null);
                count--;
                found = true;
            }
            current = current.getNextNode();
        }
       }
   return result;
   }

当我输入想要删除的密钥时。它将删除所需密钥之后的所有密钥。它不是一个双重链接列表。我刚刚创建了一个tail节点来访问列表中的最后一个节点

Java Dictionary linked-list

来源：https://stackoverflow.com/questions/29911873/deleting-a-node-from-a-linked-list-based-on-a-key

3条答案

按热度按时间

qv7cva1a1#

看来你正忙于更新名单。此代码简化了算法：

// this method returns the head of the new list with the item possibly removed
public Node remove (K key) {
V result = null;
if (this.isEmpty()) {
    return null;                          // return null for empty list
} else if (head.getKey().equals(key)) {
    return head.getNextNode();            // return head if head matches
} else {
   Node current = head;
   Node next = head.getNextNode();

   while (next != null) {                 // walk down the list and search
       if (next.getKey().equals(key)) {
           current.setNextNode(next.getNextNode());
           break;
       }
       current = next;                    // advance list pointers
       next = next.getNextNode();
    }

    return head;                          // will return head for list with 1 element
    }
}

赞(0）回复(0）举报 2021-07-13

bqujaahr2#

你大概知道了，除了两件事： previous = current 应该在if块之外执行，以便在向前移动电流之前始终分配它，并且 previous.setNextNode(null) 应在撤消前一行时删除。
另外，当列表中的第一个节点与键匹配时，需要设置一个特例，以便可以重新分配头。

while(current!=null&&!found){
    if(current.getKey().equals(key)){
        result = current.getValue();
        previous.setNextNode(current.getNextNode());
        count--;
        found = true;
    }
    previous = current;
    current = current.getNextNode();
}

赞(0）回复(0）举报 2021-07-13

rseugnpd3#

您有两个错误：
你准备好了吗 previous = current; ，作为第一个语句，表示前一个和当前总是相同的。
您应该删除此行： previous.setNextNode(null); 在分配新的下一个节点后立即执行此操作。

赞(0）回复(0）举报 2021-07-13