Click here to Skip to main content
15,867,686 members
Articles / General Programming / Algorithms

Generic SinglyLinkedList in C# with Basic and Advanced Custom Operations

Rate me:
Please Sign up or sign in to vote.
4.33/5 (6 votes)
7 May 2010CPOL6 min read 39.1K   534   12   7
The following article describes C# implementation of various basic and advanced operations including some of the programming problems involving singly linked list

Introduction

This article covers the custom implementation of Generic Singly LinkedList in C# and includes basic and advanced operations on the list with optimized algorithm.

Background

As a .NET programmer, we always have the luxury of using in-built out of the box FCL classes for data structures and there are many of them e.g., LinkedList<T>, Queue<T>, SortedDictionary<T Key, T Value>, Stack<T>, etc. but in many of the programming interviews, generally it is expected from us to come up initially with a certain data structure and all of its basic operations, then advanced operations and later to optimize them for time and space complexity. Here I have tried to implement a generic LinkedList with basic as well as advanced operations which reveal the underlying algorithm behind this very popular and in-demand data structure. Basic operations include adding to the front and back of the list, removing from the front and back of the list, adding and removing at a specific index, searching and updating an element, displaying and clearing the list contents, etc., and advanced operations include finding the mid element, determining whether the list contains a loop/cycle, etc.

Using the Code

I have written three classes for this demonstration:

  1. Class TestLinkedList - Test class for my singly linked list implementation. Code is included in the ZIP (It contains the Main method to test all of the operations with the list in a simple Console based UI. Nothing unusual !)
  2. Class ListNode<T> - Generic list node class. Note that by implementing a generic node class, I have avoided the overhead of boxing/unboxing and increased the utility and re-use.
    Our class ListNode<T> is a generic class which means it can contain nodes for any data type. It has two fields, one is 'item' of type T which is a placeholder for the data to be stored in the node, and other is 'next' of type ListNode<T> which is simply a pointer to the next node in the list. Then we have a constructor to initialize the node with data which internally calls another constructor which initializes the node with data and pointer to the next node. If the list is empty, the node will be initialized as first node (commonly called as just 'first' or 'head') with data and pointer to the next node equals null (marking the end of the list). I have overridden the ToString() method here for ease of understanding and debugging as it is the data stored at the node which is what we are concerned with. My overridden implementation will simply return the node value in a string format. See the code below:
C#
/// <summary>
/// Generic ListNode class - avoiding boxing unboxing here by using generic implementation
/// </summary>
/// <typeparam name="T"></typeparam>

public class ListNode<T>
{
	private ListNode<T> next;
	private T item;
	/// <summary>
	/// Property to hold pointer to next ListNode - Self containing object
	/// </summary>

	public ListNode<T> Next
	{
		get { return next; }
		set { next = value; }
	}

	/// <summary>
	/// Property to hold value into the Node
	/// </summary>

	public T Item
	{
		get { return item; }
		set { item = value; }
	}

	/// <summary>
	/// Constructor with item init
	/// </summary>
	/// <param name="item"></param>

	public ListNode(T item)
	: this(item,null)
	{
	}

	/// <summary>
	/// Constructor with item and the next node specified
	/// </summary>
	/// <param name="item"></param>
	/// <param name="next"></param>

	public ListNode(T item, ListNode<T> next)
	{
		this.item = item;
		this.next = next;
	}

	/// <summary>
	/// Overriding ToString to return a string value for the item in the node
	/// </summary>
	/// <returns></returns>

	public override string ToString()
	{
		if (item == null)
			return string.Empty;
		return item.ToString();
	}
}

Class SinglyLinkedList<T>:ICollection<T>

First we create a generic SinglyLinkedList<T> class implementing ICollection interface so that we can iterate through the list items, and provide a framework to implement supporting operations such as remove, add, Contains, GetEnumerator, Sort, etc.

Let's delve deeper into this class. We have a field 'strListName' of type String to specify the name of the list. For testing purposes, I have hard-coded it to 'MyList'. Bad practice, isn't it? Anyway, there are 2 fields 'firstNode' and 'lastNode' of type ListNode<T> to point to the starting and ending nodes in the list for obvious reasons (sequential traversals for various operations) and a variable 'count' which keeps track of the length of the list, in short, the number of elements in the list. for every add operation, count increments by 1 and for every remove operation, it decrements by 1. There is a boolean Property 'IsEmpty' which returns true if the list contains no elements, and false otherwise. I have also added an indexer to LinkedList class to fetch an item for the specified index. As this is a singly linked list, we do not have a previous Node pointer. We have two constructors to initialize our list with either the provided name or the default name and first and last nodes set to null (initializing an empty list). See the code below:

