.NET Linked Lists

Introduction

Linked lists are fundamental data structures that store collections of elements in a sequential manner. Unlike arrays or lists that use contiguous memory locations, linked lists connect elements through references (or links). Each element in a linked list contains data and a reference to the next element in the sequence.

In .NET, the LinkedList<T> class provides a powerful implementation of a doubly linked list, where each node points to both the next and previous nodes, allowing for efficient traversal in both directions.

Understanding Linked Lists in .NET

A linked list in .NET consists of nodes, each containing:

• The actual data (of type T)
• A reference to the next node
• A reference to the previous node (since .NET uses doubly linked lists)

This structure offers several advantages:

• Efficient insertions and deletions at any position
• Dynamic size allocation
• No need to resize or reallocate memory when the collection grows

The LinkedList<T> Class

The LinkedList<T> class is part of the System.Collections.Generic namespace and represents a doubly linked list in .NET.

Basic Properties and Methods

Property/Method	Description
Count	Gets the number of nodes in the linked list
First	Gets the first node in the linked list
Last	Gets the last node in the linked list
AddFirst(T)	Adds a new node containing the specified value at the start
AddLast(T)	Adds a new node containing the specified value at the end
AddBefore()	Adds a new node before an existing node
AddAfter()	Adds a new node after an existing node
Remove(T)	Removes the first occurrence of the specified value
RemoveFirst()	Removes the node at the start
RemoveLast()	Removes the node at the end
Contains(T)	Checks if a value exists in the linked list
Clear()	Removes all nodes from the linked list

Creating and Using a LinkedList in C#

Let's see how to create and manipulate a linked list in C#:

csharp

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // Creating a new linked list of strings
        LinkedList<string> programmingLanguages = new LinkedList<string>();
        
        // Adding elements to the linked list
        programmingLanguages.AddLast("C#");
        programmingLanguages.AddLast("Java");
        programmingLanguages.AddLast("Python");
        
        // Adding an element at the beginning
        programmingLanguages.AddFirst("JavaScript");
        
        // Adding an element after a specific node
        LinkedListNode<string> javaNode = programmingLanguages.Find("Java");
        programmingLanguages.AddAfter(javaNode, "C++");
        
        // Displaying all elements
        Console.WriteLine("Programming Languages in the Linked List:");
        foreach (string language in programmingLanguages)
        {
            Console.WriteLine(language);
        }
        
        // Output:
        // Programming Languages in the Linked List:
        // JavaScript
        // C#
        // Java
        // C++
        // Python
    }
}

Common Linked List Operations

Traversing a Linked List

You can traverse a linked list using a foreach loop or by manually navigating from one node to another:

csharp

// Using foreach (simplest method)
foreach (var item in myLinkedList)
{
    Console.WriteLine(item);
}

// Traversing forward manually using nodes
LinkedListNode<string> current = myLinkedList.First;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

// Traversing backward
LinkedListNode<string> lastNode = myLinkedList.Last;
while (lastNode != null)
{
    Console.WriteLine(lastNode.Value);
    lastNode = lastNode.Previous;
}

Inserting Elements

csharp

LinkedList<int> numbers = new LinkedList<int>();

// Add at beginning
numbers.AddFirst(1);  // List: 1

// Add at end
numbers.AddLast(5);   // List: 1 -> 5

// Add after a specific node
LinkedListNode<int> node = numbers.First;
numbers.AddAfter(node, 2);  // List: 1 -> 2 -> 5

// Add before a specific node
node = numbers.Last;
numbers.AddBefore(node, 3);  // List: 1 -> 2 -> 3 -> 5

Removing Elements

csharp

LinkedList<int> numbers = new LinkedList<int>(new[] { 10, 20, 30, 40, 50 });

// Remove first element
numbers.RemoveFirst();  // List: 20 -> 30 -> 40 -> 50

// Remove last element
numbers.RemoveLast();   // List: 20 -> 30 -> 40

// Remove a specific element
numbers.Remove(30);     // List: 20 -> 40

// Clear the entire list
numbers.Clear();        // List is empty

Searching Elements

csharp

LinkedList<string> fruits = new LinkedList<string>(new[] { "Apple", "Banana", "Cherry", "Date", "Elderberry" });

