C# ile Linked List: Node'lar, Sentinel ve Klasik Linked List Problemleri

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

1.000.000 sipariş tutarını toplayacaksın. Tutarlar üç farklı yapıda duruyor: bir List<int>, BCL'nin (Base Class Library) LinkedList<int>'i ve kendi yazdığımız, node'ları bellekte rastgele dağılmış bir singly linked list. Üçü de aynı 1.000.000 toplamayı yapıyor ve hiçbiri heap'te yer ayırmıyor.

List 0,3 ms sürüyorsa LinkedList<int> ne kadar sürer? Peki node'ları dağınık olan liste? İkinci bir soru: 100.000 int'i List'te tutmak 400 KB civarında bellek alıyor. Aynı 100.000 int LinkedList<int>'te kaç byte tutar?

Node'lar ve Singly Linked List

Linked list, element'leri bellekte yan yana değil, her biri bir sonrakini gösteren ayrı node'larda tutar. Array'in tersine, bir element eklemek ya da çıkarmak için kimseyi kaydırmak gerekmez; iki reference'ı değiştirmek yeter. Bedeli de array'in tersine: i'nci element'e gitmek için baştan i adım yürümek gerekir, index ile erişim yoktur.

namespace Algorithms.Linear;

public sealed class ListNode<T>(T value)
{
    public T Value { get; set; } = value;
    public ListNode<T>? Next { get; set; }
}

Bu node'larla kurduğumuz singly linked list, başta bir sentinel node tutuyor:

using System.Collections;

namespace Algorithms.Linear;

public sealed class SinglyLinkedList<T> : IEnumerable<T>
{
    // sentinel: her zaman var, hiç veri tutmaz; "boş liste" ve "ilk node" özel durum olmaktan çıkar
    private readonly ListNode<T> _head = new(default!);
    private ListNode<T> _tail;

    public SinglyLinkedList() => _tail = _head;

    public int Count { get; private set; }
    public ListNode<T>? First => _head.Next;

    public void AddFirst(T value)
    {
        ListNode<T> node = new(value) { Next = _head.Next };
        _head.Next = node;
        if (_tail == _head) _tail = node;
        Count++;
    }

    public void AddLast(T value)
    {
        ListNode<T> node = new(value);
        _tail.Next = node;
        _tail = node;
        Count++;
    }

    public bool Remove(T value)
    {
        EqualityComparer<T> comparer = EqualityComparer<T>.Default;
        // "previous" sentinel'den başlar: ilk node'u silmek özel bir durum değil
        for (ListNode<T> previous = _head; previous.Next is { } current; previous = current)
        {
            if (!comparer.Equals(current.Value, value)) continue;
            previous.Next = current.Next;
            if (current == _tail) _tail = previous;
            Count--;
            return true;
        }
        return false;
    }

