Data Structures : Part 1 - Singly Linked Lists

using System;

namespace System.Collections.Implementations
{
	public class SinglyLinkedList : IEnumerable, IEnumerator
	{
		#region Private Variables

		// Our next item in the list
		private SinglyLinkedList _Next = null;
		// The value of the current item
		private object           _Item = null;

		#endregion

		#region Constructors

		/// <summary>
		/// Creates a new SinglyLinkedList object
		/// </summary>
		public SinglyLinkedList() 
		{ 
			// Nothing is done here.  This is just included so 
			// people can create new linked lists.
		}


		/// <summary>
		/// Creates a new SinglyLinkedList node for the Item
		/// </summary>
		/// <param name="Item"></param>
		protected SinglyLinkedList(object Item)
		{
			// Wow.  Not much here either.  Just setting the item
			_Item = Item;
		}


		#endregion

		#region Working Routines

		/// <summary>
		/// Gets the Indexth item in the list
		/// </summary>
		/// <param name="Index">Index of the item to get</param>
		/// <returns>Item sought</returns>
		public object Get(int Index)
		{
			return FindNode(Index)._Item;
		}


		/// <summary>
		/// Adds an item to the end of the list
		/// </summary>
		/// <param name="Item">Item to be added</param>
		/// <returns>The new length of the list</returns>
		public void Add(object Item)
		{
			Last._Next = new SinglyLinkedList(Item);
		}


		/// <summary>
		/// Inserts an item at the specified index in the list
		/// </summary>
		/// <param name="Item">The item to add</param>
		/// <param name="Index">The index to add the item at</param>
		public void Insert(object Item, int Index)
		{
			// Nothing too tricky here.

			SinglyLinkedList PreviousNode = FindNode(Index);

			SinglyLinkedList NextItem = new SinglyLinkedList(Item);
			NextItem._Next = PreviousNode._Next;
			PreviousNode._Next = NextItem;
		}


		/// <summary>
		/// Replaces the Item at the Indexth place in the list
		/// </summary>
		/// <param name="Index">Index of the item to replace</param>
		/// <param name="Item">Item to swap in</param>
		public void Replace(int Index, object Item)
		{
			FindNode(Index)._Item = Item;
		}


		/// <summary>
		/// Removes the item at the specified index
		/// </summary>
		/// <param name="Index">Index of the item to remove</param>
		public void Remove(int Index)
		{
			// Nothing too tricky here.

			SinglyLinkedList PreviousNode = FindNode(Index);

			if (PreviousNode._Next == null)
				throw new ArgumentOutOfRangeException("Index", Index, "Index greater than the number of items");
			else
				PreviousNode._Next = PreviousNode._Next._Next;
		}


		/// <summary>
		/// Finds a node given the index
		/// </summary>
		/// <param name="Index">Index of the node to find</param>
		/// <returns>Node found</returns>
		private SinglyLinkedList FindNode(int Index)
		{
			if (Index < 0)
				throw new ArgumentOutOfRangeException("Index", Index, "Index must be greater than or equal to 0");
			
			SinglyLinkedList Target;
			for (Target = this; Index > 0; Index--)
				if (Target._Next != null)
					Target = Target._Next;
				else
					throw new ArgumentOutOfRangeException("Index", Index, "Index greater than the number of items");

			return Target;
		}


		/// <summary>
		/// Combines two linked lists together
		/// </summary>
		/// <param name="OtherList">Other linked list</param>
		public void Append(SinglyLinkedList OtherList)
		{
			// Glue.  Plain and simple glue.
			Last._Next = OtherList._Next;
		}
		

		#endregion

		#region Properties

		/// <summary>
		/// Public Accessor for the list items
		/// </summary>
		public object this[int Index]
		{
			get
			{
				return FindNode(Index)._Item;
			}
			set
			{
				Insert(value, Index);
			}
		}


		/// <summary>
		/// Length of the entire list
		/// </summary>
		public int Length
		{
			get
			{
				int Counter = 0;
				for (SinglyLinkedList Target = this; Target._Next != null; Target = Target._Next) 
				{ 
					Counter++;
				}

				return Counter;
			}
		}

		
		/// <summary>
		/// Gets the last item in the list
		/// </summary>
		protected SinglyLinkedList Last
		{
			get
			{
				SinglyLinkedList Target;
				
				for (Target = this; Target._Next != null; Target = Target._Next) { }

				return Target;
			}
		}
		
		
		#endregion

		#region Enumeration Members
		
		/// <summary>
		/// Initializes enumeration
		/// </summary>
		/// <returns>Resets the enumerator and returns itself</returns>
		public IEnumerator GetEnumerator()
		{
			Reset();
			return this;
		}

		
		/// <summary>
		/// This is the currently enumerated item
		/// </summary>
		private SinglyLinkedList _EnumerationTarget = null;
	
		/// <summary>
		/// Resets enumeration to point to the first element
		/// </summary>
		public void Reset()
		{
			_EnumerationTarget = this;
		}


		/// <summary>
		/// Gets the currently enumerated object
		/// </summary>
		public object Current
		{
			get
			{
				return _EnumerationTarget._Item;
			}
		}

		
		/// <summary>
		/// Advances to the next object
		/// </summary>
		/// <returns>Flag determining whether there are no further objects</returns>
		public bool MoveNext()
		{
			_EnumerationTarget = _EnumerationTarget._Next;
			return _EnumerationTarget != null;
		}


		#endregion

		public class Stack : SinglyLinkedList
		{
			public void Push(object Item)
			{
				Add(Item);
			}

			public object Pop()
			{
				if (_Next == null)
					throw new Exception("Stack is Empty");

				object Item = Last;
				Remove(Length - 1);
				return Item;
			}

			public object Peek()
			{
				if (_Next == null)
					throw new Exception("Stack is Empty");

				return Last._Item;
			}
		}



		public class Queue : SinglyLinkedList
		{
			public void Enqueue(object Item)
			{
				Add(Item);
			}

			public object Dequeue()
			{
				if (_Next == null)
					throw new Exception("Queue is Empty");

				object Item = this[0];
				Remove(0);
				return Item;
			}

			public object Peek()
			{
				if (_Next == null)
					throw new Exception("Queue is Empty");

				return this[0];
			}
		}
	}
}