// Check if element exists
bool containsBanana = fruits.Contains("Banana");  // True
bool containsKiwi = fruits.Contains("Kiwi");     // False

// Find a node containing a specific value
LinkedListNode<string> cherryNode = fruits.Find("Cherry");
if (cherryNode != null)
{
    Console.WriteLine($"Found: {cherryNode.Value}");
    
    // Get adjacent nodes
    if (cherryNode.Previous != null)
        Console.WriteLine($"Previous: {cherryNode.Previous.Value}");
    
    if (cherryNode.Next != null)
        Console.WriteLine($"Next: {cherryNode.Next.Value}");
}

Practical Examples

Example 1: Browser History Navigation

A linked list can effectively model a browser's history for navigation:

csharp

using System;
using System.Collections.Generic;

public class BrowserHistory
{
    private LinkedList<string> history;
    private LinkedListNode<string> currentPage;
    
    public BrowserHistory(string homepage)
    {
        history = new LinkedList<string>();
        currentPage = history.AddLast(homepage);
    }
    
    public void Visit(string url)
    {
        // Remove all forward history
        while (currentPage != history.Last)
        {
            history.Remove(history.Last);
        }
        
        // Add new page
        currentPage = history.AddLast(url);
        Console.WriteLine($"Visited: {url}");
    }
    
    public string Back()
    {
        if (currentPage.Previous != null)
        {
            currentPage = currentPage.Previous;
            Console.WriteLine($"Navigated back to: {currentPage.Value}");
            return currentPage.Value;
        }
        
        Console.WriteLine("Cannot go back, already at oldest page");
        return currentPage.Value;
    }
    
    public string Forward()
    {
        if (currentPage.Next != null)
        {
            currentPage = currentPage.Next;
            Console.WriteLine($"Navigated forward to: {currentPage.Value}");
            return currentPage.Value;
        }
        
        Console.WriteLine("Cannot go forward, already at newest page");
        return currentPage.Value;
    }
    
    public void ShowHistory()
    {
        Console.WriteLine("\nBrowsing History:");
        foreach (string url in history)
        {
            if (url == currentPage.Value)
                Console.WriteLine($"► {url} (current)");
            else
                Console.WriteLine($"  {url}");
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        // Demo browser history
        BrowserHistory browser = new BrowserHistory("https://www.example.com");
        browser.Visit("https://www.google.com");
        browser.Visit("https://www.microsoft.com");
        browser.ShowHistory();
        
        browser.Back();
        browser.Back();
        browser.ShowHistory();
        
        browser.Forward();
        browser.Visit("https://www.github.com");
        browser.ShowHistory();
    }
}

Example 2: Implementing a Music Playlist

csharp

using System;
using System.Collections.Generic;

public class Song
{
    public string Title { get; set; }
    public string Artist { get; set; }
    public TimeSpan Duration { get; set; }
    
    public Song(string title, string artist, TimeSpan duration)
    {
        Title = title;
        Artist = artist;
        Duration = duration;
    }
    
    public override string ToString()
    {
        return $"{Title} by {Artist} ({Duration.Minutes}:{Duration.Seconds:D2})";
    }
}

public class MusicPlaylist
{
    private LinkedList<Song> playlist;
    private LinkedListNode<Song> currentSong;
    
    public MusicPlaylist()
    {
        playlist = new LinkedList<Song>();
    }
    
    public void AddSong(Song song)
    {
        playlist.AddLast(song);
        if (currentSong == null)
            currentSong = playlist.First;
        
        Console.WriteLine($"Added: {song}");
    }
    
    public Song RemoveSong(string title)
    {
        LinkedListNode<Song> songToRemove = null;
        LinkedListNode<Song> current = playlist.First;
        
        while (current != null)
        {
            if (current.Value.Title.Equals(title, StringComparison.OrdinalIgnoreCase))
            {
                songToRemove = current;
                break;
            }
            current = current.Next;
        }
        
        if (songToRemove != null)
        {
            Song removedSong = songToRemove.Value;
            
            // If we're removing the current song, move to the next one
            if (currentSong == songToRemove)
                currentSong = currentSong.Next ?? playlist.First;
            
            playlist.Remove(songToRemove);
            Console.WriteLine($"Removed: {removedSong}");
            return removedSong;
        }
        
        Console.WriteLine($"Song '{title}' not found");
        return null;
    }
    
