java - 为什么Java中LinkedList的get(index)比remove(index)慢

Question

我有一个包含 100000 个字符串项的 LinkedList。当我对索引执行诸如 get、remove、add 等操作时，它似乎是相同的机制。首先它浏览列表以访问 Node[index]，然后进行另一个操作，对于“get”，它仅引用节点的项目，而“remove”则执行更多操作。但为什么“获取”操作比“删除”操作花费更多时间

for(int index=99999;index>=0;index--){
    links.get(index);
}

获取时间(以纳秒为单位):15083052805

for(int index=99999;index>=0;index--){
    links.remove(index);
}

以纳秒为单位的删除时间:2310625

LinkedList的功能:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

Answer 1

获取索引 N 处的元素的成本非常高，因为要真正获取该元素，需要遍历列表节点直到到达该元素。

现在，当您删除循环中的元素时，请意识到您总是删除列表的最后一个元素(您的 i 在该循环中始终与 list.size()-1 完全对应) )。

node(index)方法实际上是通过从前/后搜索来优化访问，具体取决于index是否更接近0或list.size()。在您删除的情况下，它总是从后面搜索并在第一次尝试时命中。

要吸取的教训:LinkedList不是适合通过随机索引访问的列表类型。