using System;

namespace Test
{
    class List<T>
    {
        public List(int capacity = 10)
        {
            Data = new ListItem<T>[capacity];
            FreeCells = new int[capacity];
            Head = -1;
            Tail = -1;
            Free = 0;
            Capacity = capacity;
            FreeCells[FreeCells.Length - 1] = -1;
            for (int i = 0; i < FreeCells.Length - 1; i++)
            {
                FreeCells[i] = i + 1;
            }
        }

        public void Add(T value)
        {
            Data[Free].Value = value;
            if (Head == -1)
            {
                Head = Free;
                Tail = Free;
            }
            Data[Tail].Next = Free;
            Tail = Free;
            Free = FreeCells[Free];
        }

        public int IndexOf(T value)
        {
            if (Head == -1)
            {
                return -1;
            }

            ListItem<T> current = Data[Head];
            int i = Head;

            while (i != -1)
            {
                if (Data[i].Value.Equals(value))
                {
                    return i;
                }
                i = current.Next;
                current = Data[current.Next];
            }

            return i;
        }

        public void Remove(T value)
        {
            int i = IndexOf(value);

            if (i == Head)
            {
                if (Head == Tail)
                {
                    Head = -1;
                    Tail = -1;
                }
                else
                {
                    Head = i + 1;
                }
            }
            else if (i == Tail)
            {
                if (Head == Tail)
                {
                    Head = -1;
                    Tail = -1;
                }
                else
                {
                    Tail = i - 1;
                    Data[i - 1].Next = -1;
                }
            }
            else
            {
                Data[i - 1].Next = Data[i + 1].Next;
            }

            FreeCells[i] = Free;
            Free = i;
        }

        public void RemoveAt(int index)
        {
            if (Head == -1)
            {
                throw new IndexOutOfRangeException();
            }

            int count = 0;
            ListItem<T> current = Data[Head];
            int i = Head;
            int prev = Head;

            while (count != index)
            {
                if (i == -1)
                {
                    throw new IndexOutOfRangeException();
                }

                prev = i;

                i = current.Next;
                current = Data[current.Next];
                count++;
            }

            Data[prev].Next = Data[i].Next;
            FreeCells[i] = Free;
            Free = i;
        }

        public void Clear()
        {
            Data = new ListItem<T>[Capacity];
            FreeCells = new int[Capacity];
            Head = -1;
            Tail = -1;
            Free = 0;
            FreeCells[FreeCells.Length - 1] = -1;
            for (int i = 0; i < FreeCells.Length - 1; i++)
            {
                FreeCells[i] = i + 1;
            }
        }

        public T this[int index]
        {
            get
            {
                int count = 0;
                ListItem<T> current = Data[Head];
                int i = Head;

                while (count != index)
                {
                    if (i == -1)
                    {
                        throw new IndexOutOfRangeException();
                    }
                    i = current.Next;
                    current = Data[current.Next];
                    count++;
                }

                return Data[i].Value;
            }
        }

        private struct ListItem<T>
        {
            public T Value;
            public int Next;
        }

        private ListItem<T>[] Data;
        private int[] FreeCells;
        private int Free;
        private int Head;
        private int Tail;
        private int Capacity;
    }

    class Program
    {
        public static void Main(string[] args)
        {
            List<int> list = new List<int>();

            list.Add(5);
            list.Add(7);
            list.Add(3);
            list.Add(1);
            list.Add(55);

            for (int i = 0; i < 5; i++)
            {
                Console.WriteLine(list[i]);
            }

            for (int i = 4; i >= 0; i--)
            {
                list.RemoveAt(i);
            }

            list.Add(3);
            Console.WriteLine("new {0}", list[0]);

            list.Remove(3);

            list.Add(5);
            Console.WriteLine("new2 {0}", list[0]);
        }
    }
}