从列表中获取/删除第一个元素的有效方法？

Question

我想取出并从列表中删除第一个元素.我可以看到,我有两个选择:

第一种方法:

LinkedList<String> servers = new LinkedList<String>();
....
String firstServerName = servers.removeFirst();

第二种方法

ArrayList<String> servers = new ArrayList<String>();
....
String firstServerName = servers.remove(0);

我的列表中有很多元素.

• 我们应该使用哪种偏好？
• 以上两者有什么区别？它们在性能方面在技术上是一样的吗？如果我们有很多元素,这里涉及的复杂性是多少？

什么是最有效的方法.

Answer 1

如果“优先删除”的比较是在ArrayList和LinkedList类别之间进行，则LinkedList获胜明显。

从链接列表中删除元素的成本较高O(1)，而从数组（数组列表）中删除则成本较高O(n)。

Answer 2

确保您了解LinkedList和ArrayList之间的区别.ArrayList使用Array实现.

LinkedList需要恒定时间来删除元素.ArrayList可能需要线性时间来删除第一个元素(以确认我需要检查实现,而不是java expert).

另外我认为LinkedList在空间方面更有效.因为每次删除元素时ArrayList都不会(也不应该)重新调整数组的大小,因此它占用的空间比需要的多.

Answer 3

实际上，LinkedList#removeFirst效率更高，因为它在双向链表上运行，并且删除第一个元素基本上只是将它与列表的头部断开链接并将下一个元素更新为第一个元素：

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

ArrayList#remove 正在对内部数组进行操作，该数组需要通过复制子数组将所​​有后续元素向左移动一个位置：

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

另一方面，LinkedList#get操作需要遍历整个列表的一半以检索指定索引处的元素 - 在最坏的情况下。ArrayList#get将直接访问指定索引处的元素，因为它对数组进行操作。

我在这里提高效率的经验法则是：

• 使用LinkedList，如果你做了很多的add/remove在检索操作比较（例如：get）;
• 使用ArrayList，如果你使用比较做了很多检索操作中add/ remove。

Answer 4

我认为你需要的是ArrayDeque（一个被不公平地忽视的类java.util）。其removeFirst方法对于 的执行时间为 O(1) LinkedList，同时它通常表现出 的更好的空间和时间特性ArrayList。它\xe2\x80\x99s 实现为数组中的循环队列。

\n\n

你应该很少使用LinkedList. 在我作为 Java 程序员的 17 年里，我曾经做过一次，现在回想起来很后悔。

\n

Answer 5

List.subList\xe2\x80\x8b(int fromIndex, int toIndex)

\n

\n

返回此列表中指定的 fromIndex（包含）和 toIndex（不包含）之间的部分的视图。

\n

\n

适合用于ArrayList，其中删除第一个元素的复杂度为 O(n)。

\n

final String firstServerName = servers.get(0);\nservers = servers.subList(1, servers.size());\n

\n

Answer 6

使用链表要快得多。

链表

它只会引用节点，因此第一个节点就会消失。

数组列表

对于数组列表，它必须将所有元素移回一个位置以保持底层数组正确。