LinkedList – kedjan som aldrig tappar bort sig

En LinkedList<T> är som en rad vänner som håller varandra i handen. Behöver du lägga till någon i mitten så släpper två personer taget och tar ett nytt grepp – smidigt! Behöver du flytta någon? Inga massiva array-kopior, bara nya handslag.

TL;DR

• LinkedList<T> består av noder som pekar på nästa – ibland även föregående – nod.
• Den är stark när du ofta lägger till eller tar bort element i mitten av listan.
• Slumptillgång (minLista[5]) är inte dess superkraft – använd listor om du måste indexera ofta.

Efter den här sidan kan du

• Förklara skillnaden mellan enkel- och dubbel-länkade listor.
• Använda C#-klassens LinkedList<T> för insertion och borttag i O(1).
• Skriva en enkel egen nodstruktur när du vill förstå vad som händer under huven.
• Veta när du ska välja LinkedList framför List<T> – och när du låter bli.

Hur den är uppbyggd

[HEAD] → [Data | Next] → [Data | Next] → … → [Data | null]

• Enkel-länkad lista (singly linked): Varje nod pekar bara framåt.
• Dubbel-länkad lista (doubly linked): Noden har både Next och Previous – vilket .NET:s LinkedList<T> använder.

Snabb tabell – vad kostar vad?

Exempel: dubbel-länkad lista i C#

.NET ger oss en färdig LinkedList<T>. Så här använder du den:

var todo = new LinkedList<string>();

todo.AddLast("Koka kaffe");
var codeNode = todo.AddLast("Skriva kod");
todo.AddLast("Pusha till GitHub");

// Lägg in något före "Skriva kod"
todo.AddBefore(codeNode, "Sätta på spellistan");

// Ta bort en nod direkt
todo.Remove(codeNode);

foreach (var task in todo)
{
    Console.WriteLine(task);
}

Lägg märke till att AddBefore och Remove jobbar med nodreferenser (LinkedListNode<T>) – det är där O(1)-magin händer.

Bygg en egen nod – för kunskaps skull

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

    public Node(T value)
    {
        Value = value;
    }
}

public class SinglyLinkedList<T>
{
    public Node<T>? Head { get; private set; }

    public void AddFirst(T value)
    {
        var node = new Node<T>(value)
        {
            Next = Head
        };
        Head = node;
    }

    public void RemoveFirst()
    {
        if (Head is null) return;
        Head = Head.Next;
    }
}

Egen implementation ger dig koll på pekare, garbage collection och varför referenser betyder något.

När ska du använda LinkedList?

✅ Perfekt när:

• Du bygger en undo-/redo-stack där du behöver flytta dig fram och tillbaka.
• Du hanterar en LRU-cache (Least Recently Used) – flytta senaste elementet till fronten.
• Du jobbar med köer där element ofta plockas från mitten (t.ex. spel-logik).

❌ Undvik när:

• Du behöver slumpmässig åtkomst ofta (myList[42]).
• Du jobbar med få förändringar men många läsningar – en vanlig List<T> är oftast snabbare och snålare med minnet.
• Du måste serialisera till JSON/XML (LinkedList blir mer verbos än en lista).

Vanliga misstag

• Tappa bort noder: Om du inte uppdaterar både Next och Previous (vid dubbel-länkning) så skapar du lätt “öar” av noder som aldrig nås.
• Ta bort under iteration: Använd alltid nodreferenser (current = current.Next) innan du kallar Remove på nuvarande nod.
• Gör LinkedList<T> till silverkula: Den är optimerad för jämna mutationer, inte för generisk vardagsförvaring.

Kombinera med andra strukturer

• Dictionary<K, LinkedListNode<T>> – klassisk uppsättning för en LRU-cache: O(1) för att hitta noden, O(1) för att flytta den.
• Queue + LinkedList – kör LinkedList för prioriterade insättningar, Queue för normal trafik.

Övningar

1. Grön: Implementera en metod MoveToFront(LinkedListNode<T>) som flyttar en nod till början av listan.
2. Gul: Bygg en playlist där du kan hoppa framåt/bakåt utan att tappa nuvarande nod (använd LinkedListNode<T>.Next/Previous).
3. Röd: Implementera en enkel LRU-cache med LinkedList<T> + Dictionary<K, LinkedListNode<T>>.

Sammanfattning

• LinkedList<T> är bäst när du ofta lägger till eller tar bort element mitt i listan.
• Den offrar indexbaserad åtkomst för snabba mutationer.
• Kombinationen med andra strukturer gör den till ett kraftfullt verktyg i din låda.

Dad joke

Varför blev noden uppsagd? Den tappade kontakten med sina kollegor och slutade peka åt rätt håll.