    public void Reverse()
    {
        ListNode<T>? oldFirst = _head.Next;
        _head.Next = LinkedListProblems.Reverse(oldFirst);
        if (oldFirst is not null) _tail = oldFirst;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (ListNode<T>? node = _head.Next; node is not null; node = node.Next)
            yield return node.Value;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Sentinel ile Edge Case'leri Yok Etmek

Sentinel olmadan Remove yazmayı dene. İlk node silinecekse _head'i güncellemen gerekir, ortadaki bir node silinecekse bir önceki node'un Next'ini. Liste boşsa ayrı bir kontrol, tek elemanlıysa _tail'i de null'a çekmek için bir kontrol daha. Linked list hatalarının çoğu bu dallarda: ilk ya da son element silinince bozulan bir _tail, boş listede NullReferenceException.

Sentinel (dummy head), hiçbir zaman veri tutmayan ve hiçbir zaman silinmeyen bir node. Her gerçek node'un artık bir öncesi var; ilk node'un öncesi sentinel. Remove'daki döngü previous = _head'den başladığı için ilk node'u silmek, ortadakini silmekle aynı iki satır. Boş liste de _head.Next == null olan liste; özel bir kontrol gerektirmiyor. Bedeli tek bir fazladan node.

Testler, en çok bozulan iki yeri hedefliyor: baştan, ortadan ve sondan silme sonrası _tail'in doğru yerde kalması ve reverse sonrası AddLast'in yeni sona eklemesi:

[Fact]
public void SinglyRemove_FirstMiddleLast_KeepsListConsistent()
{
    SinglyLinkedList<string> list = new();
    foreach (string s in new[] { "a", "b", "c", "d" }) list.AddLast(s);

    Assert.True(list.Remove("a"));
    Assert.True(list.Remove("c"));
    Assert.True(list.Remove("d"));
    list.AddLast("e"); // tail "b"ye geri dönmüş olmalı

    Assert.Equal(["b", "e"], list);
    Assert.Equal(2, list.Count);
}

[Fact]
public void SinglyReverse_ThenAddLast_UsesNewTail()
{
    SinglyLinkedList<int> list = new();
    foreach (int i in new[] { 1, 2, 3 }) list.AddLast(i);

    list.Reverse();
    list.AddLast(0);

    Assert.Equal([3, 2, 1, 0], list);
}

Doubly Linked List ve Circular Sentinel

Singly linked list'te bir node'u silmek için önceki node'u bilmen gerekir; elinde yalnızca silinecek node varsa baştan aramak zorundasın. Doubly linked list her node'da Previous'ı da tutar ve elindeki node'u O(1)'de çıkarır. Sentinel'i circular yaparsan, yani sentinel'in Next'i ilk node'u, Previous'ı son node'u gösterirse, null kontrolü tamamen ortadan kalkar:

using System.Collections;

namespace Algorithms.Linear;

public sealed class DoublyNode<T>(T value)
{
    public T Value { get; set; } = value;
    public DoublyNode<T> Previous { get; internal set; } = null!;
    public DoublyNode<T> Next { get; internal set; } = null!;
}

public sealed class DoublyLinkedList<T> : IEnumerable<T>
{
    // circular sentinel: sentinel.Next ilk node, sentinel.Previous son node
    private readonly DoublyNode<T> _sentinel;

    public DoublyLinkedList()
    {
        _sentinel = new DoublyNode<T>(default!);
        _sentinel.Next = _sentinel.Previous = _sentinel;
    }

    public int Count { get; private set; }

    public DoublyNode<T> AddLast(T value) => InsertAfter(_sentinel.Previous, value);
    public DoublyNode<T> AddFirst(T value) => InsertAfter(_sentinel, value);

    private DoublyNode<T> InsertAfter(DoublyNode<T> previous, T value)
    {
        DoublyNode<T> node = new(value) { Previous = previous, Next = previous.Next };
        previous.Next.Previous = node;
        previous.Next = node;
        Count++;
        return node;
    }

    // O(1): node iki komşusunu da biliyor, arama gerekmiyor
    public void Remove(DoublyNode<T> node)
    {
        node.Previous.Next = node.Next;
        node.Next.Previous = node.Previous;
        node.Next = node.Previous = null!;
        Count--;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (DoublyNode<T> node = _sentinel.Next; node != _sentinel; node = node.Next)
            yield return node.Value;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

AddFirst ve AddLast aynı InsertAfter'ı çağırıyor; boş listede de dolu listede de aynı dört atama çalışıyor. BCL'nin LinkedList<T>'i de doubly ve circular: ayrı bir sentinel tutmuyor ama head alanındaki ilk node'un prev'i son node'u gösteriyor. Her LinkedListNode<T> ayrıca ait olduğu listeye bir reference tutuyor; başka bir listenin node'unu Remove'a verirsen bu sayede exception alıyorsun. API'si (Application Programming Interface) C# Koleksiyonlar serisinin "C# Queue, Stack, LinkedList ve PriorityQueue" yazısında.

Klasik Problemler: Reverse, Cycle, Middle, Merge

Linked list problemleri pointer'ları doğru sırayla değiştirmeyi öğretir. İlki in-place reverse:

public static ListNode<T>? Reverse<T>(ListNode<T>? head)
{
    ListNode<T>? previous = null;
    ListNode<T>? current = head;
    while (current is not null)
    {
        ListNode<T>? next = current.Next; // önce kaydet, yoksa listenin geri kalanı kaybolur
        current.Next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

Her adımda üç pointer var: zaten ters çevrilmiş kısmın başı (previous), şu an işlenen node (current) ve henüz dokunulmamış kısmın başı (next). Sıra önemli: current.Next'i değiştirmeden önce next'e kaydetmezsen, listenin geri kalanına giden tek reference'ı kaybedersin. O kısım artık GC (Garbage Collector) için çöp. O(n) zaman, O(1) ek bellek.

İkincisi cycle detection. Bozuk bir veri ya da hatalı bir bağlama yüzünden son node'un Next'i listede daha önceki bir node'u gösteriyorsa, listeyi gezen her döngü sonsuza kadar döner. Floyd algoritması bunu iki pointer ile ve ek bellek kullanmadan bulur: yavaş olan her adımda bir, hızlı olan iki node ilerler. Cycle yoksa hızlı olan sona ulaşır; cycle varsa hızlı olan yavaşı döngünün içinde arkadan yakalar.

// Floyd: slow 1, fast 2 adım ilerler; yalnızca cycle varsa buluşurlar
public static bool HasCycle<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) return true;
    }
    return false;
}

public static ListNode<T>? CycleStart<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (!ReferenceEquals(slow, fast)) continue;
        // bir pointer'ı başa al; ikisi birer adım ilerleyince cycle'ın başında buluşurlar
        for (slow = head; !ReferenceEquals(slow, fast); slow = slow!.Next, fast = fast!.Next) { }
        return slow;
    }
    return null;
}

CycleStart'taki ikinci aşamanın neden çalıştığının kısa bir hesabı var. Başla cycle'ın başı arasındaki mesafe a, cycle'ın başından buluşma noktasına mesafe b, cycle uzunluğu c olsun. Buluşmada hızlı pointer yavaşın iki katı yol almıştır: 2(a + b) = a + b + kc, yani a = kc − b. Buluşma noktasından a adım daha yürümek, cycle'ın başına denk geliyor. Aynı fast/slow fikri ortadaki node'u da tek geçişte buluyor: hızlı olan sona vardığında yavaş olan ortadadır.

// çift sayıda node'da ortadaki iki node'dan ikincisini döner
public static ListNode<T>? Middle<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow;
}

public static ListNode<int>? MergeSorted(ListNode<int>? a, ListNode<int>? b)
{
    ListNode<int> dummy = new(0);
    ListNode<int> tail = dummy;
    while (a is not null && b is not null)
    {
        // <= eşit değerlerde "a"dakini önce alır: merge stable olur
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else { tail.Next = b; b = b.Next; }
        tail = tail.Next;
    }
    tail.Next = a ?? b;
    return dummy.Next;
}

MergeSorted sentinel fikrinin bir kez daha işe yaradığı yer: dummy sayesinde "sonuç listesinin ilk node'u hangisi?" sorusu için ayrı bir dal yok. Yeni node da ayırmıyor; mevcut node'ları yeniden bağlıyor. Bu method, serinin sorting yazısındaki merge sort'un linked list versiyonunun kalbi. Testler cycle'ı elle kuruyor (5 → 3) ve cycle'ın başlangıç node'unun aynı instance olduğunu doğruluyor:

[Fact]
public void HasCycle_TailPointsBack_DetectsCycleAndStart()
{
    ListNode<int> head = FromValues(1, 2, 3, 4, 5)!;
    ListNode<int> third = head.Next!.Next!;
    ListNode<int> last = third.Next!.Next!;
    last.Next = third; // 5 -> 3

    Assert.True(HasCycle(head));
    Assert.Same(third, CycleStart(head));
    Assert.False(HasCycle(FromValues(1, 2, 3)));
    Assert.Null(CycleStart(FromValues(1, 2, 3)));
}

