|
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];
}
}
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.