[Java]ArrayListとLinkedListの違いについて

この記事は、シアトルコンサルティング株式会社 Advent Calendar 2021の24日目の記事です。
こんにちは、シアトルコンサルティングの小泉です。

##はじめに
今回はJavaのコレクションフレームワークであるListについて調べてみました。
その中でもArrayListとLinkedListのそれぞれの特徴について説明します。

##ゴール
ArrayListとLinkedListの違いについて理解する。

##はじめに
JavaのコレクションフレームワークであるListについて説明します。

Listクラス

java.util.ArrayList
・配列型のリスト
・指定位置の要素の取得が速い
・要素の挿入、削除が遅い

java.util.LinkedList
・線形リスト型のリスト
・指定位置の要素の取得が遅い
・要素の挿入、削除が速い

ArrayList

Listインタフェースを実装したコレクションクラスです。
「Array」という名にあるように「配列のような感覚」で扱うことができます。
書き方は下記の通りです。

ArrayList<型> 変数名 = new ArrayList<型>();

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String args[]) {

        List<String> sampleList = new ArrayList<String>();
        sampleList.add("1回目のリストに格納");
        sampleList.add("2回目のリストに格納");

        // リストに格納した全要素を順番に出力
        for (int i = 0; i < sampleList.size(); i++) {
            System.out.println(sampleList.get(i));
        }
    }
}

・要素の追加：addメソッド
・要素の取得：getメソッド
####特徴
ArrayListは要素がそれぞれ順序番号を持っており、全てメモリ上でインデックス化されているため、特定の要素へすぐにアクセスすることが出来ます。
一方、末尾意外の要素を足したり引いたりする際は、それ以降の要素全ての順序番号を繰り上げたり繰り下げたりするための再配置処理が行われるため多くの時間がかかってしまいます。

LinkedList

LinkedListは、要素同士を前後双方向のリンクで参照するリンクリストを表します。
書き方は下記の通りです。

LinkedList<型> 変数名 = new LinkedList<型>();

class Main {
  public static void main(String args[]) {

         List<String> sampleList = new LinkedList<String>();
        sampleList.add("1回目のリストに格納");
        sampleList.add("2回目のリストに格納");

        // リストに格納した全要素を順番に出力
        for (int i = 0; i < sampleList.size(); i++) {
            System.out.println(sampleList.get(i));
        }
    }
}

・要素の追加：addメソッド
・要素の取得：getメソッド
####特徴
LinkedListでは要素同士が、それぞれ前後に持っているリンク情報で繋がっています。

それぞれの要素は順序番号を保持していないため、特定の要素を取り出す際は、先頭もしくは末尾から一つずつ順序を数えていく必要があります。そのため順序番号があらかじめ保持されているArrayListに比べると、多くの時間がかかってしまいます。
一方、要素を足したり引いたりする際は、リンク情報を書き換えれば終わりなので、再配置処理が行われない分ArrayListよりも高速です。

##さいごに
ArrayListとLinkedListそれぞれの特徴は理解していただけましたでしょうか？
ソースコードに関してはほぼ同じですが、処理の中身の違いを理解することで開発する際に役立つと思います。