ArrayListとLinkedListについて

ArrayListとLinkedList

Javaでは、基本型(int、boolean、String、char)またはインスタンスをリストとして保存する場合、通常は配列を使用します。しかし、配列は宣言時にサイズを指定する必要があるため、動的に要素の追加や削除などができないという欠点があります。配列の要素を追加または削除する場合、新しい配列を宣言してコピーするなどの方法を使用して直接操作する必要があります。データを継続的に変更するアルゴリズム問題や、あるプログラムの実装などでは、これはかなりの不便さとなります。

このような不便さを解消するのが、Listインターフェースを継承して実装されたArrayListとLinkedListクラスです。これらの両方は、Collectionsオブジェクトの一種です。これらの2つのリストは、動的に使用できるため、新しい値の追加や削除が便利で、基本配列の欠点をカバーしています。ただし、内部要素として基本型ではなく、Integer、Characterなどのクラス型の要素を持つため、メモリの面では配列よりもスペースを使用すると考えられます。

// array
int[] Iarr = new int[10];
char[] Carr = new char[10];
String[] Sarr = new String[10];
boolean[] Barr = new boolean[10];

// array list系
ArrayList<Integer> IarrL = new ArrayList<>();
ArrayList<Character> CarrL = new ArrayList<>();
LinkedList<String> SarrL = new LinkedList<>();
LinkedList<Boolean> BarrL = new LinkedList<>();

これらの2つは明らかに似ていますが、異なる点を持っています。したがって、状況に応じて異なる方法で使用する必要があります。

ArrayList

ArrayListは内部的にデータを配列としてメモリ上で管理し、データの追加や削除には以下のように一時的な配列を作成し、データをコピーする方法を使用しています。

各データの追加や削除ごとに、配列を新たに作成してデータをコピーするため、既存の10個のデータに1つのデータを追加する場合、10回のコピーが必要です。したがって、追加や削除にはO(n)の時間計算量が必要です。

一方、参照の場合、データは配列の形式で保存されているため、ユーザーが望むインデックスのデータをO(1)の時間で直接取得することができます。

したがって、ArrayListの場合、追加や削除には不利であり、参照には有利です。

LinkedList

LinkedListはデータを単一のノードとして構成し、各ノードは自身の前のノードと次のノードのみを知っています。開始ノードも次のノードのみを参照しているだけです。ArrayListが全体の視点でデータセットを見るのであれば、LinkedListは一人称の視点でデータセットを見ると考えることができます。

各ノードは個別にメモリに保存され、次のノードの位置を示しているため、データの追加や削除時に他のデータのコピーは必要ありません。新しいデータノードを作成し、挿入するだけです。したがって、データの追加や削除にはO(1)の時間計算量を持つことができます。

一方、データの参照部分では、ArrayListとは異なり、目的のインデックスまでノードを逐一通過し、次のノードをチェックする必要があります。したがって、最大でO(n)の時間計算量が発生する可能性があります。

結果的に、LinkedListの場合、追加や削除には有利であり、参照には不利です。

Conclusion

ArrayListは大量のデータに対しては追加や削除には不利であり、参照には有利です。一方、LinkedListは大量のデータに対しては参照には不利であり、追加や削除には有利です。したがって、状況に応じて必要なものを選択することで、プログラムのパフォーマンス面でより良い結果が得られる可能性があります。

課題

・コードでアルゴリズムを作成する必要があるかも(https://www.nextree.co.kr/p6506/　→ 勉強してみよう)