0

deal我正在制作一个甲板类，通过使用 ArrayList 来保存多张卡片（我制作的另一个类）但是，当我的老师提到返回顶部卡片的方法时，我无法弄清楚我的老师的意思是什么甲板：

请记住，由于 ArrayList 的设计，您可以发牌中的顶牌、底牌或任何牌。想想哪一个是最有效的实现。

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

常规数组和链表呢？

我打算把它放在homework标签下，但它给了我一个说明它已经过时的描述。

4

3 回答 3

4

当您发牌时，您是从牌组中取出一张牌，这与仅访问该牌不同。访问卡将是恒定的时间，但移除不是。从 中删除时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实现中，每个节点只维护一个指向下一个节点的指针，所以删除很简单，它只是改变了前一个节点的链接。remove考虑in 的这个实现LinkedList（同样来自 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;
}

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

于 2013-02-09T22:33:20.487 回答
1

如果您的类中没有特别介绍，那么您想阅读类和方法的 Java 文档。

特别是，当你从牌堆中“发”一张牌时，你就是在移除它。阅读ArrayList.remove(index) 的 Javadoc发现：

移除此列表中指定位置的元素。将任何后续元素向左移动（从它们的索引中减去 1）。

考虑如何根据ArrayList您“发牌”的位置来应用它。

于 2013-02-09T22:34:12.577 回答
0

ArrayList 只是一个数组，在里面。所以访问任何项目都是 O(1)。但是，删除东西是另一回事。如果“交易”是指“将其从列表中删除”，稍微思考一下就会发现，从 ArrayList 中的一个位置删除它很便宜，而在其他地方则很昂贵。因此，如果您必须有效地处理从任何地方删除，您可能不想使用 ArrayList。

于 2013-02-09T22:33:36.620 回答