03_LinkedList.cs

using System;
using System.Collections.Generic;

namespace DataStructures
{
    /// <summary>
    /// Demonstrates the LinkedList<T> doubly-linked list in C#.
    /// Each node holds a value and references to both the next and previous nodes,
    /// enabling O(1) insertions/removals at known positions.
    /// 
    /// Common use cases: route planners, playlist navigation, undo/redo buffers,
    /// insertion-heavy workloads where List<T> shifts would be expensive.
    /// </summary>
    public class LinkedListExamples
    {
        // ─── Entry Point ───────────────────────────────────────────────
        public static void Main()
        {
            Console.WriteLine("═══════════════════════════════════════════════");
            Console.WriteLine("        C# LinkedList<T> Examples              ");
            Console.WriteLine("═══════════════════════════════════════════════\n");

            // ── 1. Building a Travel Route ──────────────────────────────
            Console.WriteLine("── Building a Travel Route ────────────────────");
            var route = new LinkedList<string>();

            // Add cities to the route
            route.AddLast("London");
            route.AddLast("Paris");
            route.AddLast("Rome");
            Console.WriteLine("  Route: " + string.Join(" → ", route));

            // Add a city at the beginning (starting point)
            route.AddFirst("Edinburgh");
            Console.WriteLine("  After AddFirst(\"Edinburgh\"): " + string.Join(" → ", route));

            // Add a city after a specific node
            LinkedListNode<string> parisNode = route.Find("Paris");
            if (parisNode != null)
            {
                route.AddAfter(parisNode, "Barcelona");
                Console.WriteLine("  After AddAfter(Paris, Barcelona): " + string.Join(" → ", route));
            }

            // Add a city before a specific node
            LinkedListNode<string> romeNode = route.Find("Rome");
            if (romeNode != null)
            {
                route.AddBefore(romeNode, "Zurich");
                Console.WriteLine("  After AddBefore(Rome, Zurich): " + string.Join(" → ", route));
            }
            Console.WriteLine();

            // ── 2. Navigating the Linked List ──────────────────────────
            Console.WriteLine("── Navigating the Route ───────────────────────");
            Console.WriteLine($"  First city : {route.First.Value}");
            Console.WriteLine($"  Last city  : {route.Last.Value}");
            Console.WriteLine($"  Total stops: {route.Count}");
            Console.WriteLine();

            // Forward traversal using nodes
            Console.WriteLine("  Forward traversal:");
            LinkedListNode<string> current = route.First;
            int stop = 1;
            while (current != null)
            {
                Console.WriteLine($"    Stop {stop}: {current.Value}");
                current = current.Next;
                stop++;
            }
            Console.WriteLine();

            // Backward traversal using nodes
            Console.WriteLine("  Reverse traversal:");
            current = route.Last;
            stop = route.Count;
            while (current != null)
            {
                Console.WriteLine($"    Stop {stop}: {current.Value}");
                current = current.Previous;
                stop--;
            }
            Console.WriteLine();

            // ── 3. Finding & Removing Nodes ────────────────────────────
            Console.WriteLine("── Find & Remove Operations ──────────────────");

            // Find a specific node
            LinkedListNode<string> found = route.Find("Barcelona");
            Console.WriteLine($"  Find(\"Barcelona\") → {(found != null ? "Found" : "Not found")}");

            // Find from the end (FindLast)
            route.AddLast("Paris"); // duplicate — Paris appears twice
            LinkedListNode<string> lastParis = route.FindLast("Paris");
            Console.WriteLine($"  FindLast(\"Paris\") → value = {lastParis.Value}");
            Console.WriteLine($"  Next after last Paris: {lastParis.Next?.Value ?? "(end of list)"}");

            // Remove a specific value
            route.Remove("Paris"); // removes first occurrence
            Console.WriteLine($"  After Remove(\"Paris\"): " + string.Join(" → ", route));

            // Remove first and last
            route.RemoveFirst();
            route.RemoveLast();
            Console.WriteLine($"  After RemoveFirst + RemoveLast: " + string.Join(" → ", route));

            // Remove a specific node
            LinkedListNode<string> zurichNode = route.Find("Zurich");
            if (zurichNode != null)
            {
                route.Remove(zurichNode);
                Console.WriteLine($"  After removing Zurich node: " + string.Join(" → ", route));
            }
            Console.WriteLine();

            // ── 4. Contains & Clear ─────────────────────────────────────
            Console.WriteLine("── Contains & Clear ──────────────────────────");
            Console.WriteLine($"  Contains(\"Rome\"): {route.Contains("Rome")}");
            Console.WriteLine($"  Contains(\"Tokyo\"): {route.Contains("Tokyo")}");
            Console.WriteLine($"  Count before clear: {route.Count}");
            route.Clear();
            Console.WriteLine($"  Count after clear:  {route.Count}");

            Console.WriteLine("\n═══════════════════════════════════════════════");
            Console.WriteLine("  Complexity: AddFirst/Last O(1) | AddAfter/Before O(1)");
            Console.WriteLine("  Find O(n) | Remove(node) O(1) | Remove(value) O(n)");
            Console.WriteLine("═══════════════════════════════════════════════");
        }
    }
}