Traversal ใน Singly Linked List ด้วย C# LinkedList<T>

System.Collections.Generic.LinkedList<T> เป็น Doubly Linked List Implementation ใน .NET ใช้สำหรับ Insert/Delete ที่เร็ว (O(1)) เมื่อมี Node Reference

Basic Operations

using System;
using System.Collections.Generic;

public class Demo
{
    public static void Main()
    {
        var list = new LinkedList();

        // Add Nodes
        list.AddLast("One");
        list.AddLast("Two");
        list.AddLast("Four");

        Console.WriteLine("Initial Traversal:");
        foreach (var item in list)
            Console.WriteLine(item);

        // Insert Before/After (O(1) - ต้องมี Node Reference)
        var nodeFour = list.Find("Four");
        if (nodeFour != null)
        {
            list.AddBefore(nodeFour, "Three");
            list.AddAfter(nodeFour, "Five");
        }

        Console.WriteLine("\nAfter Insertions:");
        foreach (var item in list)
            Console.WriteLine(item);
    }
}

ผลลัพธ์

Initial Traversal:
One
Two
Four

After Insertions:
One
Two
Three
Four
Five

LinkedList<T> Key Methods

Traversal Patterns

// 1. Forward (foreach - ใช้ Enumerator)
foreach (var item in list) { }

// 2. Forward (Explicit Node)
for (var node = list.First; node != null; node = node.Next)
{
    Console.WriteLine(node.Value);
}

// 3. Backward
for (var node = list.Last; node != null; node = node.Previous)
{
    Console.WriteLine(node.Value);
}

// 4. LINQ (Materializes - O(N) Space)
var array = list.ToArray();
var reversed = list.Reverse().ToList();

Custom Singly Linked List (교육용)

// .NET LinkedList คือ Doubly - สำหรับ Singly ต้อง Implement เอง
public class SinglyLinkedListNode
{
    public T Value { get; set; }
    public SinglyLinkedListNode Next { get; set; }
}

public class SinglyLinkedList
{
    public SinglyLinkedListNode Head { get; private set; }

    public void AddLast(T value)
    {
        var node = new SinglyLinkedListNode { Value = value };
        if (Head == null)
        {
            Head = node;
        }
        else
        {
            var current = Head;
            while (current.Next != null) current = current.Next;
            current.Next = node;
        }
    }

    // Traversal
    public IEnumerable Traverse()
    {
        for (var current = Head; current != null; current = current.Next)
            yield return current.Value;
    }
}

เมื่อไหร่ใช้ LinkedList<T>

• Frequent Insert/Delete at Known Positions (มี Node Reference)
• Queue/Deque Implementation
• LRU Cache (Move to Front)
• Undo/Redo Stack (Doubly Linked)

เมื่อไหร่ ไม่ ควรใช้

• Random Access by Index (ใช้ List/Array)
• Search/Contains บ่อย (O(n) - ใช้ HashSet/Dictionary)
• Memory Critical (Node Overhead ~24-32 bytes/node)
• Cache Performance (Non-contiguous Memory)

Performance: LinkedList vs List

// List: AddLast O(1) Amortized, Insert/Remove Middle O(n)
// LinkedList: AddLast O(1), Insert/Remove Middle O(1)* with Node Ref

// Benchmark: Insert 1000 items at middle
// List:     ~500,000 operations (shift elements)
// LinkedList: ~1,000 operations (pointer changes only)
// แต่ LinkedList มี Overhead ต่อ Node และ Cache Miss มาก