はとはとプロジェクト > Java プログラミング > コレクションフレームワーク > List インターフェース

List インターフェース

順序付けられたコレクションとその実装クラスの特性と効率的な使い方

List インターフェースの概要

List<E> インターフェースは、順序付けられた要素のコレクションを定義します。リスト内の各要素には特定のインデックス（位置）があり、そのインデックスを使って要素にアクセスできます。Listは重複要素を許可するため、同じ要素を複数回追加することが可能です。

List の主な特徴

  • 順序付け: 要素は挿入された順序で保持されます
  • インデックスベース: 0から始まるインデックスで要素にアクセス可能
  • 重複許容: 同じ要素を複数含むことができます
  • Null許容: null要素を格納できます（実装による）

主な List 実装クラス

ArrayList

ArrayList は動的配列に基づく List インターフェースの実装です。内部的には要素を配列に格納し、容量が不足すると自動的に拡張されます。

ArrayList の特徴

  • ランダムアクセスが高速: get(i)、set(i, e) 操作は O(1) の時間計算量
  • 末尾への追加は通常高速: add(e) 操作はほとんどの場合 O(1)、ただし容量拡張が必要な場合は O(n)
  • 中間位置への挿入・削除は低速: add(i, e)、remove(i) は O(n) の時間計算量
  • イテレーションは効率的: 連続したメモリ領域を使用するため、キャッシュフレンドリー
  • スレッドセーフではない: 同期化されていないため、複数スレッドでの使用には外部同期が必要

ArrayList の基本的な使用例

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

public class ArrayListExample {
    public static void main(String[] args) {
        // ArrayList の作成
        List<String> fruits = new ArrayList<>();
        
        // 要素の追加
        fruits.add("りんご");
        fruits.add("バナナ");
        fruits.add("オレンジ");
        
        // 特定の位置に要素を挿入
        fruits.add(1, "ぶどう");  // ["りんご", "ぶどう", "バナナ", "オレンジ"]
        
        // 要素へのアクセス
        String fruit = fruits.get(0);  // "りんご"
        
        // 要素の変更
        fruits.set(0, "青りんご");  // ["青りんご", "ぶどう", "バナナ", "オレンジ"]
        
        // 要素の削除
        fruits.remove(2);  // "バナナ"を削除 -> ["青りんご", "ぶどう", "オレンジ"]
        
        // リストのサイズ取得
        int size = fruits.size();  // 3
        
        // 要素の検索
        int index = fruits.indexOf("ぶどう");  // 1
        boolean contains = fruits.contains("バナナ");  // false
        
        // リストの走査
        for (String f : fruits) {
            System.out.println(f);
        }
    }
}

LinkedList

LinkedList は双方向リンクリストに基づく List インターフェースの実装です。各要素（ノード）は前後の要素への参照を持ちます。

LinkedList の特徴

  • 要素の挿入・削除が高速: 位置が分かっている場合、add(i, e)、remove(i) は O(1)
  • 要素へのアクセスは低速: get(i)、set(i, e) は O(n) の時間計算量（先頭・末尾を除く）
  • List と Queue/Deque の両方として使用可能: List, Queue, Deque インターフェースを全て実装
  • メモリ使用量が多い: 各要素が前後への参照を保持するため、ArrayList より多くのメモリを使用
  • イテレーションは相対的に遅い: メモリの局所性が低いため、キャッシュミスが発生しやすい

LinkedList の基本的な使用例

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList の作成
        LinkedList<String> names = new LinkedList<>();
        
        // 要素の追加（List として使用）
        names.add("田中");
        names.add("佐藤");
        
        // 先頭・末尾への追加（Deque として使用）
        names.addFirst("山田");  // ["山田", "田中", "佐藤"]
        names.addLast("鈴木");   // ["山田", "田中", "佐藤", "鈴木"]
        
        // 先頭・末尾の要素を取得
        String first = names.getFirst();  // "山田"
        String last = names.getLast();    // "鈴木"
        
        // 先頭・末尾の要素を削除
        names.removeFirst();  // "山田"を削除 -> ["田中", "佐藤", "鈴木"]
        names.removeLast();   // "鈴木"を削除 -> ["田中", "佐藤"]
        
        // キューとして使用
        names.offer("高橋");   // ["田中", "佐藤", "高橋"]
        String head = names.poll();  // "田中"を取得して削除 -> ["佐藤", "高橋"]
        
        // スタックとして使用
        names.push("伊藤");    // ["伊藤", "佐藤", "高橋"]
        String top = names.pop();  // "伊藤"を取得して削除 -> ["佐藤", "高橋"]
    }
}

ArrayList と LinkedList の使い分け

操作 ArrayList LinkedList 推奨される実装
ランダムアクセス（get/set） O(1) - 高速 O(n) - 低速 ArrayList
先頭への追加/削除 O(n) - 低速 O(1) - 高速 LinkedList
末尾への追加 償却 O(1) - 高速 O(1) - 高速 ArrayList
中間への挿入/削除 O(n) - 低速 O(n) - 低速（ただし実際の操作は高速） LinkedList（位置が分かっている場合）
イテレーション 効率的 比較的非効率的 ArrayList
メモリ使用量 少ない 多い ArrayList