C#
/// <summary>
/// SinglyLinkedList class for generic implementation of LinkedList. 
/// Again, avoiding boxing unboxing here and using ICollection interface members. 
/// Believe this can be useful when applying other 
/// operations such as sorting, searching etc. 
/// </summary>
/// <typeparam name="T"></typeparam>

public class SinglyLinkedList<T>:ICollection<T>
{
	#region private variables
	private string strListName;
	private ListNode<T> firstNode;
	private ListNode<T> lastNode;
	private int count;
	#endregion

	/// <summary>
	/// Property to hold first node in the list
	/// </summary>

	public ListNode<T> FirstNode
	{
		get { return firstNode; }
	}

	/// <summary>
	/// Property to hold last node in the list
	/// </summary>

	public ListNode<T> LastNode
	{
		get { return lastNode; }
	}

	/// <summary>
	/// Indexer to iterate through the list and fetch the item
	/// </summary>
	/// <param name="index"></param>
	/// <returns></returns>

	public T this[int index]
	{
		get 
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException();
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index; i++)
			{
				if (currentNode.Next == null)
					throw new ArgumentOutOfRangeException();
				currentNode = currentNode.Next;
			}
		return currentNode.Item;
		}
	}

	/// <summary>
	/// Property to hold count of items in the list
	/// </summary>

	public int Count
	{
		get { return count; }
	}

	/// <summary>
	/// Property to determine if the list is empty or contains any item
	/// </summary>

	public bool IsEmpty
	{
		get 
		{
			lock (this)
			{
				return firstNode == null;
			}
		}
	}

	/// <summary>
	/// Constructor initializing list with a provided list name
	/// </summary>
	/// <param name="strListName"></param>

	public SinglyLinkedList(string strListName)
	{
		this.strListName = strListName;
		count = 0;
		firstNode = lastNode = null;
	}

	/// <summary>
	/// default constructor initializing list with a default name 'MyList'
	/// </summary>

	public SinglyLinkedList() : this("MyList") { }
	/// <summary>
	/// Operation ToString overridden to get the contents from the list
	/// </summary>
	/// <returns></returns>

	public override string ToString()
	{
		if (IsEmpty)
			return string.Empty;
		StringBuilder returnString = new StringBuilder();
		foreach (T item in this)
		{
			if (returnString.Length > 0)
				returnString.Append("->");
			returnString.Append(item);
		}
		return returnString.ToString();
	}

Following this, let's take a look at the basic operations which can be performed on a singly linkedlist such as adding an item to front, adding an item to back, removing an item from front, removing an item from back, searching and updating an item, getting the length of list, inserting at a specific index, removing from a specific, index etc. Basically traversing through the list sequentially involves setting the pointer to the first node and looping through the list till the pointer refers to null node (marking as end of the list). Adding a node to the list involves creating a node with a value, and inserting it either at the front or the back of the list, or at a specified index, and then increment the counter after adjusting the 'next' pointers accordingly to and from the newly added node (if not the first node of the list). Removing is simpler. Destroy the node to be removed by setting the previous node pointer to the next node pointer and decrement the counter by 1. If the node to be removed is the first node, reset the pointer to the next element and in case of last node, traverse through the list and reset the last node to the previous node and next pointer to null. Clearing a list is as simple as it can get. Just set starting and ending nodes to null and reset the counter to 0. Find and Update operations involve traversing through the list, matching the input item with the item contained in the currently identified node and perform the operation.

The following code sample illustrates the implementation of these operations:

C#
/// <summary>
/// Operation inserts item at the front of the list
/// </summary>
/// <param name="item"></param>

public void InsertAtFront(T item)
{
	lock (this)
	{
		if (IsEmpty)
			firstNode = lastNode = new ListNode<T>(item);
		else
			firstNode = new ListNode<T>(item, firstNode);
		count++;
	}
}

/// <summary>
/// Operation inserts item at the back of the list
/// </summary>
/// <param name="item"></param>

public void InsertAtBack(T item)
{
	lock (this)
	{
		if (IsEmpty)
			firstNode = lastNode = new ListNode<T>(item);
		else
			lastNode = lastNode.Next = new ListNode<T>(item);
		count++;
	}
}

/// <summary>
/// Operation removes item from the front of the list
/// </summary>
/// <returns></returns>

