C#でArrayListを作る

C#で動的配列の「ArrayList」を作ります! veilnuiです!

突然ですが、あなたは「コレクションフレームワーク」を知っていますか?
「java.utilパッケージ」「System.Collection.Generic名前空間」などにあるアレです。
それらコレクションフレームワークを自力で実装してみようと思います。

今回は配列リスト。すなわち「ArrayList」です。

機能

動的配列を名乗るためには、最低限の実装をしないといけません。

  • 末端に要素の追加
  • 指定位置に要素の追加
  • 等価の要素の削除
  • 指定位置の要素の削除

この他にもありますが、基本機能はこれです。
それ以外の機能は、この機能の組み合わせみたいなものです。

クラス宣言

public class ArrayList<E> {
  E[] array;
  int length;
}

クラスにはジェネリックを1つ指定。型安全のために必要です。
データ保存の配列と、現在の要素数を保存する数値型は必須です。

public int Length { private set; get; }

数値型は自動実装プロパティでもOKです。

要素の追加

まず、必要になるのは、要素を追加する「addメソッド」です。

ですが、要素を追加する前に、配列に空きがあるか確認する必要があります!
そのメソッドを実装しましょう!

public bool IsVacant () => return array.Length > length;

配列の要素数(array.length)が現在の要素数(index)より大きければ、空きがあります!
しかし、空きがなければ配列を拡張する必要があります!

Array.Resize (ref 配列, 要素数);

ArrayクラスにResizeメソッドがあるので、これを使います。
このメソッドは便利です。Javaには無かったです。

末端に要素を追加

public void Add (E element) {
  if (! IsVacant()) {
    Array.Resize (ref array, array.Length << 1);
  }
  array[length] = element;
  Length++;
}

指定位置に要素を追加

末端ではなく、指定位置に要素を追加する場合です。
このときは、各要素を1つづつ玉突きコピーして、スペースを作る必要があります。

Array.Copy (コピー元配列, コピー開始位置, ペースト先配列, ペースト開始位置, コピーする要素の数);

ArrayクラスにCopyメソッドがあるので、これを使います。
引数が多いですが、使い方を覚えてしまえば簡単です。

public void Add (E element, int index) {
  if (! Isvacant()) {
    Array.Resize(ref array, array.Length << 1);
  }
  Array.Copy(array, index, array, index + 1, array.Lengh - index);
  array[index] = element;
  Length++;
}

指定位置の要素の削除

要素を削除するときは、配列の空きを気にする必要がありません。
Array.Copyで後ろの要素を1つづつ玉突きコピーしていきます。

public void Remove(int index) {
  Array.Copy(array, index + 1, array, index, Length - index - 1);
  Length++;
}

注意点ですが、Array.Copyは、要素をコピーした後にパティングを行いません。
パティングを行う場合は、次のソースも必要です。

array[Length - 1] = default;

等価の要素の削除

配列内から、同じ要素を探すために「Array.IndexOfメソッド」を使います。
このメソッドは、配列の先頭から末端にかけて線形探索(リニアサーチ)で要素を探します。

逆側から線形探索したいときは「Array,LastIndexOfメソッド」です。

なお、二分探索(バイナリサーチ)で要素を探したい場合は「Array.BinarySearchメソッド」です。

public bool Remove(E element) {
  int index = Array.IndexOf(array, element);
  if(index != -1) {
    Remove(index);
    return true;
  } else {
    return false;
  }
}

「Array.IndexOf」「Array.BinarySearch」は、要素が見つからないときに「-1」を返してきます。
なお「Array.BinarySearch」は、配列がソート済みであることが条件です。
そのため、基本的には「Array.IndexOf」を使います。

あとは、要素のインディックスで「Remove(int index)メソッド」を呼べば良いだけです。

ひとこと

「ArrayList」は実装が楽です。
ですが、ArrayListと対を成す「LinkedList」は比べられないくらい難しく複雑です。

コメント

タイトルとURLをコピーしました