[Java] - List/ArrayList/LinkedList

Listインタフェース

の繰り返しを可能にする保存順序のセットを実装

ArrayList

Listインタフェース実装クラス

の保存順序を保持し、

の繰り返しを許可する.

集合フレームワークで最も一般的な集合クラス

同様に、

は、通常の配列およびインデックス管理オブジェクトを使用する.

アレイを作成すると、サイズは

に固定されます.

ArrayListは、記憶容量を超えるオブジェクトが入ると自動的に記憶容量

を増加することができる.

既存のVectorを改良し、Vectorの実施原理および機能と同様にした.
ArrayListは、

Vectorではなく

である.
ArrayListの使い方を簡単に理解してみましょう.

List<String> list = new ArrayList<>();
list.add("hello");
list.add("cat");
list.add("hi");
list.add("dog");
list.add("good");
list.add("friends");

System.out.println(list.size());   //  6
System.out.println(list.get(3));   //  dog
list.remove(3);
list.remove("cat");
System.out.println(list);   //  [hello, hi, good, friends]

通常、ArrayListを作成し、実行時にオブジェクトを追加しますが、固定オブジェクトからなるListが生成されることもあります.
この場合、Arrays.asList(T... a)の方法を用いることができる.

List<String> companies = Arrays.asList("google", "apple", "samsung");
System.out.println(companies);  //  [google, apple, samsung]

List<Integer> numbers = Arrays.asList(1, 10, 100);
System.out.println(numbers);  //  [1, 10, 100]

LinkedList

配列は、構造が簡単で、使いやすく、データ・クエリーの速度が最も速いという利点があります.
以下のような欠点がある.

サイズは変更できません.

の非連続データの追加または削除には時間がかかります.

配列の欠点を補うために링크드 리스트(LinkedList)の資料構造が現れた.
配列内のすべてのデータは連続的に存在しますが、リンクリスト
不連続に存在するデータは相互に接続された形で構成される.

ソース:https://www.faceprep.in/data-structures/linked-list-vs-array/
「リンク」リストの各要素(node)は、自分に関連付けられた次の要素への参照(アドレス値)とデータから構成されます.

class Node {
    Node    next;   //  다음 요소의 주소 저장
    Object  obj;    //  데이터 저장
}

リンクリストのデータを追加、削除するのは簡単です.

追加

A -> B -> D

BとDノードの間に「C」ノード

を追加する.

Cノード

を作成

Bの次のノード参照をD->C

に変更する.

Cの次のノード参照をDに適用

A -> B -> C -> D

削除

A -> B -> C

"B"ノード

を削除する.

Aの次のノード参照をB->C

に変更する.
A -> C
中間的にデータを追加/削除する場合、リンクリストのパフォーマンスは配列よりはるかに優れています.

ダブルリンクリスト

リンクリストの移動方向は一方向であるため、次の要素にアクセスしやすいが、前の要素にアクセスするのは難しい.
これを補うのは더블 링크드 리스트(이중 연결리스트, doubly linked list)です.

ソース:https://medium.com/journey-of-one-thousand-apps/data-structures-in-the-real-world-508f5968545a
リンクリストに前の要素への参照変数を追加しただけです.

class Node {
    Node    next;       //  다음 요소의 주소 저장
    Node    previous;   //  이전 요소의 주소 저장
    Object  obj;        //  데이터 저장
}

ダブルリンクリストは、リンクリストよりも各要素にアクセスおよび移動しやすいため、より多く使用されます.
デュアルリンクリストへのアクセス性の向上
[二重ループリンクリスト(二重ループリンクリスト、二重ループリンクリスト)]
ダブルリンクリストの最初のノードと最後のノードを接続します.
->テレビの最後のチャンネルにチャンネルを追加するのは、最初のチャンネルに移動するのと同じです.
実際、JavaのLinkedListクラスは名前とは異なり、「ダブルリンクリスト」ではなく「リンクリスト」として実装されている.
LinkedListの内部コードは次のように示されており、前の要素と次の要素はいずれも参照可能な形式である.