public object RemoveFromFront()
{
	lock (this)
	{
		if (IsEmpty)
			throw new ApplicationException("list is empty");
		object removedData = firstNode.Item;
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.Next;
		count--;
		return removedData;
	}
}

/// <summary>
/// Operation removes item from the back of the list
/// </summary>
/// <returns></returns>

public object RemoveFromBack()
{
	lock (this)
	{
		if (IsEmpty)
			throw new ApplicationException("list is empty");
		object removedData = lastNode.Item;
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else
		{
			ListNode<T> currentNode = firstNode;
			while (currentNode.Next != lastNode)
				currentNode = currentNode.Next;
			lastNode = currentNode;
			currentNode.Next = null;
		}
		count--;
		return removedData;
	}
}

/// <summary>
/// Operation inserts item at the specified index in the list
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>

public void InsertAt(int index, T item)
{
	lock (this)
	{
		if (index > count || index < 0)
			throw new ArgumentOutOfRangeException();
		if (index == 0)
			InsertAtFront(item);
		else if (index == (count - 1))
			InsertAtBack(item);
		else
		{
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index - 1; i++)
			{
				currentNode = currentNode.Next;
			}
			ListNode<T> newNode = new ListNode<T>(item, currentNode.Next);
			currentNode.Next = newNode;
			count++;
		}
	}
}

/// <summary>
/// Operation removes item from the specified index in the list
/// </summary>
/// <param name="index"></param>
/// <returns></returns>

public object RemoveAt(int index)
{
	lock (this)
	{
		if (index > count || index < 0)
			throw new ArgumentOutOfRangeException();
		object removedData;
		if (index == 0)
			removedData = RemoveFromFront();
		else if (index == (count - 1))
			removedData = RemoveFromBack();
		else
		{
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index; i++)
			{
				currentNode = currentNode.Next;
			}
			removedData = currentNode.Item;
			currentNode.Next = currentNode.Next.Next;
			count--;
		}
		return removedData;
	}
}

/// <summary>
/// Removes the input item if exists and returns true else false
/// </summary>
/// <param name="item"></param>
/// <returns></returns>

public bool Remove(T item)
{
	if (firstNode.Item.ToString().Equals(item.ToString()))
	{
		RemoveFromFront();
		return true;
	}
	else if (lastNode.Item.ToString().Equals(item.ToString()))
	{
		RemoveFromBack();
		return true;
	}
	else
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode.Next != null)
		{
			if (currentNode.Next.Item.ToString().Equals(item.ToString()))
			{
				currentNode.Next = currentNode.Next.Next;
				count--;
				if (currentNode.Next == null)
					lastNode = currentNode;
				return true;
			}
			currentNode = currentNode.Next;
		}
	}
	return false;
}


/// <summary>
/// Operation updates an item provided as an input with a new item 
/// (also provided as an input)
/// </summary>
/// <param name="oldItem"></param>
/// <param name="newItem"></param>
/// <returns></returns>

public bool Update(T oldItem, T newItem)
{
	lock (this)
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode != null)
		{
			if (currentNode.ToString().Equals(oldItem.ToString()))
			{
				currentNode.Item = newItem;
				return true;
			}
			currentNode = currentNode.Next;
		}
		return false;
	}
}

/// <summary>
/// Returns true if list contains the input item else false
/// </summary>
/// <param name="item"></param>
/// <returns></returns>

public bool Contains(T item)
{
	lock (this)
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode != null)
		{
			if (currentNode.Item.ToString().Equals(item.ToString()))
			{
				return true;
			}
			currentNode = currentNode.Next;
		}
		return false;
	}
}

/// <summary>
/// Operation resets the list and clears all its contents
/// </summary>

public void Clear()
{
	firstNode = lastNode = null;
	count = 0;
}

Now the most significant operations on a linkedlist where your code can really be a differentiator between a developer and a good developer who can optimize the code by absolutely squeezing the algorithm. Here we go, following code illustrates how to reverse a linkedlist, how to find the mid element of the list and how to determine if the list contains a cycle and note that we need to implement these operations keeping in mind the time and space efficiency (remember Big O notation??).

Reversing a list involves simple swapping algorithm where we have set the lastnode to firstnode initially. We also have an additional ListNode<T> element which effectively acts as a previousNode pointer (to be used in swap) and a currentNode pointer which moves through the list one by one swapping with the previousNode. At last, we are setting the firstNode to currentNode which completes the reversal operation in O(n).

