ILinkedList interface definition
using System;
using System.Collections.Generic;namespace Sheva.Collections
{
public interface ILinkedList<T>
{
Boolean IsEmpty { get;}
void AddFirst(T item);
void AddLast(T item);
T First { get;}
T Last { get;}
T RemoveFirst();
T RemoveLast();
IEnumerable<T> Backwards { get;}
IEnumerable<T> Forwards { get;}
}
}
SingleLinkedList implementation
using System;
using System.Collections;
using System.Collections.Generic;namespace Sheva.Collections
{
public class SingleLinkedList<T> : ILinkedList<T>, ICollection<T>
{
private Node firstNode;
private Node lastNode;/// <summary>
/// Create an empty <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
public SingleLinkedList()
{
firstNode = lastNode = null;
}#region ILinkedList<T> Members/// <summary>
/// Check whether the specified <see cref="SingleLinkedList">SingleLinkedList</see> is empty.
/// </summary>
public Boolean IsEmpty
{
get { return firstNode == null; }
}/// <summary>
/// Gets the first node of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
public T First
{
get
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!");
return firstNode.Value;
}
}/// <summary>
/// Gets the last node of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
public T Last
{
get
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!");
return lastNode.Value;
}
}/// <summary>
/// Adds a new value at the start of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <param name="value">The value to add at the start of the <see cref="SingleLinkedList">SingleLinkedList</see>.</param>
public void AddFirst(T value)
{
Node newNode = new Node();
newNode.Value = value;if (IsEmpty)
{
firstNode = lastNode = newNode;
}
else
{
newNode.Next = firstNode;
firstNode = newNode;
}
}/// <summary>
/// Adds a new value at the end of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <param name="value">The value to add at the start of the <see cref="SingleLinkedList">SingleLinkedList</see>.</param>
public void AddLast(T value)
{
Node newNode = new Node();
newNode.Value = value;if (IsEmpty)
{
firstNode = lastNode = newNode;
}
else
{
lastNode.Next = newNode;
lastNode = newNode;
}
}/// <summary>
/// Removes the node at the start of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <returns>the value removed from the <see cref="SingleLinkedList">SingleLinkedList</see>.</returns>
public T RemoveFirst()
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!");
T removedValue
= firstNode.Value;
if (firstNode == lastNode) firstNode = lastNode = null;
firstNode = firstNode.Next;return removedValue;
}/// <summary>
/// Removes the node at the end of the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <returns>the value removed from the <see cref="SingleLinkedList">SingleLinkedList</see>.</returns>
public T RemoveLast()
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!"); T removedValue
= lastNode.Value;
if (firstNode == lastNode)
{
firstNode = lastNode = null;
}// Locate new last node.
Node currentNode = firstNode;
while (currentNode.Next != lastNode)
{
currentNode = currentNode.Next;
}// Remove last node.
lastNode = currentNode;
currentNode.Next = null;return removedValue;
} IEnumerable
<T> ILinkedList<T>.Backwards
{
get { throw new NotImplementedException("The list doesn't support this operation!"); }
}/// <summary>
/// Returns an enumerator that forwardly iterates through the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <returns>An <see cref="IEnumerable<T>">Enumerable</see> for the LinkedList. </returns>
public IEnumerable<T> Forwards
{
get
{
Node current = firstNode;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}
}#endregion#region ICollection<T> Membersvoid ICollection<T>.Add(T value)
{
this.AddLast(value);
}/// <summary>
/// Removes all nodes from the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
public void Clear()
{
firstNode = lastNode = null;
}/// <summary>
/// Determines whether a value is in the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <param name="value">The value to locate in the <see cref="SingleLinkedList">SingleLinkedList</see>.</param>
/// <returns>true if value is found in the <see cref="SingleLinkedList">SingleLinkedList</see>; otherwise, false. </returns>
public Boolean Contains(T value)
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!"); Node currentNode
= firstNode;
while (currentNode != null)
{
if (currentNode.Value.Equals(value)) return true; currentNode
= currentNode.Next;
}return false;
}/// <summary>
/// Copies the entire <see cref="SingleLinkedList">SingleLinkedList</see> to a compatible one-dimensional <see cref="System.Array">Array</see>, starting at the specified index of the target array.
/// </summary>
/// <param name="array">The one-dimensional <see cref="System.Array">Array</see> that is the destination of the elements copied from <see cref="SingleLinkedList">SingleLinkedList</see>. The array must have zero-based indexing.</param>
/// <param name="index">The zero-based index in array at which copying begins.</param>
public void CopyTo(T[] array, Int32 index)
{
if (array == null) throw new ArgumentNullException("array is a null reference ");
if (index < 0) throw new ArgumentOutOfRangeException("arrayIndex is less than zero.");
if (index >= array.Length) throw new ArgumentException("arrayIndex is equal to or greater than the length of array");
if (this.Count > (array.Length - index)) throw new ArgumentException("The number of elements in the source list is greater than the available space from index to the end of the destination array."); Int32 offset
= 0;
Node currentNode = firstNode;
while (currentNode != null)
{
array[index + offset] = currentNode.Value;
currentNode = currentNode.Next;
offset++;
}
}/// <summary>
/// Gets the number of nodes actually contained in the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
public Int32 Count
{
get
{
Int32 count = 0;
Node currentNode = firstNode;
while (currentNode != null)
{
currentNode = currentNode.Next;
count++;
}return count;
}
}/// <summary>
///
/// </summary>
public Boolean IsReadOnly
{
get { return false; }
}/// <summary>
/// Removes the first occurrence of value from the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <param name="value">The value to remove from the <see cref="SingleLinkedList">SingleLinkedList</see>.</param>
/// <returns>
/// true if the element containing value is successfully removed; otherwise, false.
/// This method also returns false if value was not found in the original <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </returns>
public Boolean Remove(T value)
{
if (IsEmpty) throw new InvalidOperationException("The list is empty!"); Node currentNode
= firstNode;
while (currentNode != null)
{
if (currentNode.Next.Value.Equals(value))
{
currentNode.Next = currentNode.Next.Next;
return true;
} currentNode
= currentNode.Next;
}return false;
}#endregion#region IEnumerable<T> Members/// <summary>
/// Returns an enumerator that forwardly iterates through the <see cref="SingleLinkedList">SingleLinkedList</see>.
/// </summary>
/// <returns>An <see cref="IEnumerator<T>>">Enumerator</see> for the <see cref="SingleLinkedList">SingleLinkedList</see>.</returns>
public IEnumerator<T> GetEnumerator()
{
return Forwards.GetEnumerator();
}#endregion#region IEnumerable Members IEnumerator IEnumerable.GetEnumerator()
{
return Forwards.GetEnumerator();
}#endregion
private class Node
{
public T Value;
public Node Next;
}
}
}