// LinkedList.java
public class LinkedList<E>
  ...
  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;

      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }
  ...
}

理由は上述したように,リンクリストの低アクセス性を向上させるためである.

ArrayList vs LinkedList

ArrayListとLinkedListの違いをサンプルコードで理解します.

追加/削除

実行

public static void main(String[] args) {
    List<String> al = new ArrayList<>(2000000);
    List<String> ll = new LinkedList<>();

    System.out.println("=====순차적 추가=====");
    System.out.println("ArrayList : " + add1(al));
    System.out.println("LinkedList : " + add1(ll));
    System.out.println("=====중간 추가=====");
    System.out.println("ArrayList : " + add2(al));
    System.out.println("LinkedList : " + add2(ll));
    System.out.println("=====중간 삭제=====");
    System.out.println("ArrayList : " + remove2(al));
    System.out.println("LinkedList : " + remove2(ll));
    System.out.println("=====순차적 삭제=====");
    System.out.println("ArrayList : " + remove1(al));
    System.out.println("LinkedList : " + remove1(ll));
}

private static long add1(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        list.add(i + "");
    }
    long end = System.currentTimeMillis();
    return end - start;
}

private static long add2(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        list.add(5000,i + "");
    }
    long end = System.currentTimeMillis();
    return end - start;
}

private static long remove1(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = list.size() - 1; i >= 0; i--) {
        list.remove(i);
    }
    long end = System.currentTimeMillis();
    return end - start;
}

private static long remove2(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        list.remove(i);
    }
    long end = System.currentTimeMillis();
    return end - start;
}

結果

=====순차적 추가=====
ArrayList : 99
LinkedList : 233
=====중간 추가=====
ArrayList : 2233
LinkedList : 106
=====중간 삭제=====
ArrayList : 1403
LinkedList : 219
=====순차적 삭제=====
ArrayList : 8
LinkedList : 25

シーケンスの追加/削除→ArrayListが高速

試験中のArrayListは十分な初期容量を提供し、記憶領域不足による新規ArrayListの生成を回避する

順序削除最後のデータから逆順削除

ArrayListが最後のデータから削除されたときに要素を再配置する必要がないため、かなり高速です.

中間追加/削除→LinkedList高速

LinkedListでは、各要素の接続を変更するだけで済むため、処理速度が速い.

アクセス(クエリー)

アクセス時間をテストしてみましょう.
実行

public static void main(String[] args) {
    List<String> al = new ArrayList<>(1000000);
    List<String> ll = new LinkedList<>();
    
    add(al);
    add(ll);

    System.out.println("=====접근시간 테스트=====");
    System.out.println("ArrayList :" + access(al));
    System.out.println("LinkedList :" + access(ll));

}

private static long access(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
          list.get(i);
    }
    long end = System.currentTimeMillis();
    return end - start;
}

private static void add(List<String> list) {
    for (int i = 0; i < 100000; i++) {
        list.add(i+"");
    }
}

結果

=====접근시간 테스트=====
ArrayList :1
LinkedList :133

エレメントアクセス時間->ArrayListが速い

配列については、次の式で簡単な検索要素のアドレスを得ることができます.
インデックスnのデータのアドレス=配列のアドレス+n*データ型のサイズ

アレイ->各要素がメモリに連続して存在します

は、上述のようにデータ

を簡単に高速に読み出す.

リンクリスト->不連続な各要素

からn番目のデータまで

を順次読み出す.

データの数が多いほど、読み取りデータのアクセス時間が長くなります.

整理する

コレクションの読み込み(アクセス時間)コメントの追加/削除ArrayListの高速で遅い追加/削除順序が高速です.メモリ使用率が低いLinkedListデータは遅いほどアクセス性が悪い

References

南宮城

,『ジャワの晶石』,道宇出版(2016)

https://www.geeksforgeeks.org/vector-vs-arraylist-java/

https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated