C# Linked Lists

Introduction

Linked lists are fundamental data structures that store sequences of elements in a linear order. Unlike arrays, linked lists don't store elements in contiguous memory locations but use references (or links) to connect nodes together. Each node contains data and a reference to the next node in the sequence.

In C#, the .NET Framework provides built-in support for linked lists through the LinkedList<T> class in the System.Collections.Generic namespace. This implementation is a doubly-linked list, meaning each node references both the next and previous nodes, allowing for traversal in both directions.

Understanding Linked Lists

What is a Linked List?

A linked list consists of nodes, where each node contains:

Data (the actual value)
Reference to the next node (and previous node in doubly-linked lists)

The first node is called the "head" and the last node is called the "tail". If the linked list is empty, both head and tail are null.

Types of Linked Lists

While C# primarily implements doubly-linked lists, it's helpful to understand different types:

Singly-linked list: Each node references only the next node
Doubly-linked list: Each node references both next and previous nodes
Circular linked list: The tail node references the head node, creating a circle

Using `LinkedList<T>` in C#

Let's start by creating a basic linked list:

csharp
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Creating a linked list of integers
        LinkedList<int> numbers = new LinkedList<int>();
        
        // Adding elements
        numbers.AddLast(10);
        numbers.AddLast(20);
        numbers.AddLast(30);
        
        Console.WriteLine("Linked list elements:");
        foreach (int number in numbers)
        {
            Console.WriteLine(number);
        }
    }
}

Output:

Linked list elements:
10
20
30

Basic `LinkedList<T>` Operations

The LinkedList<T> class provides several methods to manipulate the list:

Adding Elements

csharp
LinkedList<string> names = new LinkedList<string>();

// Add to the end of the list
names.AddLast("Alice");

// Add to the beginning of the list
names.AddFirst("Bob");

// The list now contains: Bob, Alice

// Add after a specific node
LinkedListNode<string> aliceNode = names.Find("Alice");
names.AddAfter(aliceNode, "Charlie");

// Add before a specific node
LinkedListNode<string> charlieNode = names.Find("Charlie");
names.AddBefore(charlieNode, "David");

// The list now contains: Bob, Alice, David, Charlie

Console.WriteLine("Names in the linked list:");
foreach (string name in names)
{
    Console.Write($"{name} ");
}

Output:

Names in the linked list:
Bob Alice David Charlie

Removing Elements

csharp
LinkedList<string> fruits = new LinkedList<string>();
fruits.AddLast("Apple");
fruits.AddLast("Banana");
fruits.AddLast("Cherry");
fruits.AddLast("Date");

// Remove the first node
fruits.RemoveFirst();

// Remove the last node
fruits.RemoveLast();

// Remove a specific node
LinkedListNode<string> bananaNode = fruits.Find("Banana");
if (bananaNode != null)
{
    fruits.Remove(bananaNode);
}

// The list now contains only: Cherry

Console.WriteLine("Remaining fruits:");
foreach (string fruit in fruits)
{
    Console.WriteLine(fruit);
}

Output:

Remaining fruits:
Cherry

Accessing Elements

Unlike arrays or lists, linked lists don't provide direct index-based access. You need to traverse the list to find elements:

csharp
LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(10);
numbers.AddLast(20);
numbers.AddLast(30);

// Access the first element
int first = numbers.First.Value;
Console.WriteLine($"First element: {first}");

// Access the last element
int last = numbers.Last.Value;
Console.WriteLine($"Last element: {last}");

// Find a specific value and get its node
LinkedListNode<int> node = numbers.Find(20);
if (node != null)
{
    Console.WriteLine($"Found value: {node.Value}");
    
    // Access adjacent nodes
    if (node.Previous != null)
        Console.WriteLine($"Previous value: {node.Previous.Value}");
    
    if (node.Next != null)
        Console.WriteLine($"Next value: {node.Next.Value}");
}

