gistfile1.cs

namespace Test
{


  public class Program
  {
    public static void Main()
    {

      var list = new MyClass<string>();

      while ( true )
      {

        var cmd = Console.ReadLine();
        if ( cmd.StartsWith( "<" ) )
          list.AddFirst( cmd.Substring( 1 ) );

        else if ( cmd.StartsWith( "-" ) )
          list.Remove( cmd.Substring( 1 ) );

        else if ( cmd == "!" )
          list.Reverse();

        else
          list.AddLast( cmd );


        Console.WriteLine( new string( '-', 50 ) );

        foreach ( var item in list )
          Console.WriteLine( item );


        Console.WriteLine( new string( '-', 50 ) );

      }
    }
  }

  // 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 MyClass<T> : IMyList<T>
  {

    public LinkedList<T> _list = new LinkedList<T>();
    public Dictionary<T, ICollection<LinkedListNode<T>>> _dictionary = new Dictionary<T, ICollection<LinkedListNode<T>>>();





    public void AddFirst( T item )
    {
      LinkedListNode<T> node;
      if ( _isReverse )
        node = _list.AddLast( item );
      else
        node = _list.AddFirst( item );

      Index( item, node );
    }

    private void Index( T item, LinkedListNode<T> node )
    {
      ICollection<LinkedListNode<T>> list;

      if ( !_dictionary.TryGetValue( item, out list ) )
      {
        list = new LinkedList<LinkedListNode<T>>();
        _dictionary.Add( item, list );
      }

      list.Add( node );
    }

    public void AddLast( T item )
    {
      LinkedListNode<T> node;
      if ( !_isReverse )
        node = _list.AddLast( item );
      else
        node = _list.AddFirst( item );

      Index( item, node );
    }

    public void Remove( T item )
    {
      ICollection<LinkedListNode<T>> list;
      if ( !_dictionary.TryGetValue( item, out list ) )
        return;

      var node = list.FirstOrDefault();
      if ( node == null )
        return;

      node.List.Remove( node );
    }

    private bool _isReverse = false;

    public void Reverse()
    {
      _isReverse = !_isReverse;
    }

    public IEnumerator<T> GetEnumerator()
    {
      LinkedListNode<T> node;
      if ( _isReverse )
        node = _list.Last;
      else
        node = _list.First;

      while ( true )
      {

        if ( node == null )
          yield break;

        yield return node.Value;

        if ( _isReverse )
          node = node.Previous;
        else
          node = node.Next;
      }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }
  }
}