Implementing LinkedList and DoubleLinkedList in C#.
April 18, 2026•1,049 words
Linked lists are one of the fundamental tools in computer data structures. These data structures play a crucial role in a wide range of applications, from database implementation to games, from web applications to image processing. In this article, we will explore linked lists and their variations, focusing in particular on double linked lists and the advantages they offer over traditional linked lists.
What is a LinkedList
A linked list is a collection of nodes, each of which contains a piece of data and a reference (or "link") to the next node in the sequence. The starting node is called the "head", and the ending node has a null reference, indicating the end of the list.
Linked lists can be of various types, including:
- Single Linked List: Each node has only one reference to the next node. It is the simplest form of linked list.
- Double linked list: Each node has references to both the next and previous nodes. This structure offers more flexibility than individual linked lists.
- Circular Linked List: The last node of the list has a reference to the first node, creating a loop.
Single LinkedList
This is an implementation of a Linked List node
public class Node<T>{
public T Item;
public Node<T>? Next;
}
There are three main operation on a linked list: AddFirst to ad a new item to the top, AddLast to add a new item at the end of the list, Remove to delete a specific item of the list.
/// Adds a new item to the top of the list
public void AddFirst(T item) {
Node<T> newNode = new Node<T>();
newNode.Item = item;
newNode.Next = null;
if (Size != 0) {
newNode.Next = Head;
}
Head = newNode;
Size++;
}
/// Adds a new item at the end of the list
public void AddLast(T item) {
Node<T> newNode = new Node<T>();
newNode.Item = item;
newNode.Next = null;
if (Size == 0) {
Head = newNode;
} else {
Node<T>? tmpNode = Head;
// Iterate all items
while (tmpNode.Next is not null) {
tmpNode = tmpNode.Next;
}
tmpNode.Next = newNode;
}
Size++;
}
/// Remove an item from the list
public void Remove(int position) {
if (position < 0 || Size < 1 || position >= Size) {
throw new ArgumentOutOfRangeException();
// Handle the case of a list with one element
} else if (Size == 1) {
Head = null;
Size--;
// Handle the case of removing the first element of the list
} else if (position == 0) {
Head = Head.Next;
Size--;
} else {
Node<T>? tmpNode = Head;
Node<T>? tmpPrevious = null;
for (var i = 0; tmpNode is not null && i < position; i++) {
tmpPrevious = tmpNode;
tmpNode = tmpNode.Next;
}
tmpPrevious.Next = tmpNode.Next;
Size--;
}
}
This is the full implementation of LinkedList class.
Double LinkedList
A double linked list structure offers some important advantages over single linked lists:
- Traversability in both directions: In double linked lists, it is possible to traverse the list both forwards and backwards, which is useful in situations where you need to examine or modify data both before and after the current node.
- Ease of deleting nodes: Deleting a node from a double linked list is more efficient than a single linked list, as it is possible to directly access the previous and next node.
- Efficient insertions at the beginning and end: Adding or removing nodes at the beginning or end of a double linked list is just as efficient as doing it in the middle.
This is a typical double linked list node.
public DoubleLinkedList() {
Head = null;
Tail = null;
Size = 0;
}
Here the implementation of main operation on a double linked list
/// Adds a new item to the top of the list
public void AddFirst(T item) {
Node<T> newNode = new Node<T>();
newNode.Item = item;
newNode.Next = null;
newNode.Prev = null;
// Handle the case of a list with zero element
if (Size == 0) {
Head = newNode;
Tail = newNode;
// Handle the case of a list with one element
} else if (Size == 1) {
newNode.Next = Tail;
Head = newNode;
Tail.Prev = newNode;
} else{
newNode.Next = Head;
Head = newNode;
}
Size++;
}
/// Adds a new item at the end of the list
public void AddLast(T item) {
Node<T> newNode = new Node<T>();
newNode.Item = item;
newNode.Next = null;
newNode.Prev = null;
// Handle the case of a list with zero element
if (Size == 0) {
Head = newNode;
Tail = newNode;
// Handle the case of a list with one element
} else if (Size == 1) {
newNode.Prev = Head;
Head.Next = newNode;
Tail = newNode;
} else {
Tail.Next = newNode;
newNode.Prev = Tail;
Tail = newNode;
}
Size++;
}
/// Remove an item from the list
public void Remove(int position) {
if (position < 0 || Size < 1 || position >= Size) {
throw new ArgumentOutOfRangeException();
// Handle the case of a list with one element
} else if (Size == 1) {
Head = null;
Tail = null;
Size--;
// Handle the case of removing the first element of the list
} else if (position == 0) {
Head = Head.Next;
Head.Prev = null;
Size--;
// Handle the case of removing the last element of the list
} else if (position == Size - 1) {
Tail = Tail.Prev;
Tail.Next = null;
Size--;
} else {
Node<T>? tmpNode = Head;
for (var i = 0; tmpNode is not null && i < position; i++) {
tmpNode = tmpNode.Next;
}
tmpNode.Prev.Next = tmpNode.Next;
tmpNode.Next.Prev = tmpNode.Prev;
Size--;
}
}
This is the full implementation of DoubleLinkedList class.
Follow @gslf Sponsor Watch Star
Linked lists, along with their variants such as double linked lists, are essential tools in computer data structures. They are used in a wide range of applications and offer key advantages in terms of flexibility and speed of insertion/deletion. The choice between a single linked list and a double linked list depends on the specific needs of your project. Understanding these data structures and their uses will allow you to write more efficient and flexible code.