    public Song Play()
    {
        if (currentSong == null)
        {
            Console.WriteLine("Playlist is empty");
            return null;
        }
        
        Console.WriteLine($"Playing: {currentSong.Value}");
        return currentSong.Value;
    }
    
    public Song Next()
    {
        if (currentSong == null || playlist.Count <= 1)
            return Play();
        
        currentSong = currentSong.Next ?? playlist.First;
        return Play();
    }
    
    public Song Previous()
    {
        if (currentSong == null || playlist.Count <= 1)
            return Play();
        
        currentSong = currentSong.Previous ?? playlist.Last;
        return Play();
    }
    
    public void ShowPlaylist()
    {
        Console.WriteLine("\nCurrent Playlist:");
        if (playlist.Count == 0)
        {
            Console.WriteLine("  (Empty)");
            return;
        }
        
        foreach (Song song in playlist)
        {
            if (currentSong != null && song.Equals(currentSong.Value))
                Console.WriteLine($"► {song}");
            else
                Console.WriteLine($"  {song}");
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        MusicPlaylist myPlaylist = new MusicPlaylist();
        
        myPlaylist.AddSong(new Song("Bohemian Rhapsody", "Queen", new TimeSpan(0, 5, 55)));
        myPlaylist.AddSong(new Song("Hotel California", "Eagles", new TimeSpan(0, 6, 30)));
        myPlaylist.AddSong(new Song("Imagine", "John Lennon", new TimeSpan(0, 3, 4)));
        myPlaylist.AddSong(new Song("Sweet Child O' Mine", "Guns N' Roses", new TimeSpan(0, 5, 56)));
        
        myPlaylist.ShowPlaylist();
        
        myPlaylist.Play();
        myPlaylist.Next();
        myPlaylist.Next();
        
        myPlaylist.RemoveSong("Hotel California");
        myPlaylist.ShowPlaylist();
        
        myPlaylist.Previous();
        myPlaylist.Previous();
    }
}

LinkedList vs. List: When to Use Each

Aspect	LinkedList<T>	List<T>
Memory allocation	Non-contiguous	Contiguous
Access by index	O(n) - must traverse	O(1) - direct access
Insertion/deletion at beginning/middle	O(1) - just update references	O(n) - must shift elements
Insertion/deletion at end	O(1)	O(1) amortized
Memory overhead	Higher (node references)	Lower

Use LinkedList when:

• You need frequent insertions and removals at arbitrary positions
• You don't need random access by index
• You need efficient splitting and combining of lists
• You need to maintain references to specific nodes

Use List when:

• You need frequent random access by index
• Memory efficiency is important
• You need to access elements by position frequently
• You primarily add/remove elements at the end

Common Pitfalls and Best Practices

1. Reference handling: Always check if nodes are null before accessing their values
2. Modifying during enumeration: Don't modify a LinkedList while iterating with foreach
3. Memory management: Be aware that LinkedList uses more memory per element than arrays
4. Node references: Keep track of important nodes to avoid unnecessary traversals
5. Edge cases: Always consider empty lists and single-element lists in your implementations

Summary

.NET's LinkedList<T> implementation provides a versatile doubly linked list data structure that excels at insertions and deletions at arbitrary positions. It's particularly useful for scenarios where elements need to be frequently added or removed from the middle of a collection, such as implementing navigation systems, playlists, or any situation where ordering matters and the collection changes frequently.

While it's not as efficient as arrays or List<T> for random access operations, its node-based structure makes it extremely flexible for certain use cases. Understanding when to use LinkedList versus other collection types is key to writing efficient .NET applications.

Exercises

1. Create a TaskManager class that uses a LinkedList to store tasks with priorities, allowing insertion based on priority level.
2. Implement a text editor's undo/redo functionality using LinkedList.
3. Build a caching system that removes the least recently used items using a LinkedList to track access order.
4. Modify the music playlist example to create a shuffled playlist while still maintaining the ability to move forward and backward.
5. Implement a CircularLinkedList<T> class that automatically wraps around when reaching the end.

Additional Resources

• Official Microsoft Documentation for LinkedList<T>
• Data Structures: Linked Lists in C#
• Advanced Collection Types in .NET
• Choosing the Right Collection Type