0

ArrayList を使用して複数の Card を保持することで、デッキ クラスを作成しています (別のクラスを作成しました) deal。デッキ：

ArrayList の設計により、一番上のカード、一番下のカード、またはデッキ内の任意のカードを配ることができることに注意してください。どれが最も効率的な実装になるかを考えてください。

配列型構造体の先頭から要素を呼び出すのは効率的だといつも思っていました。これはArrayListの場合ですか？

通常の配列とlinkedListはどうですか?

これをタグの下に置く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実装では、各ノードは次のノードへのポインターを維持するだけなので、削除は簡単で、前のノードのリンクを変更するだけです。removeinのこの実装を考えてみましょう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;
}

LinkedListこれは、すべての状況で s が優れていると言っているわけではありません。配列のランダムなインデックスにアクセスする必要がある場合、ArrayList通常は の方がはるかに効率的です (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 に答える