15,171,053 members
Articles / General Programming / Algorithms
Article
Posted 6 May 2010

#### Stats

34.5K views
12 bookmarked

Rate me:
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();
}
}```

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>
/// 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>

{
#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>

{
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 !

## Share

No Biography provided

 First Prev Next
 Regarding RemoveAt method prabhath Eranda29-May-17 15:24 prabhath Eranda 29-May-17 15:24
 Regarding Indexer in your code bahunani7-Dec-16 7:46 bahunani 7-Dec-16 7:46
 My vote of 5 Hamit Reyhani17-Feb-11 4:06 Hamit Reyhani 17-Feb-11 4:06
 Thanks Mercurial1239-Aug-10 3:36 Mercurial123 9-Aug-10 3:36
 Re: Thanks TobiasP30-Nov-10 0:34 TobiasP 30-Nov-10 0:34
 My vote of 1 SledgeHammer016-May-10 19:30 SledgeHammer01 6-May-10 19:30
 I gave you a 1 because: a) poor formatting b) absolutely nothing new here... just re-inventing the wheel c) not a very good implementation either
 Re: My vote of 1 Sarang Date7-May-10 3:35 Sarang Date 7-May-10 3:35
 Last Visit: 31-Dec-99 19:00     Last Update: 20-Jan-22 2:23 Refresh 1