Linked Lists

A linked list is a linear data structure where each element (node) points to the next. Unlike arrays, elements are not stored contiguously in memory.

Singly vs Doubly Linked

• Singly linked: Each node has Data and Next — you can only traverse forward.
• Doubly linked: Each node also has Previous — you can traverse both directions.

Building a Simple Linked List

public class Node<T>
{
    public T Data { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

// Build a list: 10 -> 20 -> 30
var head = new Node<int>(10);
head.Next = new Node<int>(20);
head.Next.Next = new Node<int>(30);

// Traverse
var current = head;
while (current != null)
{
    Console.Write($"{current.Data} -> ");
    current = current.Next;
}
Console.WriteLine("null");
// Output: 10 -> 20 -> 30 -> null

Built-in LinkedList

C# provides LinkedList<T> in System.Collections.Generic, which is a doubly-linked list:

var list = new LinkedList<string>();
list.AddLast("Alice");
list.AddLast("Bob");
list.AddFirst("Zara");

foreach (var name in list)
    Console.WriteLine(name);
// Zara, Alice, Bob

// Find and insert after
var node = list.Find("Alice");
list.AddAfter(node!, "Charlie");

When to Use Linked Lists

Use linked lists when you need frequent insertions/deletions at arbitrary positions and don't need random access.