laozhaoq.cs

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace LaozhaoQ
    {
        // Please write an sequence list implements the interface with the required
        // time complexity described in the comments. The users can add the same
        // element as many times as they want, but it doesn't support the null item.
        // You can use any types in .NET BCL but cannot use any 3rd party libraries.
        // PS: You don't need to consider the multi-threaded environment.
        interface IMyList<T> : IEnumerable<T>
        {
            // O(1)
            // Add an item at the beginning of the list.
            void AddFirst(T item);

            // O(1)
            // Add an item at the end of the list.
            void AddLast(T item);

            // O(1)
            // Remove the item from the list. If the list contains multiple
            // copies/references of the item, remove one of them.
            void Remove(T item);

            // O(1)
            // Reverse the list.
            void Reverse();
        }
        public class MyList<T> : IMyList<T>
        {
            LinkedList<T> _list = new LinkedList<T>();
            HashSet<T> _removed = new HashSet<T>();
            bool _reversed = false;
            public void AddFirst(T item)
            {
                _list.AddFirst(item);
            }

            public void AddLast(T item)
            {
                _list.AddLast(item);
            }

            public void Remove(T item)
            {
                _removed.Add(item);
            }

            public void Reverse()
            {
                _reversed = true;
            }

            public IEnumerator<T> GetEnumerator()
            {
                LinkedListNode<T> node;
                if (!_reversed)
                {
                    node = _list.First;
                    while (node != null)
                    {
                        if (_removed.Contains(node.Value)) {
                            node = node.Next;
                            continue; 
                        }
                        yield return node.Value;
                        node = node.Next;
                    }
                    yield break;
                }
                node = _list.Last;
                while (node != null)
                {
                    if (_removed.Contains(node.Value)) 
                    {
                        node = node.Previous;
                        continue;
                    } 
                    yield return node.Value;
                    node = node.Previous;
                }
            }

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return _list.GetEnumerator();//不知道这是干嘛的
            }
        }
        class Program
        {
            static void Print(MyList<int> list) {
                foreach (int value in list)
                {
                    Console.WriteLine(value);
                }
                Console.WriteLine("---------------");
            }
            static void Main(string[] args)
            {
                MyList<int> list = new MyList<int>();
                list.AddFirst(1);
                list.AddFirst(2);
                Print(list);//2,1
                list.AddLast(3);
                Print(list);//2,1,3
                list.Reverse();
                Print(list);//3,1,2
                list.Remove(1);
                Print(list);//3,2
                Console.ReadKey();
            }
        }
    }