java - 从哪里调用 ArrayList 中的元素更有效？

Question

我正在制作一个套牌类，通过使用 ArrayList 来保存多张卡片(我制作的另一个类)但是，当我的老师提到交易<时，我无法弄清楚这句话的意思 返回牌组顶牌的方法:

Remember that because of the design of an ArrayList, you may deal the top Card, the bottom Card, or any Card from within the Deck. Think about which would be the most efficient implementation.

我一直认为从任何数组类型结构的前面调用元素都是有效的。 ArrayList 也是这样吗？

常规数组和链表怎么样？

<小时/>

我本打算将其放在 homework 标签下，但它给了我一个说明，表明它已过时。

Answer 1

当您发牌时，您将从牌组中移除一张牌，这与仅仅访问该牌不同。访问卡将是恒定时间，但移除卡则不是。当您从 ArrayList 中删除时，您需要重新排列列表中的所有元素。考虑一下 remove 方法的实现(来自 OpenJDK)

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; // Let gc do its work
   return oldValue;
}

因此，如果移动列表前面的元素，则必须移动整个数组。

现在在LinkedList实现中，每个节点只维护一个指向下一个节点的指针，因此删除很简单，它只是更改前一个节点的链接。考虑一下 LinkedList 中 remove 的实现(同样来自 OpenJDK):

private E remove(Entry<E> e) {
       if (e == header)
           throw new NoSuchElementException();
       E result = e.element;
       e.previous.next = e.next;
       e.next.previous = e.previous;
       e.next = e.previous = null;
       e.element = null;
       size--;
       modCount++;
       return result;
}

这并不是说 LinkedList 在任何情况下都更好。如果需要访问数组的随机索引，ArrayList 通常会更高效(LinkedList 需要从头到尾遍历每个节点，直到找到该索引)。