Java の動的配列

さまざまな複雑さのプログラムを作成する場合、各開発者は配列を含む多くのデータ型を使用します。この構造は、1 種類のセットを保管するのに適しており、パフォーマンスが高く、一般的に便利です。 配列の重大な欠点は、配列が静的であることです。配列のサイズは事前に指定する必要があります。しかし、プログラマーはまだ未来を予測する方法を知りません（もちろん、情報を信じられないほど速く処理し、あらゆる出来事を予測できる AI が登場しない限り）。このため、プログラムの実行中にサイズを変更できる構造を作成しました。これは動的配列と呼ばれます。

JavaRush コースの動的配列

このトピックは、Java 構文クエストの JavaRush コースのレベル 7と部分的にレベル 8 で非常にわかりやすく明確に説明されています。数回の講義と 18 個もの問題を通じて、動的配列の種類とパフォーマンスを含むそれらの違いなど、主要な問題が取り上げられます。動的配列は開発者の憂鬱や頭痛を軽減し、信じられないほどの時間を節約できるため、このトピックは非常に重要です。

動的配列とは何ですか?

動的配列は、プログラムの実行中にサイズを変更できる配列です。Java では、この役割は主に ArrayList クラスと LinkedList クラスによって果たされます。配列とは異なり、ArrayList と LinkedList には参照データ型のみが含まれます。つまり、オブジェクトのみを格納できます。幸いなことに、Java には、プリミティブ型を動的配列に格納できる自動ボックス化および自動アンボックス化メカニズムがあります。静的配列と同様に、動的配列は同種です。つまり、単一のデータ型を格納できます。ただし、継承メカニズムとインターフェイスの適切な使用のおかげで、1 つの共通クラスから継承されたさまざまなクラス全体を 1 つの動的配列に格納することができます。詳細については以下で説明します。つまり、静的配列は次のように動作します。 Javaの動的配列は次のように動作します (図の 3 番目のステップからの続き): Java は特別なネイティブ関数を使用して配列をコピーするため、このような「移動」はそれほど簡単ではありません。高い。

なぜ動的配列が必要なのでしょうか?

Java の動的配列は、プログラムの作成時点ではサイズが不明な同種のデータのセットを処理するために使用されます。たとえば、現在アプリケーションを使用しているすべてのクライアントのデータをキャッシュしたい場合があります。このようなクライアントの数を事前に予測することは不可能です。動的配列を使用しない場合、この問題は次のオプションで解決できます。

1. ニーズを 100% カバーできる大規模な配列を作成します。
2. バッファとして機能する静的配列を作成します。
3. セットなどの他の動的構造を適用します。

最初のオプションは、厳密に限定された範囲の場合にのみ適しています。他の場合には、このような配列は大量のメモリ空間を占有し、非常に非効率的になります。2 つ目では、バッファのクリアや読み取りなどのための追加メカニズムの実装が必要になります。3 番目にも、機能の違いによる欠点があります。

Java で動的配列は何をするのでしょうか?

Java 言語では、ArrayList クラスと LinkedList クラスは動的配列として機能します。最も一般的に使用されるのは ArrayList です。これは、二重リンク リストの概念を実装する LinkedList とは異なり、従来の配列として機能するためです。それについては少し後で話します。

ArrayList、LinkedList - 概念と運用ルール

ArrayList は、プログラムの実行中に展開できる古典的な配列です。これは通常の配列に基づいており、作成時のサイズは 10 要素です。サイズが大きくなると容量も増えます。ArrayList が機能するルールは次のとおりです。

• 静的配列と同様に、0 からインデックスが付けられます。
• 末尾の挿入とインデックスによるアクセスは非常に高速です - O(1);
• 要素を先頭または途中に挿入するには、すべての要素を 1 セル右にコピーし、必要な位置に新しい要素を貼り付ける必要があります。
• 値によるアクセスは要素の数 - O(n) に依存します。
• 従来の配列とは異なり、null を格納できます。

LinkedList の場合は、すべてがもう少し複雑です。二重リンク リストに基づいています。つまり、構造的には、この動的 Java 配列は、相互に参照する多数の分散オブジェクトです。写真付きで説明すると分かりやすいです。HeadLinkedList 内には、要素の数に関する情報と最初と最後の要素へのリンクを格納する メイン オブジェクトがあります。現在のフィールドsize = 0は 、firstおよびですlast = null。このリストに追加される各要素は、個別の内部オブジェクトのコンテンツです。要素を追加しましょうJohnny。 これで、値「Johnny」を持つノードができました。メイン要素の場合、最初と最後の要素へのリンクは新しいノードを指します。このオブジェクトには、前と次の要素へのリンクもあります。これが最初の要素であるため、前の要素へのリンクは常に null になります。また、次の要素へのリンクはまだ存在しないため、常に null になります。これを修正しましょう。 値「Watson」を持つ新しい要素を追加し、これが 2 番目の要素になりました。最初の要素には次の要素を指すフィールドがあり、新しい要素には前の要素を指すnextフィールドがあることに注意してください。previousメイン要素の場合、最後の要素へのリンクが新しいノードを指すようになります。次の図は、リストの中央に要素を追加する方法を示しています。 新しい要素「Hamish」が追加されました。リストの中央に挿入するには、図に示すように、要素へのリンクを再割り当てするだけです。これらの図は、詳細には触れずに、トップレベルでの二重リンクリストのプロセスを説明しています。LinkedList に関する話を要約すると、その操作に関するいくつかのルールを導き出すことができます。

• 配列と同様に、0 からインデックスが付けられます。
• 最初と最後の要素へのアクセスは、要素の数 - O(1) には依存しません。
• インデックスによる要素の取得、リストの途中からの挿入または削除は、要素の数 - O(n) に依存します。
• イテレータ メカニズムを使用すると、挿入と削除が一定時間内に行われます。
• 従来の配列とは異なり、null を格納できます。

コード例

いくつかの例を見てみましょう。コード スニペットには、ArrayList と LinkedList の両方の例が含まれています。

創造

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

要素の追加

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

一見すると、add()ANDメソッドはaddLast()同じ機能を実行しますが、このメソッドはadd()インターフェイスから LinkedList に送信されList、メソッドはaddLastインターフェイスから送信されますDeque。LinkedList は、これらのインターフェイスの両方を実装します。この場合、コンテキストに最も適した方法を使用することをお勧めします。LinkedList をキューとして使用する場合は、 を使用するのが最適ですaddLast。LinkedList をリストとして使用する場合は、 を使用するのが適切ですadd()。

要素の削除

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

オブジェクトがインデックスによって削除された場合、メソッドは削除されたオブジェクトを返します。オブジェクトが値によって削除される (または LinkedList の最初または最後の要素が削除される) 場合、メソッドはオブジェクトが見つかって削除された場合はtrueを返し、それ以外の場合はfalse を返します。

要素にアクセスしてリストを検索する

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

ループ状に歩く

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

ここで、検索について少し述べておく価値があります。indexOf()初心者の開発者の多くは、リスト内の要素を検索するときに、メソッドと が存在するにもかかわらず、ループで検索を開始し、すべての要素を検索された要素と比較しますlastIndexOf()。このメソッドを使用して、contains()要素がリストに存在するという事実を取得することもできます。

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

さらに読むためのリンク

1. ArrayList からの要素の削除に関する優れた記事がここにあります。これは動的 Java 配列であるため、要素の削除には多くの微妙な点があります。
2. ArrayList の仕組みについては、ここで詳しく説明します。
3. LinkedList についてもう少し詳しく説明します。
4. ArrayListとLinkedListに関する Habr の記事がいくつかあります。