Listとは？
順序があって重複も許容するルールを持つデータ構造です。個人的には最もよく使うデータ構造だと思います。Java では、List インターフェースを実装したクラスを使って利用します。
List を作るときに考えるべきことは「データをどのように線形につなげるか」という点です。データを線形に扱うための基礎的な仕組みを使って、List を作ってみましょう。
ArrayList
ArrayListは、配列を利用してListを実装した実装クラスです。そのため、配列の特徴を理解しておく必要があります。
高速なインデックスアクセス
- インデックスを使って O(1) で目的の要素にアクセスできます。
- これは「配列がメモリ上で連続配置されている」ことによるメリットです。
“固定サイズ”が最大の課題
- 予想以上にデータが増えると、配列の許容範囲を超えてしまいます。
- 逆に大きく取りすぎると、未使用領域が無駄になります。
フィールド設計 & コンストラクタ設計
- 望むデータ型だけを扱いたいのでジェネリクスを使います。
- 配列の長さ (length) と実際に値が格納されるサイズ (size) は異なるので、分けて管理する必要があります。
class MyArrayList<T> {
private T[] array;
private int size;
MyArrayList(){
array = (T[]) new Object[10];
size = 0;
}
}
メソッド設計
- シンプルに CRUD (作成・読み取り・更新・削除) だけ実装してみます。
- 例外処理など詳しい部分は割愛している部分があります。
基本的には、これくらいの必須メソッドがあると便利です。
class MyArrayList<T> {
private T[] array;
private int size;
MyArrayList(){
array = (T[]) new Object[10];
size = 0;
}
public void add(Object param) {
//..
}
public T get(int index) {
//..
}
public T update(int index, Object param) {
//..
}
public T delete(int index) {
//..
}
public int size(){
//..
}
}
これらのメソッドは、List を実装するときに基本的に備わっているものです。将来、他の実装が出てくることを考えて、インターフェースで設計しておきましょう。
interface MyList<T> {
void add(T param);
T get(int index);
T update(int index, T param);
T delete(int index);
int size();
}
class MyArrayList<T> implements MyList<T> {
private T[] array;
private int size;
MyArrayList(){
array = (T[]) new Object[10];
size = 0;
}
@Override
public void add(Object param) {
//..
}
@Override
public T get(int index) {
//..
}
@Override
public T update(int index, Object param) {
//..
}
@Override
public T delete(int index) {
//..
}
@Override
public int size(){
//..
}
}
メソッド実装 - add() & get()
まずは簡単に、配列に値を追加するメソッドを作ります。このロジックでは、作成した配列に型変換 (キャスト) を行った上で値を代入し、保存が完了したら size を 1 増やします。
@Override
public void add(Object param) {
array[length] = (T) param;
size++;
}
そして、保存された値を確認するために get メソッドも作ります。
@Override
public T get(int index) {
return array[index];
}
テストしてみると、無事に値の追加と取得ができるようになりました。しかし、MyArrayList には大きな問題があります。
public class TestMyList {
public static void main(String[] args) {
MyList<String> myList = new MyArrayList<>();
myList.add("a");
myList.add("b");
System.out.println(myList.get(0));
System.out.println(myList.get(1));
}
}
class MyArrayList<T> implements MyList<T> {
private T[] array;
private int size;
MyArrayList(){
array = (T[]) new Object[10];
size = 0;
}
@Override
public void add(Object param) {
array[length] = (T) param;
size++;
}
@Override
public T get(int index) {
return array[index];
}
@Override
public T update(int index, Object param) {
}
@Override
public T delete(int index) {
}
@Override
public int size() {
}
}
インスタンスを作るときに設定した配列のサイズを超えると、MyArrayList はこれ以上使えなくなります。List のデータ構造を実装するには、size が配列の length と同じになったときに、動的に配列を拡張する必要があります。
public class TestMyList {
public static void main(String[] args) {
MyList<String> myList = new MyArrayList<>();
myList.add("a");
myList.add("b");
myList.add("c");
myList.add("d");
myList.add("e");
myList.add("f");
myList.add("g");
myList.add("h");
myList.add("i");
myList.add("j");
myList.add("k"); // ここでエラー!
}
}
以下のように書き足せば、配列がいっぱいになったときにさらに大きい配列を用意できるようになります。
@Override
public void add(Object param) {
if (size >= array.length) {
T[] newArray = (T[]) new Object[array.length * 2];
for (int i = 0; i < array.length; i++) {
newArray[i] = array[i];
}
array = newArray;
}
array[size] = (T) param;
size++;
}
メソッド実装 - update() & delete()
続いて、更新 (update) と削除 (delete) も実装します。
更新は簡単です。配列はインデックスがわかれば直接値を取得できるので、その値を変えてあげるだけです。
@Override
public T update(int index, Object param) {
T returnValue = array[index];
array[index] = (T) param;
return returnValue;
}
削除機能はもう少し工夫が必要です。配列で値を削除すると、その場所が空いてしまいます。そこで、この空いた部分を詰める処理を行います。
まず、削除対象の値をリターン用に保存しておきます。その後、削除する要素の後ろにある要素を一つずつ前へずらして詰めます。そして、最後に要素が入っている場所を null に変更します。
size も 1 減らすのを忘れずに行います。
@Override
public T delete(int index) {
T returnValue = array[index];
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[size - 1] = null;
size--;
return returnValue;
}
基本的な機能は完成...
ここまで非常に簡単な ArrayList を作成してみました。プログラミング言語に備わっている実際の ArrayList の実装には、さらに多くの機能があります。
MyArrayList では例外処理がまったく行われておらず、リストを便利に扱うための補助的な機能も用意されていません。
とはいえ、「ArrayList」というリストのデータ構造を実装する仕組みそのものは、大きく変わるわけではないでしょう。
LinkedList(未完成)
、、、