はじめに
プログラミング学習を始めて、Java覚えたてで開発していたころ
先輩からリストと配列の違いを聞かれて答えられず、困惑したのを思い出しました。
実務を重ねて3年、ようやっと実感として理解が深まってきたので
備忘録としてメモ程度ですがまとめておこうと思います。
配列のデータ構造
- 要素を一列に並べて管理する
- 最初から固定の要素数でメモリを確保する
- 用意した要素数が連続した領域にメモリとして確保される
- 添え字を使ってメモリアドレスを直接指定できるので要素へのアクセスが速い
- 途中に要素を挿入したり追加したりするには元にあった要素をズラす必要があり大変
＊ Javaの配列操作例
ArrayExample.java
// 4つの要素が入るint型の配列を作成
int array[] = new int[4];
// 各要素に任意の数字を格納（何も追加しなければ初期値は0）
array[0] = 5;
array[1] = 2;
array[2] = 8;
array[3] = 16;
// 2番目の要素（添え字[1]）を4に変更する
array[1] = 4; // 単純に上書きすれば良い
// 配列の要素数を5個に増やす→簡単にはできない
// 別の配列を作ってコピーする必要がありサイズによってはメモリ負荷が倍増
// （実装方法はさまざま。ここでは一例を）
int box[] = new int[5];
System.arraycopy(array, 0, box, 0, 4); // arrayの中身をbox[0]〜4つ分コピー
リストのデータ構造
- 要素を一列に並べて管理する
- 要素数が可変できる
- 前後にポインタが付与されポインタで接続されながらあいているメモリ領域に要素が格納されていく
- 要素にアクセスするには先頭からポインタを辿っていく必要があり時間がかかる
- 途中に要素を挿入したり、削除したりするにはポインタの接続を変えるだけなので速い
＊ Javaのリスト操作例
Javaのリストの場合、厳密にはArrayListとLinkedListで
データへのアクセス方法が異なるため処理時間が微妙に違ってきます。
ここでは、配列と比較するためLinkedListの例を実装します。
ListExample.java
// importなどは省略
// String型を格納できるリストを生成
LinkedList<String> mojiList = new LinkedList<String>();
// 任意の文字列をリストに追加（いくつでも）
mojiList.add("ひとつめ");
mojiList.add("ふたつめ");
mojiList.add("みっつめ");
// 「ふたつめ」を「二つ目」に変更
mojiList.set(1, "二つ目");
// 3番目に入っている要素を取得
// (実際はポインターを辿ってアクセスするため処理時間が配列よりもかかる)
String moji = mojiList.get(2); // 「みっつめ」が返る
// 「ひとつめ」の直後に「一つ目」を挿入→「二つ目」が後ろにずれる
// （ポインターをつけかえるだけなので処理速度は速い）
mojiList.add(1,"一つ目");
// 指定した位置にある要素を削除
mojiList.remove(2); // 「二つ目」が削除される
// このほか、LinkedListには先頭の要素へのみ処理を行うメソッドもあります
mojiList.remove(); // 先頭の要素、「ひとつめ」を削除
まとめ
要するに、配列もリストも「データを一列に並べる」という点では同様。
ただし、どちらにもメリット・デメリットがあります。
| メリット | デメリット | |
|---|---|---|
| 配列 | 各データへのアクセスが容易で処理時間を短縮可能 | データの追加、挿入や、削除に時間がかかる |
| リスト | 追加箇所にアクセスできていれば、データの追加や削除が容易 | 特定のデータにアクセスするためにリストの先頭から辿る必要がある |
データにアクセスすることが多い場合は配列、
データの追加・削除が頻繁に行われる処理にはリスト、
と使い分けが重要になるみたいです。
とはいえ最近のコンピュータ性能からすると
どこまで気にするべきかは疑問。
Javaに限っていえば、配列かリストかに加えて、
ArrayListを使うのかLinkedListを使うのか、も念頭に置いたほうがよい。
参考：LinkedList と ArrayList の使い分け方
おわりに
データ構造やアルゴリズムについては以下の書籍を参考に勉強しました。
いきなりプログラミング学習から入るのではなく、
並行してデータ構造、アルゴリズムの基礎も頭にいれていたほうが良いですね。
なお、簡単なソースコードの検証にはpaiza.ioが便利です。
＊ お願い
間違えている情報やリンク切れがありましたらどうぞご指摘ください。