Finding a cycle can be tricky because once you have a cycle in your list and you try to determine it by brute force, traversing through the list till the end, it will never work because the loop will go infinitely. The key here is to have a slow pointer and a fast pointer. Fast pointer moves at twice the speed of slow pointer and if at any stage, fast pointer overlaps with the slow pointer, it indicates a cycle.

Finding a midpoint of the list uses the same principle. Fast pointer reaches the end of the list in half the time of the slow pointer and hence the moment it reaches the end, the slower pointer will point to the mid of the list. If the list has a cycle, then it returns null because in a cycle, there can be no midpoint.

C#
/// <summary>
/// Operation to reverse the contents of the linked list 
/// by resetting the pointers and swapping the contents
/// </summary>

public void Reverse()
{
	if (firstNode == null || firstNode.Next == null)
		return;
	lastNode = firstNode;
	ListNode<T> prevNode = null;
	ListNode<T> currentNode = firstNode;
	ListNode<T> nextNode = firstNode.Next;

	while (currentNode != null)
	{
		currentNode.Next = prevNode;
		if (nextNode == null)
			break;
		prevNode = currentNode;
		currentNode = nextNode;
		nextNode = nextNode.Next;
	}
	firstNode = currentNode;
}

/// <summary>
/// Operation to find if the linked list contains a circular loop
/// </summary>
/// <returns></returns>

public bool HasCycle()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> iteratorNode = firstNode;
	for (; iteratorNode != null && iteratorNode.Next != null; 
		iteratorNode = iteratorNode.Next )
	{
		if (currentNode.Next == null || 
			currentNode.Next.Next == null) return false;
		if (currentNode.Next == iteratorNode || 
			currentNode.Next.Next == iteratorNode) return true;
		currentNode = currentNode.Next.Next;
	}
	return false;
}

/// <summary>
/// Operation to find the midpoint of a list 
/// </summary>
/// <returns></returns>

public ListNode<T> GetMiddleItem()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> iteratorNode = firstNode;
	for (; iteratorNode != null && iteratorNode.Next != null; 
		iteratorNode = iteratorNode.Next)
	{
		if (currentNode.Next == null || 
			currentNode.Next.Next == null) return iteratorNode;
		if (currentNode.Next == iteratorNode || 
			currentNode.Next.Next == iteratorNode) return null;
		currentNode = currentNode.Next.Next;
	}
	return firstNode;
}

Interface IEnumerable<T> Members

C#
#region IEnumerable<T> Members
/// <summary>
/// Custom GetEnumerator method to traverse through the list and 
/// yield the current value
/// </summary>
/// <returns></returns>

 public IEnumerator<T> GetEnumerator()
 {
	ListNode<T> currentNode = firstNode;
	while (currentNode != null)
	{
		yield return currentNode.Item;
		currentNode = currentNode.Next;
	}
}

#endregion

#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
	return GetEnumerator();
}

#endregion

And just in case you wonder how to programmatically create a cycle in our linkedlist, here is the trick!

C#
/// <summary>
/// Operation creates a circular loop in the linked list for testing purpose. 
/// Once this loop is created, other operations would probably fail.
/// </summary>

public void CreateCycleInListToTest()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> midNode = GetMiddleItem();
	lastNode.Next = midNode;
}

Thank you for reading. I hope it was useful and a value addition to your existing knowledge on data structure operations and C# programming !

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Technical Lead Microsoft India R&D Pvt. Ltd. Hyderabad
India India
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionRegarding RemoveAt method Pin
prabhath Eranda29-May-17 14:24
prabhath Eranda29-May-17 14:24 
QuestionRegarding Indexer in your code Pin
bahunani7-Dec-16 6:46
bahunani7-Dec-16 6:46 
GeneralMy vote of 5 Pin
Hamit Reyhani17-Feb-11 3:06
Hamit Reyhani17-Feb-11 3:06 
GeneralThanks Pin
Mercurial1239-Aug-10 2:36
Mercurial1239-Aug-10 2:36 
thanks man just what I weeded to learn.
I was really confused how the hell do you make a linkedlist! LOL!


the explanations is crystal clear to me except.. I really can't get this line

lastNode = lastNode.Next = new ListNode(item);

how the hell does the first node get change with this code T_T; please enlighten me
GeneralRe: Thanks Pin
TobiasP29-Nov-10 23:34
TobiasP29-Nov-10 23:34 
GeneralMy vote of 1 Pin
SledgeHammer016-May-10 18:30
SledgeHammer016-May-10 18:30 
GeneralRe: My vote of 1 Pin
Sarang Date7-May-10 2:35
Sarang Date7-May-10 2:35 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.