How to use LinkedList in C#

A LinkedList<T> consists of nodes, each holding a value (such as integers, strings, or other types) and pointers (or links) to the next and previous nodes in the list. This allows for quick insertion and removal of elements at both ends of the list. The LinkedList<T> maintains references to both the head (first node) and tail (last node), enabling efficient operations on both ends without the need to traverse the entire list.

The LinkedList<T> can be used in many scenarios, one of which is implementing a stack (Last-In-First-Out or LIFO structure). By inserting and removing elements from the start of the list, we can easily simulate stack operations.

var linkedList = new LinkedList<int>();
// head -> null <- tail

linkedList.AddFirst(1);
// head -> 1 <- tail

linkedList.AddFirst(2);
// head -> 2 <-> 1 <- tail

Console.WriteLine($"Value={linkedList.First.Value}"); // Outputs: Value=2
linkedList.RemoveFirst();
// head -> 1 <- tail

Console.WriteLine($"Value={linkedList.First.Value}"); // Outputs: Value=1
linkedList.RemoveFirst();
// head -> null <- tail

In this example:

1. We start with an empty list.
2. We use AddFirst() to insert elements at the start of the list. Each insertion moves the new element to the front.
3. The RemoveFirst() method removes the node from the front, making the next element the new head of the list.
4. The output shows the value of the first element (linkedList.First.Value), and the list adjusts accordingly after each removal.

Primary Methods and Properties of LinkedList<T>

LinkedList<T> offers a variety of methods and properties to make working with the list easier, particularly when you need to frequently insert or remove elements at the start or end.

Here’s a list of the primary methods and properties:

• AddFirst(): Inserts a node at the start of the list.
• AddLast(): Inserts a node at the end of the list.
• First: The node at the start of the list (head).
• Last: The node at the end of the list (tail).
• RemoveFirst(): Removes the node at the start of the list.
• RemoveLast(): Removes the node at the end of the list.

The removal methods (RemoveFirst() and RemoveLast()) are void methods. They remove the node but don’t return a value. To access the node's value before removal, you can use the First or Last properties.

Iterating Through the LinkedList<T>

You can easily iterate through the elements of a LinkedList<T> using a foreach loop, just like you would with a List<T>.

var linkedList = new LinkedList<int>();
linkedList.AddFirst(1);
linkedList.AddFirst(2);
linkedList.AddFirst(3);

foreach (var val in linkedList)
{
    Console.WriteLine(val);
}

Output:

3
2
1

In this example, the elements are printed in reverse order because AddFirst() inserts elements at the head of the list. The iteration starts from the head and traverses through the list until it reaches the tail.

LinkedList<T> vs List<T>

While both LinkedList<T> and List<T> are useful collections in C#, they have significant differences when it comes to performance, particularly in terms of insertion and removal.

• LinkedList<T> is a doubly linked list, meaning that adding or removing elements at both the head and tail of the list is an O(1) operation. This makes it ideal for scenarios where you need to frequently insert or remove elements from the ends of the list.
• List<T>, on the other hand, is backed by a dynamically-sized array. Adding elements to the end of the list is efficient, with O(1) time complexity on average. However, inserting or removing elements at arbitrary positions (especially at the start) requires shifting all the elements, which takes O(n) time.

Therefore, if your application involves frequent insertions or removals at the head or tail, a LinkedList<T> is generally much faster than a List<T>. In fact, performance tests show that using a LinkedList<T> can be up to 30 times faster than using a List<T> for such operations.

// Inserting at the start of List<T>
var list = new List<int>();
for (int i = 0; i < 10000; i++)
{
    list.Insert(0, i);  // O(n) operation
}

// Inserting at the start of LinkedList<T>
var linkedList = new LinkedList<int>();
for (int i = 0; i < 10000; i++)
{
    linkedList.AddFirst(i);  // O(1) operation
}

In this case, inserting at the start of a List<T> involves shifting all the elements, which becomes increasingly slower as the list grows. However, with LinkedList<T>, each insertion is O(1) regardless of the list size, making it a far more efficient choice in such cases.

The LinkedList<T> class in C# is a powerful collection for scenarios that require frequent insertions and removals from both ends of the list. By leveraging its doubly linked list structure, LinkedList<T> provides O(1) performance for these operations, making it a better choice than List<T> when working with head/tail insertions or removals.