Output:

First element: 10
Last element: 30
Found value: 20
Previous value: 10
Next value: 30

`LinkedListNode<T>` Class

When working with linked lists, the LinkedListNode<T> class is essential. It represents a node in the LinkedList<T> and provides properties to access:

The node's value
References to the next and previous nodes
Reference to the containing linked list

csharp
LinkedList<string> colors = new LinkedList<string>();
colors.AddLast("Red");
colors.AddLast("Green");
colors.AddLast("Blue");

// Get the node containing "Green"
LinkedListNode<string> greenNode = colors.Find("Green");

// Properties of the node
Console.WriteLine($"Current value: {greenNode.Value}");
Console.WriteLine($"Previous value: {greenNode.Previous.Value}");
Console.WriteLine($"Next value: {greenNode.Next.Value}");
Console.WriteLine($"Is part of list: {greenNode.List == colors}");

Output:

Current value: Green
Previous value: Red
Next value: Blue
Is part of list: True

Traversing a Linked List

There are multiple ways to traverse a linked list in C#:

Using foreach Loop

csharp
LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(1);
numbers.AddLast(2);
numbers.AddLast(3);

Console.WriteLine("Traversing with foreach:");
foreach (int num in numbers)
{
    Console.Write($"{num} ");
}

Using Node References

csharp
Console.WriteLine("\nTraversing with node references (forward):");
LinkedListNode<int> current = numbers.First;
while (current != null)
{
    Console.Write($"{current.Value} ");
    current = current.Next;
}

Console.WriteLine("\nTraversing with node references (backward):");
current = numbers.Last;
while (current != null)
{
    Console.Write($"{current.Value} ");
    current = current.Previous;
}

Output:

Traversing with foreach:
1 2 3 
Traversing with node references (forward):
1 2 3 
Traversing with node references (backward):
3 2 1

Practical Example: Task Manager

Let's build a simple task manager that uses a linked list to maintain tasks ordered by priority:

csharp
using System;
using System.Collections.Generic;

class Task
{
    public string Description { get; set; }
    public int Priority { get; set; }

    public Task(string description, int priority)
    {
        Description = description;
        Priority = priority;
    }

    public override string ToString()
    {
        return $"[Priority: {Priority}] {Description}";
    }
}

class TaskManager
{
    private LinkedList<Task> tasks = new LinkedList<Task>();

    public void AddTask(string description, int priority)
    {
        Task newTask = new Task(description, priority);
        
        // Find the right position based on priority
        LinkedListNode<Task> current = tasks.First;
        
        // Insert in the right position (lower number = higher priority)
        while (current != null && current.Value.Priority <= priority)
        {
            current = current.Next;
        }
        
        // If current is null, add to the end. Otherwise, insert before current
        if (current == null)
        {
            tasks.AddLast(newTask);
        }
        else
        {
            tasks.AddBefore(current, newTask);
        }
        
        Console.WriteLine($"Added task: {newTask}");
    }

    public void DisplayTasks()
    {
        Console.WriteLine("\nCurrent Tasks:");
        
        if (tasks.Count == 0)
        {
            Console.WriteLine("No tasks.");
            return;
        }
        
        foreach (Task task in tasks)
        {
            Console.WriteLine(task);
        }
    }

    public void CompleteHighestPriorityTask()
    {
        if (tasks.Count == 0)
        {
            Console.WriteLine("No tasks to complete.");
            return;
        }
        
        Task completed = tasks.First.Value;
        tasks.RemoveFirst();
        
        Console.WriteLine($"Completed task: {completed}");
    }
}

class Program
{
    static void Main()
    {
        TaskManager manager = new TaskManager();
        
        manager.AddTask("Finish project proposal", 1);
        manager.AddTask("Call client", 3);
        manager.AddTask("Team meeting", 2);
        manager.AddTask("Urgent bug fix", 1);
        
        manager.DisplayTasks();
        
        manager.CompleteHighestPriorityTask();
        manager.CompleteHighestPriorityTask();
        
        manager.DisplayTasks();
    }
}

