-
-
Save Ivony/2217459 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment