9

什么是双向链表的删除方法?

4

6 回答 6

22

蜥蜴比尔所说的相同算法,但以图形方式:-)

从链接列表中删除
(来源:jaffasoft.co.uk

于 2008-11-07T01:47:44.467 回答
19

一般算法如下:

  • 找到要删除的节点。
  • node.previous.next = node.next
  • node.next.previous = node.previous
  • node.previous = null
  • node.next = null
  • 如果您在非 GC 环境中,请处理节点

您必须检查前一个和下一个节点是否为空,以查看您是删除头部还是尾部,但这些都是简单的情况。

于 2008-11-07T01:18:51.153 回答
4
public void remove ()
{
    if (getPreviousNode () != null)
        getPreviousNode ().setNextNode (getNextNode ());
    if (getNextNode () != null)
        getNextNode ().setPreviousNode (getPreviousNode ());    
}
于 2008-11-07T01:49:29.063 回答
1

双向链表实现删除方法(来自我的第二个编程作业):

public void remove(int index) {
    if(index<0 || index>size())
    throw new IndexOutOfBoundsException("Index out of bounds. Can't remove a node. No node exists at the specified index");
    if(size()==0) {
        throw new NullPointerException("Empty list");
    }
    if(!isEmpty()) {
        Node current;
        //starting next one to our head
        current = head.next;
        for(int i=0;i<index;i++) {
            current = current.next;
        }
        current.previous.next = current.next;
        current.next.previous = current.previous;
        numOfNodes--;
        sizeChangeCount++;
    }
}

public boolean remove(T o) {
    Node current = head;
    for(int i=0;i<size();i++) {
        current=current.next;
        if(current.data.equals(o)) {
            current.previous.next = current.next;
            current.next.previous = current.previous;
            numOfNodes--;
            sizeChangeCount++;
            return true;
        }           
    }
    return false;
}
于 2008-11-10T17:24:20.113 回答
0

您是在询问 api 中方法的名称吗?假设您询问 java.util.LinkedList 实际上是一个双链表,那么该答案将被删除。

...或者您是在问从该类型的数据结构中删除元素的算法的名称是什么?嗯.. 答案也是删除一个元素。现在让实际的算法来做到这一点......实际上只是改变前一个节点中的下一个指针和下一个节点中的最后一个指针的问题。但是,如果您从多个线程使用数据结构,则需要同步 remove 方法,或者按照对数据结构的使用模式有意义的顺序执行删除步骤。

于 2008-11-07T01:20:02.527 回答
0

那么当前指针指针呢?您必须将 crnt 移动到下一个节点。 http://pastebin.ca/1249635

于 2008-11-09T17:31:56.043 回答