Generic Singly Linked List Implementation in C#
The linked list is a basic data structure that can be implemented in virtually any language. The concept is simple. A linked list consists of a collection of nodes that each point to a different node. In a singly linked list, each node points to only one other node, and that node is the next node that is in the list. Generally, a singly linked list stores a reference to the first node in the linked list, and the last object in the linked list.
In this tutorial, we are going to implement a singly linked list in C#. I hope to build upon the foundation of the linked list, and implement more data structures along the way, for example, stacks and queues. That being said, this is not going to be just a small project with two classes, but we will be defining interfaces and hopefully creating some base classes. Now that we know what to expect in the coming posts, let us begin.
By the end of this tutorial, we will aim to have a bunch of classes which look like this.
I have also laid out the structure of the files like so (just for reference).
So lets begin with the interface ILinkedList<T>. This will be a generic interface which will provide the methods and properties that all linked lists that we implement should have. In the interest of space and the length of this blog post, I have left out the XML comments, but will comment on the methods as we implement them.
using System.Collections.Generic;
namespace DataStructures.LinkedList {
public interface ILinkedList<T> : IEnumerable<T> {
void PushFront(T item);
void PushBack(T item);
void InsertBefore(ILinkedListNode<T> node, ILinkedListNode<T> newNode);
void InsertBefore(ILinkedListNode<T> node, T newObject);
void InsertBefore(T value, ILinkedListNode<T> newNode);
void InsertBefore(T value, T newObject);
void InsertAfter(ILinkedListNode<T> node, ILinkedListNode<T> newNode);
void InsertAfter(ILinkedListNode<T> node, T newObject);
void InsertAfter(T value, ILinkedListNode<T> newNode);
void InsertAfter(T value, T newObject);
T PopFront();
T PopBack();
void Clear();
bool IsEmpty { get; }
int Count { get; }
ILinkedListNode<T> Front { get; }
ILinkedListNode<T> Back { get; }
void Sort(IComparer<T> comparer);
}
}
The other interfaces that we are going to be using with this tutorial is ILinkedListNode
namespace DataStructures {
public interface INode<T> {
T Value { get; set; }
}
}
namespace DataStructures.LinkedList {
public interface ILinkedListNode<T> : INode<T> {
}
}
Of course, now that we have defined our interfaces, we must implement them. As I mentioned earlier, I am planning to implement different data structures, hence we will be implementing a base class for the our list. I have called my base class LinkedListBase
using System.Collections.Generic;
using System.Collections;
namespace DataStructures.LinkedList.Impl {
public abstract class LinkedListBase<T> : ILinkedList<T> {
#region ILinkedList<T> Members
public abstract void PushFront(T item);
public abstract void PushBack(T item);
public abstract void InsertBefore(ILinkedListNode<T> node, ILinkedListNode<T> newNode);
public abstract void InsertBefore(ILinkedListNode<T> node, T newObject);
public abstract void InsertBefore(T value, ILinkedListNode<T> newNode);
public abstract void InsertBefore(T value, T newObject);
public abstract void InsertAfter(ILinkedListNode<T> node, ILinkedListNode<T> newNode);
public abstract void InsertAfter(ILinkedListNode<T> node, T newObject);
public abstract void InsertAfter(T value, ILinkedListNode<T> newNode);
public abstract void InsertAfter(T value, T newObject);
public abstract T PopFront();
public abstract T PopBack();
public abstract void Clear();
public bool IsEmpty {
get { return Count == 0; }
}
public int Count {
get; protected set;
}
public virtual ILinkedListNode<T> Front {
get; protected set;
}
public virtual ILinkedListNode<T> Back {
get; protected set;
}
public virtual void Sort(IComparer<T> comparer) {
throw new System.NotImplementedException();
}
#endregion
#region IEnumerable<T> Members
public abstract IEnumerator<T> GetEnumerator();
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator() {
return (((IEnumerable<T>)this) as IEnumerable).GetEnumerator();
}
#endregion
}
}
It is worth mentioning that the Front,Back and Count properties have the protected keyword on the setter. The reason for this is we do not want outside classes to be able to modify these values, as they are used internally within the list. The other interesting point here is that the IEnumerator
Our other base class will be the LinkedListNode
namespace DataStructures.LinkedList.Nodes {
public abstract class LinkedListNodeBase<T> : ILinkedListNode<T> {
#region INode<T> Members
public T Value {
get; set;
}
#endregion
}
}
This is straight forward. All linked list nodes need to store a value of some sort. Now we are ready to implement our actual singly linked list, and the corresponding singly linked list node.
namespace DataStructures.LinkedList.Nodes {
public class SinglyLinkedListNode<T> : LinkedListNodeBase<T> {
public SinglyLinkedListNode() {
}
public SinglyLinkedListNode(T value) {
Value = value;
}
public SinglyLinkedListNode<T> Next {
get; set;
}
public override bool Equals(object obj) {
SinglyLinkedListNode<T> node = obj as SinglyLinkedListNode<T>;
if(null == node) {
return false;
}
return Value.Equals(node.Value);
}
}
}
In the SinglyLinkedListNode
And now that we have the foundation for our linked list, we are going to implement the actual list that will be the heart of what we are doing.
using System;
using System.Collections.Generic;
using DataStructures.LinkedList.Nodes;
using DataStructures.Exception;
namespace DataStructures.LinkedList.Impl {
public class SinglyLinkedList<T> : LinkedListBase<T> {
}
}
Now lets start implementing the members of the class. The Front and Back properties hide their base implementations with the new keyword, but call back to the base to set the value. This allows us to cast the ILinkedListNode
public new SinglyLinkedListNode<T> Front {
get { return base.Front as SinglyLinkedListNode<T>; }
protected set { base.Front = value; }
}
public new SinglyLinkedListNode<T> Back {
get { return base.Back as SinglyLinkedListNode<T>; }
protected set { base.Back = value; }
}
Next, we implement the PushFront() methods. The PushFront() method allows us to add a node to the beginning of the linked list. The implementation here is simply. We must consider a few conditions. We must check whether or not the list is empty, and if so, then both the Front of the list, and the Back of the list will point to the same node. Otherwise, we just have to update the Front property and point that node’s Next property at the former Front of the list.
public override void PushFront(T item) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(item);
PushFront(node);
}
public virtual void PushFront(SinglyLinkedListNode<T> item) {
item.Next = Front;
Front = item;
if (IsEmpty) {
Back = Front;
}
Count++;
}
Next comes the implementation of adding a node to the back of the list. Here, we must check if the list is empty or not. If it is, then there will only be one node in the list after it has been added, and that will be both the Front and the Back of the list. Otherwise, if we have at least one node in the list, then the node’s last node’s Next becomes the new node, and we then just update the Back to point at the new node.
public override void PushBack(T item) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(item);
PushBack(node);
}
public virtual void PushBack(SinglyLinkedListNode<T> item) {
if (IsEmpty) {
Back = item;
Front = Back;
} else {
Back.Next = item;
Back = item;
}
Count++;
}
Now come the more tricky inserting methods. Inserting before a specified node, and inserting after a specified node. In the first case, there are a few things to consider. The first one is whether or not the list is empty. In our implementation, if the list is empty, then we will not be able to find any node to insert an object before, therefore, we throw an exception. Otherwise, we need to traverse the list, while keeping track of the current node that we are on, and the one before it. If we find that the current node that we are on is the node to insert before, then we take the pointer to the previous node, and do our insertion there. The insertion is similar to the way that we inserted to the front of the list. We just take the previous node’s Next pointer, point that at our new node, and point our new node’s Next property at the current node.
public override void InsertBefore(ILinkedListNode<T> node, ILinkedListNode<T> newNode) {
SinglyLinkedListNode<T> compareNode, current, previous = null, theNewNode;
compareNode = node as SinglyLinkedListNode<T>;
theNewNode = newNode as SinglyLinkedListNode<T>;
if (IsEmpty) {
throw new InvalidOperationException();
}
current = Front;
while (current != null) {
if (current.Equals(compareNode)) {
theNewNode.Next = current;
if (previous == null) {
Front = theNewNode;
} else {
previous.Next = theNewNode;
}
Count++;
return;
}
previous = current;
current = current.Next;
}
throw new NodeNotFoundException<T>(node);
}
public override void InsertBefore(ILinkedListNode<T> node, T newObject) {
InsertBefore(node, new SinglyLinkedListNode<T>(newObject));
}
public override void InsertBefore(T value, ILinkedListNode<T> newNode) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value);
SinglyLinkedListNode<T> newOne = newNode as SinglyLinkedListNode<T>;
InsertBefore(node, newOne);
}
public override void InsertBefore(T value, T newObject) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value);
SinglyLinkedListNode<T> newObjNode = new SinglyLinkedListNode<T>(newObject);
InsertBefore(node, newObjNode);
}
A similar implementation exists for inserting after an object, except now you just need to keep track of the node that is one ahead, and the current node.
public override void InsertAfter(ILinkedListNode<T> node, ILinkedListNode<T> newNode) {
SinglyLinkedListNode<T> compareNode, current, next, theNewNode;
compareNode = node as SinglyLinkedListNode<T>;
theNewNode = newNode as SinglyLinkedListNode<T>;
if (IsEmpty) {
throw new InvalidOperationException();
}
current = Front;
next = current.Next;
while (current != null) {
if (current.Equals(compareNode)) {
current.Next = theNewNode;
theNewNode.Next = next;
if (next == null) {
Back = theNewNode;
}
Count++;
return;
}
current = current.Next;
next = current == null ? null : current.Next;
}
throw new NodeNotFoundException<T>(node);
}
public override void InsertAfter(ILinkedListNode<T> node, T newObject) {
InsertAfter(node, new SinglyLinkedListNode<T>(newObject));
}
public override void InsertAfter(T value, ILinkedListNode<T> newNode) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value);
SinglyLinkedListNode<T> newOne = newNode as SinglyLinkedListNode<T>;
InsertAfter(node, newOne);
}
public override void InsertAfter(T value, T newObject) {
SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value);
SinglyLinkedListNode<T> newObjNode = new SinglyLinkedListNode<T>(newObject);
InsertAfter(node, newObjNode);
}
Of course, if you are able to add a node to a list, then we must be able to remove a node. Below are the implementations to removing the first node from the list, and the last node from the list. There are two differences however in these operations. When inserting into the beginning of the list, the operation is O(1), whereas inserting to the end of the list is an O(n) operation, since we must traverse the list before we are able to insert to the end. Note that in a doubly linked list, this is not the case, and that insertion to the end of the list is also an O(1) operation, since it references the node that is before the last one.
public override T PopFront() {
if (IsEmpty) {
throw new InvalidOperationException("The specified list is empty.");
}
SinglyLinkedListNode<T> temp = Front;
Front = Front.Next;
Count--;
if (Count == 0) {
Back = Front;
}
return temp.Value;
}
public override T PopBack() {
SinglyLinkedListNode<T> temp;
if (IsEmpty) {
throw new InvalidOperationException("The specified list is empty.");
}
if (Count == 1) {
temp = Back;
Front = null;
Back = null;
} else {
SinglyLinkedListNode<T> current = Front;
SinglyLinkedListNode<T> previous = null;
while (current.Next != null) {
// Traverse to the last nodes in the list.
previous = current;
current = current.Next;
}
temp = current;
Back = previous;
Back.Next = null;
}
Count--;
return temp.Value;
}
The third method that we are going to implement to remove nodes from our linked list is the Clear() method. It is straight forward, since in C#, garbage collection is handled automatically for us. All we need to do is no longer reference the nodes.
public override void Clear() {
Front = null;
Back = null;
Count = 0;
}
And finally, we must implement IEnumerable
#region IEnumerable<T> Members
public override IEnumerator<T> GetEnumerator() {
SinglyLinkedListNode<T> iter = Front;
while(null != iter) {
yield return (T)iter.Value;
iter = iter.Next;
}
}
#endregion
And there you have it. We have implemented our linked list classes, including insertion and removing of nodes, as well as laid down a foundation on which to build upon in further data structures.
I hope that this has helped, and if you have any questions or comments, or improvements to my code, feel free to leave a comment.