Tutorial on LinkedList in C#

The LinkedList<T> class in C# is part of the System.Collections.Generic namespace and represents a doubly linked list of objects. Unlike arrays or lists, linked lists do not use contiguous memory for storage.

Each element (node) contains references to both the previous and next elements, allowing efficient insertion and removal of nodes at any position.

LinkedList<T> is particularly useful for scenarios where elements need to be frequently added or removed from the start, end, or middle.

In this tutorial, we’ll cover:

1. Creating a LinkedList<T>

To create a LinkedList<T>, include the System.Collections.Generic namespace. T is the type parameter representing the type of elements in the linked list, such as int, string, or a custom class.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        // Create an empty linked list of integers
        LinkedList<int> numbers = new LinkedList<int>();

        // Create a linked list of strings with initial values
        LinkedList<string> names = new LinkedList<string>(new string[] { "Alice", "Bob", "Charlie" });

        Console.WriteLine("Initial names in linked list:");
        foreach (string name in names) {
            Console.WriteLine(name);
        }
    }
}

Output:

Initial names in linked list:
Alice
Bob
Charlie

In this example:

• LinkedList<int> numbers = new LinkedList<int>(); creates an empty linked list of integers.
• LinkedList<string> names = new LinkedList<string>(new string[] { “Alice”, “Bob”, “Charlie” }); initializes a linked list of strings with values.

2. Adding Elements to the Linked List

You can add elements to a linked list at various positions: at the beginning, at the end, or before/after a specific node.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> numbers = new LinkedList<int>();

        // Adding elements at the end
        numbers.AddLast(10);
        numbers.AddLast(20);
        numbers.AddLast(30);

        // Adding an element at the beginning
        numbers.AddFirst(5);

        Console.WriteLine("Linked list after adding elements:");
        foreach (int number in numbers) {
            Console.WriteLine(number);
        }
    }
}

Output:

Linked list after adding elements:
5
10
20
30

In this example:

• AddLast(10) and AddLast(20) add elements to the end of the list.
• AddFirst(5) adds an element to the beginning of the list.

Adding Elements Before or After a Specific Node

You can add elements before or after specific nodes using AddBefore and AddAfter.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> numbers = new LinkedList<int>(new int[] { 10, 20, 30 });

        // Adding an element before a specific node
        LinkedListNode<int> node20 = numbers.Find(20);
        numbers.AddBefore(node20, 15);

        // Adding an element after a specific node
        numbers.AddAfter(node20, 25);

        Console.WriteLine("Linked list after adding elements before and after 20:");
        foreach (int number in numbers) {
            Console.WriteLine(number);
        }
    }
}

Output:

Linked list after adding elements before and after 20:
10
15
20
25
30

In this example:

• AddBefore(node20, 15) adds 15 before 20.
• AddAfter(node20, 25) adds 25 after 20.

3. Accessing and Modifying Elements

You can access elements by traversing the linked list using nodes. Additionally, First and Last properties return the first and last nodes in the list, respectively.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> numbers = new LinkedList<int>(new int[] { 10, 20, 30 });

        // Access the first and last elements
        Console.WriteLine("First element: " + numbers.First.Value);
        Console.WriteLine("Last element: " + numbers.Last.Value);

        // Modify the first element
        numbers.First.Value = 5;

        Console.WriteLine("Linked list after modifying the first element:");
        foreach (int number in numbers) {
            Console.WriteLine(number);
        }
    }
}

Output:

First element: 10
Last element: 30
Linked list after modifying the first element:
5
20
30

In this example:

• numbers.First.Value accesses the first element (10), which is modified to 5.

4. Removing Elements

You can remove elements from a linked list using Remove, RemoveFirst, and RemoveLast.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> numbers = new LinkedList<int>(new int[] { 10, 20, 30, 40 });

        // Remove a specific element by value
        numbers.Remove(20);

        // Remove the first element
        numbers.RemoveFirst();

        // Remove the last element
        numbers.RemoveLast();

        Console.WriteLine("Linked list after removing elements:");
        foreach (int number in numbers) {
            Console.WriteLine(number);
        }
    }
}

Output:

Linked list after removing elements:
30

In this example:

• Remove(20) removes the element with value 20.
• RemoveFirst() removes the first element.
• RemoveLast() removes the last element.

5. Iterating Through a Linked List

You can iterate through a linked list using a foreach loop. Since linked lists don’t provide direct access by index, each element is accessed sequentially.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<string> names = new LinkedList<string>(new string[] { "Alice", "Bob", "Charlie" });

        Console.WriteLine("Iterating through the linked list:");
        foreach (string name in names) {
            Console.WriteLine(name);
        }
    }
}

Output:

Iterating through the linked list:
Alice
Bob
Charlie

In this example:

• The foreach loop iterates over each element in the linked list sequentially.

6. Practical Examples of LinkedList<T> in Real Scenarios

Example 1: Implementing a Simple Browser History

A LinkedList<T> can represent browser history, where you navigate back and forth between visited pages.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<string> history = new LinkedList<string>();

        // Adding pages to history
        history.AddLast("Page 1");
        history.AddLast("Page 2");
        history.AddLast("Page 3");

        Console.WriteLine("Current page: " + history.Last.Value);

        // Going back to previous page
        LinkedListNode<string> currentPage = history.Last.Previous;
        Console.WriteLine("Going back to: " + currentPage.Value);
    }
}

Output:

Current page: Page 3
Going back to: Page 2

In this example:

• AddLast simulates visiting new pages.
• Last.Previous allows navigating back in history.

Example 2: Implementing a Simple Task List

A LinkedList<T> can manage a to-do list where tasks are added, completed, and removed from the start, end, or middle.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<string> tasks = new LinkedList<string>();

        // Adding tasks
        tasks.AddLast("Task 1");
        tasks.AddLast("Task 2");
        tasks.AddLast("Task 3");

        Console.WriteLine("Task List:");
        foreach (string task in tasks) {
            Console.WriteLine(task);
        }

        // Completing the first task
        tasks.RemoveFirst();

        Console.WriteLine("Updated Task List after removing the first task:");
        foreach (string task in tasks) {
            Console.WriteLine(task);
        }
    }
}

Output:

Task List:
Task 1
Task 2
Task 3
Updated Task List after removing the first task:
Task 2
Task 3

In this example:

• RemoveFirst removes the first task from the to-do list after it is completed.

Summary

In this tutorial, we covered the LinkedList<T> class in C# and demonstrated its features:

1. Creating a LinkedList<T>: Initializing linked lists with or without initial values.
2. Adding Elements: Using AddFirst, AddLast, AddBefore, and AddAfter to add elements in different positions.
3. Accessing and Modifying Elements: Using First, Last, and specific nodes to access and modify elements.
4. Removing Elements

: Using Remove, RemoveFirst, and RemoveLast. 5. Iterating Through a Linked List: Using foreach to iterate sequentially. 6. Practical Examples: Implementing browser history and a task list.

The LinkedList<T> class is ideal for scenarios that require frequent insertion or removal of elements at arbitrary positions, making it useful for tasks like implementing browser history, to-do lists, and other data structures that rely on node traversal.