按链表中的索引删除元素

Question

已经实现了从链表中删除元素的方法：

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

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

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

Answer 1

这样的事情应该可以工作：

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 之前的节点。 将该节点指向"下一个"节点。

编辑原始代码示例充其量只是一个粗略的草图。更新了更完整的版本。

编辑 #2

略有改进：

• 从已删除的节点中清除链接
• 还可以处理双链表

Answer 2

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

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

LinkedList 还有一个remove(int)方法的实现：

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