辞書付き双方向リスト

LinkedListDictionary.cs

public class LinkedListDictionary<T> : IEnumerable<T>
    where T : IEquatable<T>
{
    private class Node
    {
        public T Value { get; set; }
        public Node Prev { get; set; }
        public Node Next { get; set; }
    }

    private readonly Dictionary<T, Node> _Data = new Dictionary<T, Node>();
    private Node _First;
    private Node _Last;

    public int Count => this._Data.Count;
    public T First => this._First != null ? this._First.Value : default(T);
    public T Last => this._Last != null ? this._Last.Value : default(T);

    public LinkedListDictionary()
    {
    }

    public LinkedListDictionary(IEnumerable<T> collection)
    {
        foreach (var item in collection)
        {
            this.AddLast(item);
        }
    }

    // O(1)
    public bool TryAddBefore(T newValue, T existingValue)
    {
        if (!this._Data.TryGetValue(existingValue, out var existingNode)) return false;

        var newNode = new Node { Value = newValue, Prev = existingNode.Prev, Next = existingNode };
        this._Data.Add(newValue, newNode);

        if (existingNode.Prev == null) this._First = newNode;
        else existingNode.Prev.Next = newNode;

        existingNode.Prev = newNode;
        return true;
    }

    // O(1)
    public bool TryAddAfter(T existingValue, T newValue)
    {
        if (!this._Data.TryGetValue(existingValue, out var existingNode)) return false;

        var newNode = new Node { Value = newValue, Prev = existingNode, Next = existingNode.Next };
        this._Data.Add(newValue, newNode);

        if (existingNode.Next == null) this._Last = newNode;
        else existingNode.Next.Prev = newNode;

        existingNode.Next = newNode;
        return true;
    }

    // O(1)
    public void AddFirst(T value)
    {
        var node = new Node { Value = value };
        this._Data.Add(value, node);

        if (this.Count == 1)
        {
            this._First = node;
            this._Last = node;
            return;
        }

        node.Next = this._First;
        this._First.Prev = node;
        this._First = node;
    }

    // O(1)
    public void AddLast(T value)
    {
        var node = new Node { Value = value };
        this._Data.Add(value, node);

        if (this.Count == 1)
        {
            this._First = node;
            this._Last = node;
            return;
        }

        node.Prev = this._Last;
        this._Last.Next = node;
        this._Last = node;
    }

    // O(1)
    public bool TryRemove(T value)
    {
        if (!this._Data.TryGetValue(value, out var node)) return false;

        if (node.Prev == null) this._First = node.Next;
        else node.Prev.Next = node.Next;

        if (node.Next == null) this._Last = node.Prev;
        else node.Next.Prev = node.Prev;

        this._Data.Remove(value);
        return true;
    }

    // O(1)
    public void Clear()
    {
        this._Data.Clear();
        this._First = null;
        this._Last = null;
    }

    // O(1)
    public bool Contains(T value)
    {
        return this._Data.ContainsKey(value);
    }

    public IEnumerator<T> GetEnumerator()
    {
        // 本来は列挙中のリスト操作で例外を出すべき
        var current = this._First;
        for (var i = 0; i < this.Count; i++)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}