【Unity】C#のCollection LinkedList

Collectionとは？

C#のCollection(コレクション)とは、複数の要素を管理、操作するためのデータ構造の総称です。

データの集まりを効率的に操作するための方法を提供して、要素の追加や削除などの操作をサポートします。

LinkedList

LinkedListは双方向連結リストと呼ばれます。

以下の特徴があります。

各要素が前後の要素への参照を保持するノードとして構成されている
Listよりもより効率的な要素の挿入、及び削除操作を実現
添え字を使ったランダムなアクセスには向かない

初期化

以下の場合、int型のLinkedListを作成します。

LinkedListを使用するには、 using System.Collections.Generic;

が必要です。

LinkedList<int> linkedList = new LinkedList<int>()

最後に追加

リストの最後に要素を追加します。

linkedList.AddLast(10);

先頭に追加

リストの先頭に要素を追加します。

linkedList.AddFirst(1);

前に追加

値が1の要素を取得し、その前に追加します。

LinkedListNode<int> node = list.Find(1);
linkedList.AddBefore(node, 0);

後に追加

値が1の要素を取得し、その後に追加します。

LinkedListNode<int> node = list.Find(1);
linkedList.AddLst(node, 1000);

削除

値が1の様を削除します。

linkedList.Remove(1);

最初を削除

先頭の要素を削除します。

linkedList.RemoveFirst();

最後を削除

最後の要素を削除します。

linkedList.RemoveLast();

検索

指定した要素を持つ最初のノードを検索します。

LinkedListNode<int> node = linkedList.Find(1);

要素を先頭から順にアクセスする

LinkedList<int>型双方向連結リストの要素は、LinkedListNode<int>型ノードになっています。

ノードはPrevに前のノード、Nextに次のノードの参照を持っています。

以下の様に先頭のノードからノードのNextを順々に辿って最後のノードまで見ることが出来ます。

次が無い場合はNextがnullになっています。

LinkedListNode<int> node = linkedList.First;
while(node != null)
{
    Debug.Log($"{node.Value}");
    node = node.Next;
}

逆に最後からPrevを辿っていけば最初のノードまで見ることが出来ます。

Valueで値を取得できます。

LinkedListの向き不向き

向いている

頻繁な挿入と削除
- 挿入も削除もノードを繋ぎ直すだけなので効率よく行えます
順番にアクセスする
- 前の要素、次の要素を順々にアクセスするのに向いています
リストのサイズが変動する
- 追加もノードを繋ぎ直すだけなので効率よく行えます

向いていない

ランダムなアクセス
- 添え字によるアクセスが必要な場合は、ListやArrayが向いています
メモリ効率が重要な場合
- 各ノードが値以外に前後の参照を持つため、若干メモリを多く使用します

主な用途

例ではint型でしたが正直使い道があまりないです。

Unity上で使用する場合はGameObjectを渡せるように、LinkedList<GameObject>のリストを作るのがいいでしょう。

私がよくやるのは、

// 未使用リスト
private LinkedList<GameObject> _freeList;
// 使用中リスト
private LinkedList<GameObject> _usedList;

のように使用中と未使用の双方向連結リストを用意し、

未使用リストにInstantiateしたエフェクト用プレハブなどを突っ込んで簡易的なObjectPoolとして使用しています。

エフェクトが必要な場合は、_freeListから先頭を取り出し_usedListの最後に移動します。

使い終わったら_usedListから_freeListに戻します。

これにより都度Instantiateするコストが抑えられ、未使用のエフェクトを探すコストも抑えられます。

まとめ

LinkedListというCollectionについて解説しました。

Listと似ていますが、若干扱いづらいかもしれません。

上級者向けかもしれませんが、うまく使えそうなら活用してみてください。

GARNET LOG