選択のガイドライン

  • ArrayListを選ぶ場合:
    • ランダムアクセス（get/set）が多い
    • リストサイズが比較的安定している
    • 主に末尾への追加操作が多い
    • メモリ効率が重要
  • LinkedListを選ぶ場合:
    • 頻繁な挿入・削除操作が多い（特に先頭/末尾）
    • スタックやキューとしても使用したい
    • リスト全体のイテレーションよりも要素の操作が主

Vector と Stack - レガシーな List 実装

Vector と Stack は Java 1.0 から存在する古い実装で、同期化されています（thread-safe）。一般的に、これらのレガシークラスの代わりに、ArrayList や LinkedList と Collections.synchronizedList() の組み合わせ、または java.util.concurrent パッケージのクラスを使用することが推奨されています。

同期化されたリストの作成

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

public class SynchronizedListExample {
    public static void main(String[] args) {
        // 非同期リスト
        List<Integer> numbers = new ArrayList<>();
        
        // 同期化されたリスト
        List<Integer> synchronizedList = Collections.synchronizedList(numbers);
        
        // 同期化されたリストを使用する場合、イテレーションには外部同期が必要
        synchronized (synchronizedList) {
            for (Integer number : synchronizedList) {
                // 安全にアクセス
                System.out.println(number);
            }
        }
    }
}

効率的なリスト操作のためのテクニック

1. 初期容量の指定

ArrayList を使用する際、あらかじめ必要な要素数が分かっている場合は、初期容量を指定することで再割り当てのオーバーヘッドを減らすことができます。

// 10,000要素を格納することが分かっている場合
List<String> largeList = new ArrayList<>(10000);

2. サブリストの活用

リストの一部だけを操作したい場合は、subList() メソッドを使用してビューを取得できます。これはオリジナルのリストを参照するため、メモリ効率が良いです。

List<String> fullList = new ArrayList<>();
// fullListに要素を追加...

// インデックス10から20までのサブリストを取得
List<String> subList = fullList.subList(10, 20);

// サブリストを操作するとオリジナルリストも変更される
subList.clear();  // fullListのインデックス10〜19の要素が削除される

3. リスト間の操作

複数のリスト間での操作には、containsAll()、addAll()、removeAll()、retainAll() などの便利なメソッドが用意されています。

List<String> list1 = new ArrayList<>();
list1.add("A"); list1.add("B"); list1.add("C");

List<String> list2 = new ArrayList<>();
list2.add("B"); list2.add("C"); list2.add("D");

// 和集合: list1とlist2の全要素（重複なし）
List<String> union = new ArrayList<>(list1);
union.addAll(list2);  // [A, B, C, B, C, D]

// 積集合: list1とlist2の共通要素
List<String> intersection = new ArrayList<>(list1);
intersection.retainAll(list2);  // [B, C]

// 差集合: list1にあってlist2にない要素
List<String> difference = new ArrayList<>(list1);
difference.removeAll(list2);  // [A]

4. リストのソート

リストは Collections.sort() メソッドまたは List.sort() メソッド（Java 8以降）を使用してソートできます。

List<Integer> numbers = new ArrayList<>();
numbers.add(5); numbers.add(2); numbers.add(8); numbers.add(1);

// 自然順序でのソート
Collections.sort(numbers);  // [1, 2, 5, 8]
// または
numbers.sort(null);  // Java 8以降

// カスタム比較器を使用したソート
numbers.sort((a, b) -> b - a);  // 降順 [8, 5, 2, 1]

Java 8以降の Stream API との連携

Java 8以降では、List は Stream API と組み合わせて強力なデータ処理が可能になります。

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class ListStreamExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("山田太郎"); names.add("鈴木一郎"); 
        names.add("佐藤花子"); names.add("田中次郎");
        
        // フィルタリング: "田"を含む名前だけを取得
        List<String> filteredNames = names.stream()
                .filter(name -> name.contains("田"))
                .collect(Collectors.toList());
        // [山田太郎, 田中次郎]
        
        // マッピング: 名前の長さのリストを作成
        List<Integer> nameLengths = names.stream()
                .map(String::length)
                .collect(Collectors.toList());
        // [4, 4, 4, 4]
        
        // ソート: 名前を長さでソート
        List<String> sortedNames = names.stream()
                .sorted((a, b) -> a.length() - b.length())
                .collect(Collectors.toList());
        // [山田太郎, 鈴木一郎, 佐藤花子, 田中次郎]
    }
}

まとめ

List インターフェースは Java コレクションフレームワークの中で最も広く使用されるインターフェースの一つです。適切な実装（ArrayList または LinkedList）を選択し、効率的な操作方法を理解することで、パフォーマンスを最適化できます。

  • ArrayList: ランダムアクセスが多い場合や、リスト全体の走査が頻繁な場合に適しています。
  • LinkedList: 頻繁な挿入・削除操作が必要な場合や、スタックやキューとしても使用したい場合に適しています。

多くの場合、ArrayList がデフォルトの選択肢として適しています。特定のユースケースで LinkedList が明確な利点を提供する場合にのみ、LinkedList の使用を検討してください。