【C#】最大容量付きのLinkedListを実装してみる

はじめに

今回は最大容量付きのLinkedListを実装してみる記事になります！

まずLinkedListとはListとは違いインデックスによる要素の指定はできませんが、挿入と削除の操作を高速(計算量 $o(1)$ )で行うことができるコレクションです。

イメージとしてはキューに近い？ですが、両端において挿入・削除が行えます。

今回はLinkedListに最大容量付きをつけてみようといことですが、どういうことかというと以下の画像を見ていただくのがわかりやすいと思います。

f:id:hanaaaaaachiru:20200428172934p:plain

そもそもリストに容量が必要なのかという点もありますが、このようなものが必要になったのでやっていきます。

はじめに
コード
使い方
さいごに

コード

public class FixedLinkedList<T> : IEnumerable<T>
{
    private LinkedList<T> _list;

    public int Count => _list.Count;
    public LinkedListNode<T> First => _list.First;
    public LinkedListNode<T> Last => _list.Last;

    public int Capacity { get; private set; }

    public FixedLinkedList(int capacity)
    {
        Capacity = capacity;
        _list = new LinkedList<T>();
    }

    public FixedLinkedList(IEnumerable<T> collection)
    {
        Capacity = collection.Count();
        if (collection != null) _list = new LinkedList<T>(collection);
        else _list = new LinkedList<T>();
    }

    public LinkedListNode<T> AddLast(T item) {
        var value = _list.AddLast(item);
        if(Count > Capacity) _list.RemoveFirst();
        return value;
    }
    public LinkedListNode<T> AddFirst(T item)
    {
        var value = _list.AddFirst(item);
        if (Count > Capacity) _list.RemoveLast();
        return value;
    }

    public void RemoveFirst() => _list.RemoveFirst();

    public void RemoveLast() => _list.RemoveLast();

    public IEnumerator<T> GetEnumerator() => _list.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => _list.GetEnumerator();
}

使い方

static void Main(string[] args)
{
    // 最大容量が3のLinkedList
    var list = new FixedLinkedList<int>(3);

    list.AddFirst(1);       // 1
    list.AddFirst(2);       // 2 1
    list.AddLast(3);        // 2 1 3

    list.AddFirst(4);       // 4 2 1
    list.AddLast(5);        // 2 1 5
}