双方向リスト

# BidirectionalList, IndexedBidirectionalList
BidirectionalList 双方向リスト
IndexedBidirectionalList 双方向リスト(栞付き)
IndexedBidirectionalList はインデクサ[]でのアクセスが早くなっています
# Combination
双方向リストの優位性(List と比べて)を検証するためのクラス
# Cache
双方向リストと Dictionary を組み合わせた特殊用途のクラス

```c#:BidirectionalList.cs
//#define INSPECTION
//#define DIAGNOSTICS
#if INSPECTION || DIAGNOSTICS
using System.Windows.Forms;
#endif
#if DIAGNOSTICS
using System.Diagnostics;
#endif

namespace System.Collections.Generic
{
    public class BidirectionalList<T>
    {//双方向リスト

        protected class Element
        {
            public T t;

            public Element prev, next;

            public Element(T t, Element prev, Element next)
            {
                this.t = t;
                this.prev = prev;
                this.next = next;
            }
        }

        protected Element top, last;

        protected int count;

        public int Count
        {
            get
            {
                return count;
            }
        }

        public BidirectionalList()
        {
            Clear();
        }

        public void Clear()
        {
            top = last = null;

            count = 0;
        }

        public void Add(T t)
        {
            count++;

            if (last == null)
            {
                Element e = new Element(t, null, null);
                top = last = e;
            }
            else
            {
                Element e = new Element(t, last, null);
                last.next = e;
                last = e;
            }
        }

        public void AddRange(IEnumerable<T> collection)
        {
            int collection_count;

            if (collection == null || (collection_count = collection.Count()) <= 0)
            {
                return;
            }

            int i = 0;

            if (last == null)
            {
                Element e = new Element(collection.ElementAt(0), null, null);
                top = last = e;

                i++;
            }

            for (; i < collection_count; i++)
            {
                Element e = new Element(collection.ElementAt(i), last, null);
                last.next = e;
                last = e;
            }

            count += collection_count;
        }

        public void Push(T t)
        {
            count++;

            if (top == null)
            {
                Element e = new Element(t, null, null);
                top = last = e;
            }
            else
            {
                Element e = new Element(t, null, top);
                top.prev = e;
                top = e;
            }
        }

        public T Pop()
        {
            if (top == null)
            {
                throw new InvalidOperationException();
            }

            T t = top.t;

            if (top.next == null)
            {
                top = last = null;
            }
            else
            {
                top.next.prev = null;
                top = top.next;
            }

            count--;

            return t;
        }

        public T Pop(int index)
        {
            if ((uint)index >= (uint)count)
            {
                throw new IndexOutOfRangeException();
            }

            T t;

            if (index == 0)
            {
                t = top.t;

                if (top.next == null)
                {
                    top = last = null;
                }
                else
                {
                    top.next.prev = null;
                    top = top.next;
                }
            }
            else if (index == count - 1)
            {
                t = last.t;
                last.prev.next = null;
                last = last.prev;
            }
            else
            {
                Element e = At(index);

                t = e.t;

                e.next.prev = e.prev;
                e.prev.next = e.next;
            }

            count--;

            return t;
        }

        public void RemoveAt(int index)
        {
            if ((uint)index >= (uint)count)
            {
                return;
            }

            if (index == 0)
            {
                if (top.next == null)
                {
                    top = last = null;
                }
                else
                {
                    top.next.prev = null;
                    top = top.next;
                }
            }
            else if (index == count - 1)
            {
                last.prev.next = null;
                last = last.prev;
            }
            else
            {
                Element e = At(index);

                e.next.prev = e.prev;
                e.prev.next = e.next;
            }

            count--;
        }

        protected Element At(int index)
        {
            if (index >= count / 2)
            {
                Element e = last;

                int i = count - 1 - index;

                for (; i > 0; i--)
                {
                    e = e.prev;
                }

                return e;
            }
            else
            {
                Element e = top;

                int i = index;

                for (; i > 0; i--)
                {
                    e = e.next;
                }

                return e;
            }
        }

        public T this[int index]
        {
            set
            {
                if ((uint)index >= (uint)count)
                {
                    throw new IndexOutOfRangeException();
                }

                Element e = At(index);

                e.t = value;
            }

            get
            {
                if ((uint)index >= (uint)count)
                {
                    throw new IndexOutOfRangeException();
                }

                Element e = At(index);

                return e.t;
            }
        }
    }

    public class IndexedBidirectionalList<T> : BidirectionalList<T>
    {//双方向リスト(インデックス付き)

        protected List<Element> indexes;

        protected int indexes_interval;

        public IndexedBidirectionalList(int indexes_interval = 1000)
        {
            if (indexes_interval <= 1)
            {
                throw new ArgumentOutOfRangeException();
            }

            //top = last = null;

            //count = 0;

            indexes = new List<Element>();

            this.indexes_interval = indexes_interval;
        }

        public new void Clear()
        {
            base.Clear();

            //top = last = null;

            //count = 0;

            indexes.Clear();
        }

        public new void Add(T t)
        {
            count++;

            if (last == null)
            {
                Element e = new Element(t, null, null);
                top = last = e;
            }
            else
            {
                Element e = new Element(t, last, null);
                last.next = e;
                last = e;

                if (count > (indexes.Count + 1) * indexes_interval)
                {
                    indexes.Add(e);
                }
            }
        }

        public new void AddRange(IEnumerable<T> collection)
        {
            int collection_count;

            if (collection == null || (collection_count = collection.Count()) <= 0)
            {
                return;
            }

            int i = 0;

            if (last == null)
            {
                Element e = new Element(collection.ElementAt(0), null, null);
                top = last = e;

                count++;
                i++;
            }

            int n = (indexes.Count + 1) * indexes_interval;

            for (; i < collection_count; i++)
            {
                Element e = new Element(collection.ElementAt(i), last, null);
                last.next = e;
                last = e;

                count++;

                if (count > n)
                {
                    indexes.Add(e);

                    n += indexes_interval;
                }
            }
        }

        public new void Push(T t)
        {
            if (top == null)
            {
                Element e = new Element(t, null, null);
                top = last = e;
            }
            else
            {
                Element e = new Element(t, null, top);
                top.prev = e;
                top = e;
            }

            count++;

            for (int i = 0; i < indexes.Count; i++)
            {
                indexes[i] = indexes[i].prev;
            }

            if (count > (indexes.Count + 1) * indexes_interval)
            {
                indexes.Add(last);
            }
        }

        protected new Element At(int index)
        {
            if (index <= indexes_interval)
            {
                if (count <= indexes_interval && index >= count / 2)
                {
                    Element e = last;

                    int i = count - 1 - index;

                    for (; i > 0; i--)
                    {
                        e = e.prev;
                    }

                    return e;
                }
                else if (indexes.Count > 0 && index >= indexes_interval / 2)
                {
                    Element e = indexes[0];

                    int i = indexes_interval - index;

                    for (; i > 0; i--)
                    {
                        e = e.prev;
                    }

                    return e;
                }
                else
                {
                    Element e = top;

                    int i = index;

                    for (; i > 0; i--)
                    {
                        e = e.next;
                    }

                    return e;
                }
            }
            else
            {
                int n1 = (index / indexes_interval) - 1;

                int n2 = index - ((n1 + 1) * indexes_interval);

                int n3, n4;

                if (n1 < indexes.Count - 1 && n2 >= indexes_interval / 2)
                {
                    n3 = indexes_interval - n2;

                    Element e = indexes[n1 + 1];

                    for (; n3 > 0; n3--)
                    {
                        e = e.prev;
                    }

                    return e;
                }
                else if ((n3 = index - (indexes.Count * indexes_interval)) > 0 && n3 > (n4 = count - index - 1))
                {
                    Element e = last;

                    for (; n4 > 0; n4--)
                    {
                        e = e.prev;
                    }

                    return e;
                }
                else
                {
                    Element e = indexes[n1];

                    for (; n2 > 0; n2--)
                    {
                        e = e.next;
                    }

                    return e;
                }
            }
        }

        public new T Pop()
        {
            if (top == null)
            {
                throw new InvalidOperationException();
            }

            T t = top.t;

            if (top.next == null)
            {
                top = last = null;
            }
            else
            {
                top.next.prev = null;
                top = top.next;
            }

            count--;

            for (int i = 0; i < indexes.Count; i++)
            {
                indexes[i] = indexes[i].next;
            }

            if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
            {
                indexes.RemoveAt(indexes.Count - 1);
            }

            return t;
        }

        public new T Pop(int index)
        {
            if ((uint)index >= (uint)count)
            {
                throw new IndexOutOfRangeException();
            }

            T t;

            if (index == 0)
            {
                t = top.t;

                if (top.next == null)
                {
                    top = last = null;
                }
                else
                {
                    top.next.prev = null;
                    top = top.next;
                }
            }
            else if (index == count - 1)
            {
                t = last.t;
                last.prev.next = null;
                last = last.prev;
            }
            else
            {
                Element e = At(index);

                t = e.t;

                e.next.prev = e.prev;
                e.prev.next = e.next;
            }

            count--;

            for (int i = (index - 1) / indexes_interval; i < indexes.Count; i++)
            {
                indexes[i] = indexes[i].next;
            }

            if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
            {
                indexes.RemoveAt(indexes.Count - 1);
            }

            return t;
        }

        public new void RemoveAt(int index)
        {
            if ((uint)index >= (uint)count)
            {
                return;
            }

            if (index == 0)
            {
                if (top.next == null)
                {
                    top = last = null;
                }
                else
                {
                    top.next.prev = null;
                    top = top.next;
                }
            }
            else if (index == count - 1)
            {
                last.prev.next = null;
                last = last.prev;
            }
            else
            {
                Element e = At(index);

                e.next.prev = e.prev;
                e.prev.next = e.next;
            }

            count--;

            for (int i = (index - 1) / indexes_interval; i < indexes.Count; i++)
            {
                indexes[i] = indexes[i].next;
            }

            if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
            {
                indexes.RemoveAt(indexes.Count - 1);
            }
        }

        public new T this[int index]
        {
            set
            {
                if ((uint)index >= (uint)count)
                {
                    throw new IndexOutOfRangeException();
                }

                Element e = At(index);

                e.t = value;
            }

            get
            {
                if ((uint)index >= (uint)count)
                {
                    throw new IndexOutOfRangeException();
                }

                Element e = At(index);

                return e.t;
            }
        }
    }

    public static class Combination
    {
#if DIAGNOSTICS
        public class Diagnostics
        {
            Stopwatch sw;

            public long ms;

            public Diagnostics()
            {
                sw = new Stopwatch();
                Clear();
            }

            public void Start()
            {
                Clear();
                sw.Restart();
            }

            public void Stop()
            {
                sw.Stop();
                ms = sw.ElapsedMilliseconds;
            }

            public void Clear()
            {
                ms = 0;
            }
        }

        public static Diagnostics diagnostics = new Diagnostics();
#endif

#if INSPECTION
        public static IConsole log;
#endif

        public static bool Raffle<T>(IList<T> il, int n, out T[] a, Random rnd = null)
        {//IList<T> il から int n 個を抽選して T[] a に取得する
            if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
            {
                a = null;
                return false;
            }

#if INSPECTION
            if (log == null)
            {
                a = null;
                return false;
            }
#endif
            a = new T[n];

            if (il.Count == n)
            {
                for (int i = 0; i < n; i++)
                {
                    a[i] = il[i];
                }
            }
            else
            {
                if (rnd == null)
                {
                    rnd = new Random();
                }

#if DIAGNOSTICS
                diagnostics.Start();
#endif
                IndexedBidirectionalList<int> bil = new IndexedBidirectionalList<int>();
#if INSPECTION
                List<int> l2 = new List<int>(il.Count);
#endif
                for (int i = 0; i < il.Count; i++)
                {
                    bil.Add(i);
#if INSPECTION
                    l2.Add(i);
#endif
                }

                for (int i = 0; i < n; i++)
                {
                    int index1 = rnd.Next(bil.Count);

                    int index2 = bil.Pop(index1);

                    a[i] = il[index2];
#if INSPECTION
                    l2.RemoveAt(index1);
#endif
                }

#if DIAGNOSTICS
                diagnostics.Stop();
#endif

#if INSPECTION
                bool error = false;

                if (bil.Count != l2.Count)
                {
                    log.WriteLine("Error1 bl.Count != l.Count");

                    error = true;
                }
                else
                {
                    for (int i = 0; i < l2.Count; i++)
                    {
                        //if (Comparer<T>.Default.Compare(bil[i], l[i]) != 0)
                        if (bil[i] != l2[i])
                        {
                            log.WriteLine("Error2 index = {0} bl[index] = {1} l[index] = {2}", i, bil[i], l2[i]);

                            error = true;

                            break;
                        }
                    }
                }

                if (!error)
                {
                    log.WriteLine("No Error");
                }
#endif
            }

            return true;
        }

#if DIAGNOSTICS
        public static bool Raffle_List<T>(IList<T> il, int n, out T[] a, Random rnd = null)
        {//IList<T> il から int n 個を抽選して T[] a に取得する

            if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
            {
                a = null;
                return false;
            }

            a = new T[n];

            if (il.Count == n)
            {
                for (int i = 0; i < n; i++)
                {
                    a[i] = il[i];
                }
            }
            else
            {
                if (rnd == null)
                {
                    rnd = new Random();
                }

                diagnostics.Start();

                List<int> l = new List<int>(il.Count);

                for (int i = 0; i < il.Count; i++)
                {
                    l.Add(i);
                }

                for (int i = 0; i < n; i++)
                {
                    int index1 = rnd.Next(l.Count);

                    int index2 = l[index1];

                    a[i] = il[index2];

                    l.RemoveAt(index1);
                }

                diagnostics.Stop();
            }

            return true;
        }

        public static bool Raffle_BidirectionalList<T>(IList<T> il, int n, out T[] a, Random rnd = null)
        {//IList<T> il から int n 個を抽選して T[] a に取得する

            if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
            {
                a = null;
                return false;
            }

            a = new T[n];

            if (il.Count == n)
            {
                for (int i = 0; i < n; i++)
                {
                    a[i] = il[i];
                }
            }
            else
            {
                if (rnd == null)
                {
                    rnd = new Random();
                }

                diagnostics.Start();

                BidirectionalList<int> l = new BidirectionalList<int>();

                for (int i = 0; i < il.Count; i++)
                {
                    l.Add(i);
                }

                for (int i = 0; i < n; i++)
                {
                    int index1 = rnd.Next(l.Count);

                    int index2 = l[index1];

                    a[i] = il[index2];

                    l.RemoveAt(index1);
                }

                diagnostics.Stop();
            }

            return true;
        }
#endif
    }

    public class Cache<Key, Value>
    {
        protected class Element
        {
            public Key key;

            public Value value;

            public Element prev, next;

            public Element(Key key, Value value, Element prev, Element next)
            {
                this.key = key;
                this.value = value;
                this.prev = prev;
                this.next = next;
            }
        }

        protected Dictionary<Key, Element> dictionary;

        protected Element top, last;

        protected int max_element_count;

        public Cache(int max_element_count)
        {
            if (max_element_count <= 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            dictionary = new Dictionary<Key, Element>();

            top = last = null;

            this.max_element_count = max_element_count;
        }

        public int Count
        {
            get
            {
                return dictionary.Count;
            }
        }

        public void Clear()
        {
            dictionary.Clear();

            top = last = null;
        }

        public delegate void CallbackHandler(Value value);

        public CallbackHandler Removed = null;

        public void Add(Key key, Value value)
        {
            Element e;

            if (top == null)
            {
                e = new Element(key, value, null, null);

                last = e;
            }
            else
            {
                e = new Element(key, value, null, top);

                top.prev = e;
            }

            top = e;

            if (dictionary.Count >= max_element_count)
            {
                dictionary.Remove(last.key);

                last.prev.next = null;

                last = last.prev;

                if (Removed != null)
                {
                    Removed(last.value);
                }
            }

            dictionary.Add(key, e);
        }

        public bool TryGetValue(Key key, out Value value)
        {
            Element e;

            if (!dictionary.TryGetValue(key, out e))
            {
                value = default(Value);

                return false;
            }

            value = e.value;

            if (e.prev != null)
            {
                if (e.next == null)
                {
                    e.prev.next = null;

                    last = e.prev;
                }
                else
                {
                    e.prev.next = e.next;
                    e.next.prev = e.prev;
                }

                top.prev = e;
                e.next = top;
                e.prev = null;
                top = e;
            }

            return true;
        }
    }
}