Output:

Added task: [Priority: 1] Finish project proposal
Added task: [Priority: 3] Call client
Added task: [Priority: 2] Team meeting
Added task: [Priority: 1] Urgent bug fix

Current Tasks:
[Priority: 1] Finish project proposal
[Priority: 1] Urgent bug fix
[Priority: 2] Team meeting
[Priority: 3] Call client

Completed task: [Priority: 1] Finish project proposal
Completed task: [Priority: 1] Urgent bug fix

Current Tasks:
[Priority: 2] Team meeting
[Priority: 3] Call client

When to Use Linked Lists

Linked lists are particularly useful in the following scenarios:

Frequent insertions and deletions: Linked lists excel when you need to frequently add or remove elements from the middle of a collection.
No random access needed: If you primarily access elements sequentially rather than by index, linked lists are appropriate.
Dynamic size requirements: Linked lists can grow or shrink efficiently without needing to resize or reallocate memory.
Implementation of other data structures: Linked lists serve as building blocks for other data structures like stacks, queues, and certain types of trees.

Linked List vs. List<T> (ArrayList)

Aspect	LinkedList<T>	List<T>
Memory allocation	Non-contiguous	Contiguous
Random access	O(n) - Sequential access only	O(1) - Direct indexing
Insertion/deletion in the middle	O(1) - Once node is located	O(n) - Need to shift elements
Insertion at beginning/end	O(1)	O(1) for end, O(n) for beginning
Memory overhead	Higher (extra references)	Lower
Iterator invalidation	Only affected nodes	Most operations invalidate iterators

Summary

Linked lists are powerful data structures in C# that offer efficient insertion and deletion operations. The .NET Framework provides a robust implementation with the LinkedList<T> class, which is a doubly-linked list allowing traversal in both directions.

Key points to remember:

Linked lists store elements in nodes with references to adjacent nodes
They excel at insertions and deletions in the middle of the collection
They don't provide index-based access like arrays or List<T>
The LinkedListNode<T> class provides access to node values and references

Choosing between a linked list and other collections depends on your specific use case and the operations you'll perform most frequently.

Exercises

Create a linked list of your favorite books and implement a method to find a book by its title.
Implement a music playlist using a linked list where users can:
- Add songs to the beginning or end
- Remove songs from anywhere in the playlist
- Move the current song forward or backward
- Display the current playlist order
Implement a simple text editor that uses a linked list to store lines of text, allowing for efficient insertion and deletion of lines.
Create a custom singly-linked list implementation (without using LinkedList<T>) to understand the underlying mechanics.

Additional Resources

Happy coding with linked lists in C#!

If you spot any mistakes on this website, please let me know at [email protected]. I’d greatly appreciate your feedback! :)

Introduction​

Understanding Linked Lists​

What is a Linked List?​

Types of Linked Lists​

Using LinkedList<T> in C#​

Basic LinkedList<T> Operations​

Adding Elements​

Removing Elements​

Accessing Elements​

LinkedListNode<T> Class​

Traversing a Linked List​

Using foreach Loop​

Using Node References​

Practical Example: Task Manager​

When to Use Linked Lists​

Linked List vs. List<T> (ArrayList)​

Summary​

Exercises​

Additional Resources​

Introduction

Understanding Linked Lists

What is a Linked List?

Types of Linked Lists

Using `LinkedList<T>` in C#

Basic `LinkedList<T>` Operations

Adding Elements

Removing Elements

Accessing Elements

`LinkedListNode<T>` Class

Traversing a Linked List

Using foreach Loop

Using Node References

Practical Example: Task Manager

When to Use Linked Lists

Linked List vs. List<T> (ArrayList)

Summary

Exercises

Additional Resources