根据键从链表中删除节点

Question

您好，我正在尝试根据密钥删除节点。我正在学习字典实现并决定从头开始实现它以充分理解这个概念。我成功地添加了 return 使用 2 个节点引用头指针和尾指针的值。但是我很难使用密钥从列表中删除节点。下面是我要从列表中删除的代码

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;
   }

当我输入要删除的所需密钥时。它会删除要删除的所需密钥之后的所有密钥。 PS 这不是双向链表。我刚刚创建了一个尾节点来访问列表中的最后一个节点

Answer 1

你有两个错误：

您将 previous = current; 设置为第一条语句，这意味着之前和当前始终相同。
您应该删除此行： previous.setNextNode(null); 正如您在分配新的下一个节点后立即执行的那样。

Answer 2

您已经了解了总体思路，除了两件事：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();
}

Answer 3

看来您在更新列表时陷入了困境。此代码简化了您的算法：

// 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
    }
}

根据键从链表中删除节点

deleting a node from a linked list based on a key

java

dictionary

linked-list