Skip to content

Instantly share code, notes, and snippets.

@onlytiancai
Created March 28, 2012 00:06
Show Gist options
  • Save onlytiancai/2221671 to your computer and use it in GitHub Desktop.
Save onlytiancai/2221671 to your computer and use it in GitHub Desktop.
老赵微博的题目撒
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();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment