Click here to Skip to main content
11,633,454 members (78,264 online)
Click here to Skip to main content
Add your own
alternative version

Data Structures : Part 1 - Singly Linked Lists

, 3 Mar 2004 82K 2.1K 34
An easy implementation of a singly linked list
singlylinkedlist_class.zip
DataStructures
bin
Debug
obj
Debug
temp
TempPE
singlylinkedlist_project.zip
DataStructures.csproj.user
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

agoat
United States United States
No Biography provided

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150728.1 | Last Updated 4 Mar 2004
Article Copyright 2004 by agoat
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid