首页 文章

根据密钥从链表中删除节点

提问于
浏览 次
2

您好我正在尝试删除基于密钥的节点 . 我正在学习字典实现，并决定从头开始实现它以完全理解这个概念 . 我成功地能够使用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它不是双链表 . 我刚刚创建了一个尾节点来访问列表中的最后一个节点

java dictionary linked-list

3 回答

  • 0

    您似乎陷入了更新列表的困境 . 此代码简化了您的算法：

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

    你有一般的想法，除了两件事： 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

    你有两个错误：

    • 您将 previous = current; 设置为第一个语句，表示previous和current始终相同 .

    • 您应该删除此行： previous.setNextNode(null); 在分配新的下一个节点后立即执行此操作 .

    回复于

相关问题