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:
- 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 !)
- 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:
public class ListNode<T>
{
private ListNode<T> next;
private T item;
public ListNode<T> Next
{
get { return next; }
set { next = value; }
}
public T Item
{
get { return item; }
set { item = value; }
}
public ListNode(T item)
: this(item,null)
{
}
public ListNode(T item, ListNode<T> next)
{
this.item = item;
this.next = next;
}
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:
public class SinglyLinkedList<T>:ICollection<T>
{
#region private variables
private string strListName;
private ListNode<T> firstNode;
private ListNode<T> lastNode;
private int count;
#endregion
public ListNode<T> FirstNode
{
get { return firstNode; }
}
public ListNode<T> LastNode
{
get { return lastNode; }
}
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;
}
}
public int Count
{
get { return count; }
}
public bool IsEmpty
{
get
{
lock (this)
{
return firstNode == null;
}
}
}
public SinglyLinkedList(string strListName)
{
this.strListName = strListName;
count = 0;
firstNode = lastNode = null;
}
public SinglyLinkedList() : this("MyList") { }
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:
public void InsertAtFront(T item)
{
lock (this)
{
if (IsEmpty)
firstNode = lastNode = new ListNode<T>(item);
else
firstNode = new ListNode<T>(item, firstNode);
count++;
}
}
public void InsertAtBack(T item)
{
lock (this)
{
if (IsEmpty)
firstNode = lastNode = new ListNode<T>(item);
else
lastNode = lastNode.Next = new ListNode<T>(item);
count++;
}
}
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;
}
}
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;
}
}
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++;
}
}
}
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;
}
}
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;
}
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;
}
}
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;
}
}
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.
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;
}
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;
}
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
#region IEnumerable<T> Members
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!
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 !
