Skip to content

Instantly share code, notes, and snippets.

@waynebaby
Forked from JeffreyZhao/gist:2216546
Created March 27, 2012 15:54
Show Gist options
  • Save waynebaby/2217401 to your computer and use it in GitHub Desktop.
Save waynebaby/2217401 to your computer and use it in GitHub Desktop.
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();
}
/// <summary>
/// 没有检查 乱写的 By Wayne
/// </summary>
/// <typeparam name="T"></typeparam>
class MyList<T> : IMyList<T> where T : class
{
LinkedList<T> _leftLinkedList = new LinkedList<T>();
LinkedList<T> _rightLinkedList = new LinkedList<T>();
Dictionary<T, List<LinkedListNode<T>>> _index = new Dictionary<T, List<LinkedListNode<T>>>();
public MyList()
{
}
public void AddFirst(T item)
{
if (item == null)
{
throw new ArgumentNullException();
}
var ln = _leftLinkedList.AddLast(item);
List<LinkedListNode<T>> lst;
if (!_index.TryGetValue(item, out lst))
{
lst = new List<LinkedListNode<T>>();
_index.Add(item,lst);
}
lst.Add(ln);
}
public void AddLast(T item)
{
if (item == null)
{
throw new ArgumentNullException();
}
var ln = _rightLinkedList.AddLast(item);
List<LinkedListNode<T>> lst;
if (!_index.TryGetValue(item, out lst))
{
lst = new List<LinkedListNode<T>>();
_index.Add(item, lst);
}
lst.Add(ln);
}
public void Remove(T item)
{
if (item == null)
{
throw new ArgumentNullException();
}
List<LinkedListNode<T>> lst;
if (_index.TryGetValue(item, out lst))
{
if (lst.Count>0)
{
var lastp = lst.Count - 1;
var ln = lst[lastp];
ln.List.Remove(ln);
lst.RemoveAt(lastp);
}
}
}
public void Reverse()
{
var mid = _leftLinkedList;
_leftLinkedList = _rightLinkedList;
_rightLinkedList = mid;
}
public IEnumerator<T> GetEnumerator()
{
return GetEnumerable();
}
private IEnumerator<T> GetEnumerable()
{
var current = _leftLinkedList.Last;
while (current != null)
{
yield return current.Value;
current = current.Previous;
}
current = _rightLinkedList.First;
while (current != null)
{
yield return current.Value;
current = current.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