[Fact]
public void MergeSorted_TwoSortedLists_ReturnsSortedList()
{
    ListNode<int>? merged = MergeSorted(FromValues(1, 4, 9), FromValues(2, 4, 10, 11));

    Assert.Equal([1, 2, 4, 4, 9, 10, 11], ToList(merged));
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.LinkedListTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (600ms)

Test run summary: Passed!
  total: 11
  failed: 0
  succeeded: 11

Linked List Ne Zaman Kaybeder?

Kâğıt üzerinde linked list'in iteration'ı da array'inki gibi O(n). Pratikte iki maliyeti var. Birincisi bellek: her node ayrı bir object, yani her element için bir object header, bir method table pointer ve bağlantı reference'ları. 100.000 int'i iki yapıya ekleyen küçük bir program, GC.GetAllocatedBytesForCurrentThread ile ayrılan byte'ları ölçüyor:

List<int>       100,000 items:      400,056 bytes (4.0 per item)
LinkedList<int> 100,000 items:    4,800,040 bytes (48.0 per item)

4 byte'lık bir int için 48 byte. LinkedListNode<T>'nin 16 byte'lık object başlığı, list, next ve prev için üç 8 byte'lık reference ve 4 byte'lık değer, hizalamayla 48'e yuvarlanıyor. Aynı veri 12 kat bellek alıyor, üstüne 100.000 ayrı object GC'nin her taramada izlemesi gereken 100.000 ayrı hedef.

İkinci maliyet cache. Array'de sıradaki element bir sonraki adreste; işlemci bunu tahmin edip önceden getiriyor. Linked list'te sıradaki node'un adresi ancak mevcut node okununca öğreniliyor (pointer chasing) ve o adres herhangi bir yer olabilir. Benchmark iki tür linked list ölçüyor: node'ları sırayla ayrılmış (yan yana duran) ve node'ları karıştırılmış sırayla bağlanmış, araya çöp ayrılarak dağıtılmış bir liste. İkincisi, uzun süre çalışan bir process'te zamanla büyümüş bir listeye benziyor.

[GlobalSetup]
public void Setup()
{
    _list = [.. Enumerable.Range(0, N)];
    _linkedList = new LinkedList<int>(Enumerable.Range(0, N));
    _ownSequential = LinkedListProblems.FromValues([.. Enumerable.Range(0, N)])!;

    // aynı değerler, ama node'lar karışık sırayla ve aralarına çöp ayrılarak bağlanıyor:
    // sıradaki node genelde bellekte uzakta, uzun süre çalışan bir process'te büyümüş bir liste gibi
    ListNode<int>[] nodes = new ListNode<int>[N];
    for (int i = 0; i < N; i++)
    {
        nodes[i] = new ListNode<int>(i);
        _keepAlive.Add(new byte[48]);
    }
    Random.Shared.Shuffle(nodes);
    for (int i = 0; i < N - 1; i++) nodes[i].Next = nodes[i + 1];
    _ownScattered = nodes[0];
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method             | N       | Mean         | Ratio  | Allocated |
|------------------- |-------- |-------------:|-------:|----------:|
| ListOfInt          | 100000  |     31.68 us |   1.00 |         - |
| BclLinkedList      | 100000  |     89.89 us |   2.84 |         - |
| OwnSequentialNodes | 100000  |     81.86 us |   2.58 |         - |
| OwnScatteredNodes  | 100000  |    867.07 us |  27.37 |         - |
|                    |         |              |        |           |
| ListOfInt          | 1000000 |    319.12 us |   1.00 |         - |
| BclLinkedList      | 1000000 |    907.13 us |   2.84 |         - |
| OwnSequentialNodes | 1000000 |    817.50 us |   2.56 |         - |
| OwnScatteredNodes  | 1000000 | 82,700.92 us | 259.16 |         - |

Node'lar sırayla ayrıldığında linked list List'ten yaklaşık 2,6–2,8 kat yavaş. .NET'in allocator'ı ardışık object'leri yan yana koyduğu için prefetch hâlâ bir ölçüde çalışıyor. Node'lar dağınıkken tablo değişiyor: 100.000 node'da 27 kat, 1.000.000 node'da 259 kat. 1 milyon dağınık node, cache'e hiç sığmayan yaklaşık 100 MB'lık bir alana yayılıyor; her adım büyük olasılıkla ana belleğe kadar giden bir okuma. Complexity aynı, O(n); aradaki fark tamamen sabitlerde. Bu yüzden "linked list'te ekleme O(1)" bilgisi tek başına seçim yapmaya yetmiyor; Big-O ve Complexity serisinin "Big-O'nun Söylemedikleri" yazısı bu farkın genel hâlini anlatıyor.

Üretimde Dikkat

Linked list'in gerçek avantajı "elinde bir node varsa onu O(1)'de çıkarabilmek ya da yanına ekleyebilmek". En bilinen kullanımı LRU (Least Recently Used) cache: bir Dictionary<TKey, LinkedListNode<TValue>> key'den node'a O(1)'de götürür, doubly linked list de erişilen node'u O(1)'de en başa taşır ve en sondakini atar. Arama yapman gereken her senaryoda ise (değere göre bul, sonra sil) bu avantaj kayboluyor; arama zaten O(n).

Index ile erişim isteyen kodu linked list'e bağlama. ElementAt(i) bir LinkedList<T> üzerinde her çağrıda baştan i adım yürür; bir for döngüsü içinde kullanılınca O(n²) olur. LinkedList<T>'in IList<T>'yi implement etmemesinin nedeni bu.

Varsayılan seçim yine List<T>. Ortadan silme sık ama liste birkaç bin elemanlıysa, List'in kaydırması (bellekte ardışık blok kopyası) çoğu zaman linked list'te node aramaktan hızlı çıkar. Karar vermeden önce kendi n'inle ölç.

Sık Düşülen Tuzaklar

Reverse'te next'i kaybetmek. current.Next = previous satırı, next = current.Next'ten önce yazılırsa liste ilk node'da kopar ve geri kalanı kaybolur. Pointer değiştiren her kodda önce kaydet, sonra değiştir.

Cycle'lı listede sonsuz döngü. Dışarıdan gelen ya da elle bağlanan bir yapıyı gezerken cycle olasılığı varsa, ya Floyd ile önce kontrol et ya da gezmeye bir üst sınır koy. Bu yazının test yardımcısı ToList'in 1.000 elemanlık bir limit parametresi var; cycle'lı bir listeyi yanlışlıkla gezen bir test donmak yerine başarısız oluyor.

Tail'i güncellemeyi unutmak. Son node silinince ya da liste ters çevrilince _tail eski node'u göstermeye devam ederse, bir sonraki AddLast listeden kopmuş bir node'a ekler ve element sessizce kaybolur. Testleri tam bu senaryolar için yaz.

Node'u listeden çıkardıktan sonra bağlantılarını bırakmak. Çıkarılmış bir node hâlâ komşularını gösteriyorsa, dışarıda o node'u tutan bir kod bütün listeyi canlı tutabilir. DoublyLinkedList.Remove, çıkardığı node'un Next ve Previous'ını bu yüzden temizliyor.

Küçük Bir Deneme

★☆☆ SinglyLinkedList<T>'e RemoveAll(Predicate<T> match) ekle. Sentinel sayesinde tek bir döngüyle yazılabildiğini göster ve baştaki, ortadaki ve sondaki node'ları silen bir test yaz.

★★☆ İki sıralı listeyi birleştiren MergeSorted'ı ve Middle'ı kullanarak linked list için merge sort yaz: listeyi ortadan ikiye böl, iki yarıyı recursive sırala, birleştir. Ek bellek kullanımı array versiyonuyla nasıl karşılaştırılıyor?

★★★ Dictionary<string, DoublyNode<(string Key, Book Value)>> ve DoublyLinkedList ile kapasitesi sınırlı bir LruCache yaz: Get erişilen kaydı başa taşısın, Set kapasite dolunca en sondakini atsın. Her iki işlemin O(1) olduğunu gösteren bir benchmark ekle.

Linked list ve array, bir sonraki yazının iki yapı taşı. Stack ve queue aslında birer ADT (Abstract Data Type): "son giren ilk çıkar" ve "ilk giren ilk çıkar" sözleşmeleri. Bir sonraki yazıda ikisini de array üzerinde implement ediyoruz, queue için circular buffer'ı ve son N log satırını tutan bounded ring buffer'ı yazıyoruz.