java—在链表中按索引删除元素

wlwcrazw  于 2021-06-27  发布在  Java
关注(0)|答案(2)|浏览(584)

已实现从链表中删除元素的方法:

public void remove(T e) {

    Node<T> node = first;
    Node<T> prevNode = null;
    while(node != null){
        if(e.equals(node)){
            if(prevNode  == null) {
                first = node.next;
            }
            else {
                prevNode.next = node.next;
            }
            size--;
        }
        else {
            prevNode = node;
        }
        node = node.next;
    }
}

如何正确实现按索引删除元素?使用remove方法的功能。

public void removeByIndex(int i) {
    remove(i);
}
bf1o4zei

bf1o4zei1#

remove(get(i));

这不是最有效的解决方案,而是使用 remove(T) 方法。你称之为 get(i) 作为要删除的对象-即指定索引处的元素。
注意:如果列表有重复的值,这个解决方案会有一些问题,但是在这种情况下,您不应该使用 remove(T) 方法。如果希望安全,请迭代到指定的索引:

Node<T> node = first;       
    for(int i=0;i<index;i++){
        prevNode=node;
        node=node.next;
    }

这样做:

node.prev.next=node.next;
node.next.prev=node.prev;
size--;

当然,这只是一个粗略的实现。为了确保完全兼容,您应该检查索引是否有效,并使用 unlink(Node) linkedlist的方法。
linkedlist还有一个 remove(int) 方法:

checkElementIndex(index);
return unlink(node(index));
4nkexdtk

4nkexdtk2#

这样的方法应该有用:

public void remove(int i) {
    if (i >= size || i < 0) {
        throw new ArrayIndexOutOfBoundsException();
    }
    Node<T> remove;
    if (i == 0) {
        remove = first;
        first = first.next;
        first.prev = null; // <- For double linked list
    } else {
        Node<T> node = first;
        for (int j = 0; j < i - 1; ++j) {
            node = node.next;
        }
        remove = node.next;
        if (i == size - 1) {
            node.next = null;
        } else {
            node.next.next.prev = node; // <- For double linked list
            node.next = node.next.next;
        }
    }
    // Clear links from removed Node
    remove.next = null;
    remove.prev = null; // <- For double linked list
    size--;
}

在位置i之前找到节点。将该节点指向“over next”节点。
编辑原始代码示例充其量只是一个粗略的草图。更新了更完整的版本。
编辑#2
轻微改善:
从删除的节点清除链接
还处理双链接列表

相关问题