Láncolt listák

A láncolt lista a pointer-gondolkodás alapgyakorlata: megmutatja, hogyan kell biztonságosan újrahuzalozni egy struktúrát, hogyan kell node-okban és nem indexekben gondolkodni, és hogyan marad stabil az invariáns szerkezeti módosítás közben.

---

1. Definíció

Mi az a láncolt lista?

A linked list egy lineáris adatstruktúra, amely node-okból épül fel. Minden node tárol egy értéket és egy hivatkozást egy másik node-ra. Singly linked list esetén a node a következő node-ra mutat; doubly linked list esetén előre és vissza is van link. A lényeg az, hogy az elemek nem egybefüggő memóriablokkban, indexek mentén helyezkednek el, mint a tömbben — a struktúrát a referenciák tartják össze.

Miért létezik?

A linked list azért hasznos, mert a lokális szerkezeti módosítások olcsók. Ha már ismered azt a node-ot, amely előtt vagy után módosítani akarsz, akkor a pointerek átállítása tipikusan O(1). Ez a fő trade-off: cserébe nem kapsz gyors index alapú elérést.

Hova illik a nagyobb képben?

A láncolt lista akkor kerül elő, amikor a feladat pointer update-ről, node beszúrásról vagy törlésről, megfordításról, lista szétvágásáról vagy összefűzéséről, cycle detectionről, vagy általában referencia-manipulációról szól. Interjún ez a téma ritkábban szól arról, hogy ténylegesen LinkedList-et kellene választanod productionben — sokkal inkább arról szól, hogy tudsz-e pontosan, információvesztés nélkül struktúrát módosítani.

Intuíció

Képzeld el úgy, mint vasúti kocsik láncát. Minden kocsi tudja, melyik a következő. Ha ki akarsz venni egy kocsit, nem kell az összes utána lévőt fizikailag balra tolni, mint egy tömbben — elég átállítani a kapcsolatot az előző és a következő között. Ezért olcsó a lokális szerkezeti módosítás. Ha viszont valaki a 17. kocsit kéri, végig kell menned az előzőkön. Ezért drága a random access.

Java kontextus

Java interjúfeladatokban a linked list szinte mindig saját ListNode osztállyal jelenik meg. A lényeg nem a JDK LinkedList API-ja — a lényeg az, hogy jól kezeled-e a referenciákat, a null eseteket és a szerkezeti invariánsokat. Egy minimális node így néz ki:

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
    }

    ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}

Miért nehéz sok embernek?

Nem azért, mert a linked list különösen elvont. Hanem azért, mert egyetlen rossz sorrendben végrehajtott pointer update elég ahhoz, hogy elveszítsd a lista maradékát. Ez a téma valójában fegyelmezett state-kezelés.

---

2. Alapfogalmak

2.1 Node-alapú felépítés

A linked list nem egy nagy objektum sorszámozott rekeszekkel, hanem node objektumok lánca. Egy node jellemzően tartalmaz egy payload értéket, egy vagy több linket, esetleg segéd metadata mezőket.

2.2 Singly vs doubly linked list

Interjúban a singly linked list a leggyakoribb.

2.3 Head és tail gondolkodás

A head az első node. Néha a tailt is külön nyilvántartod — a tail segít, ha sok append művelet van, de minden extra referencia új invariánst is jelent. Tipikus esetek: üres lista → head == null (esetleg tail == null); egyelemű lista → head == tail; több elemű lista → tail.next == null.

2.4 A bejárás szekvenciális

Ha a k-adik node-ot akarod elérni, k lépést kell sétálnod. Ez azt jelenti, hogy index alapú elérés O(n), érték szerinti keresés O(n), és sok megoldás traversal fázissal indul. Ez az egyik oka annak, hogy nyers scan jellegű feladatokban a linked list gyakran rosszabb, mint a tömb.

2.5 Beszúrás és törlés áthuzalozással

A linked list igazi ereje a pointer rewiring.

Ha prev a törlendő node előtti elemre mutat, akkor a törlés lényege:

prev.next = current.next;

Ha newNode-ot akarsz beszúrni prev után, a biztonságos sorrend:

newNode.next = prev.next;
prev.next = newNode;

A sorrend számít.

Ha túl korán írod felül prev.next értékét, elvesztheted a lista maradékát.

2.6 Dummy node minta

A dummy node egy mesterséges node a valódi head elé. Azért hasznos, mert leegyszerűsíti az edge case-eket: a valódi head törlése normál törléssé válik, az első elem elé beszúrás is normál esetté válik, és nem kell külön logika arra, hogy "ez most az első node-e?". Ez az egyik leghasznosabb linked list interjúminta.

2.7 Reversal gondolkodás

A megfordítás klasszikus feladat, mert információt kell megőrizned miközben újrahuzalozod a struktúrát. Az iteratív invariáns tipikusan ez: previous a már megfordított prefix, current a következő feldolgozandó node, nextNode ideiglenesen megőrzi a még feldolgozatlan maradékot. Ha nincs elmentve a nextNode, a lista további része eltűnhet az elérésből.

2.8 Fast és slow pointer

Két-pointeres linked list feladatoknál gyakori, hogy a slow pointer egyet, a fast pointer kettőt lép. Ez jó mintázat cycle detectionre, middle node keresésre, lista kettévágására és több palindrome-előkészítő feladatra.

2.9 Cycle detection

A standard megoldás Floyd tortoise-and-hare algoritmusa. Ha van ciklus, a gyors pointer utoléri a lassút. Ha a fast pointer eléri a null-t, akkor nincs ciklus. A szépsége az, hogy O(1) extra space-szel működik.

2.10 Komplexitási profil

2.11 A referencia-szemlélet fontos

Tömbnél a pozíció gyakran a fő identitás. Linked listnél maga a node referencia válik fontossá. Ez megváltoztatja a debugolás logikáját. Ahelyett, hogy azt mondanád, hogy "az i indexen vagyok", gyakran ezt mondod: "current a most feldolgozott node", "previous a már megoldott rész vége", vagy "slow a potenciális middle node-ra mutat".

2.12 Felismerési jelek

A linked list gondolkodás akkor kell, ha ilyesmit látsz:

• saját node osztály,
• next vagy prev linkek,
• reversal,
• remove the n-th node,
• detect a cycle,
• merge two sorted lists,
• reorder list,
• split list,
• vagy constant-space szerkezeti módosítás.

---

3. Gyakorlati használat

Mikor érdemes linked list szemléletben gondolkodni interjún?

Akkor, ha az input eleve node-alapú.

Tipikus jelek:

• "Given the head of a linked list..."
• "Reverse the list"
• "Remove duplicates from a sorted linked list"
• "Detect whether the list contains a cycle"
• "Merge two sorted linked lists"

Ilyenkor az index-alapú gondolkodás általában csak ront a megoldáson.

Tipikus linked list minták

Gyakori mintacsaládok:

• dummy node a head-biztos mutációhoz,
• fast/slow pointer middle és cycle feladatokhoz,
• iteratív reversal,
• rekurzív reversal,
• merge tail-builderrel,
• partition több ideiglenes listával,
• read-pointer / write-pointer stílusú rewiring.

Mikor rossz production választás a linked list?

Valódi Java alkalmazásokban sokszor a tömb vagy az ArrayList jobb.

Miért?

• jobb cache locality,
• kisebb objektum overhead,
• egyszerűbb API,
• jobb konstans faktorok.

Ezért interjúban a linked list gyakran inkább pointer-fegyelemről szól, mint container-választásról.

Mikor NEM jó a linked list szemlélet?

Nem jó, ha a feladatnak ez kell:

• random index elérés,
• binary search,
• primitíveken gyors scan,
• kulcs alapú lookup.

Ilyenkor a tömb, a hash struktúrák vagy a fák általában jobb illeszkedést adnak.

Java-specifikus tanács

Stack-szerű működéshez a legacy Stack helyett inkább Deque ajánlott.

Queue-szerű működéshez sokszor ArrayDeque a legjobb.

Viszont linked list interjúfeladatoknál szinte mindig explicit ListNode osztállyal dolgozz, mert a feladatmodell ezt várja.

Pair-programming nézőpont

Egy erős magyarázat így hangzik:

• "Dummy node-ot használok, így a head törlése normál esetté válik."
• "previous, current és nextNode változókat tartok, mert rossz sorrendben elveszne a lista maradéka."
• "Az invariáns az, hogy previous előtt a lista már helyesen meg van fordítva."

Ez sokkal erősebb, mint annyi, hogy "ismerem a linked list trükköt".

Kapcsolódó LeetCode feladatok

• LeetCode #206 — Reverse Linked List — három-pointeres megfordítás invariáns-fegyelemmel.
• LeetCode #21 — Merge Two Sorted Lists — dummy node + összehasonlító séta.
• LeetCode #141 — Linked List Cycle — fast/slow pointer ciklusdetektálás.
• LeetCode #19 — Remove Nth Node From End of List — two-pointer gap technika.
• LeetCode #876 — Middle of the Linked List — fast/slow a középpont megtalálásához.

---

4. Kódpéldák

Alap példa

Ez a példa felépít egy kis listát és kiírja.

public class LinkedListTraversalExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.value + (current.next != null ? " -> " : ""));
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        printList(head);
    }
}

Miért fontos?

• megmutatja a szekvenciális traversal-t,
• megmutatja a node-összekötést,
• és rögzíti, hogy linked listnél sétálsz, nem indexelsz.

Haladó példa

Ez a példa iteratívan megfordít egy singly linked listet.

public class ReverseLinkedListExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }

        return previous;
    }
}

Kulcs invariáns:

• previous a megfordított prefix,
• current a következő feldolgozandó node,
• nextNode megvédi a még nem feldolgozott maradékot.

Tipikus hiba

Ez egy klasszikus bug.

public class BrokenReverseExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode brokenReverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            current.next = previous;
            previous = current;
            current = current.next;
        }

        return previous;
    }
}

Miért rossz?

• a current.next = previous felülírja az eredeti következő node-ot,
• a current = current.next ezután már visszafelé indul,
• és a még feldolgozatlan suffix elveszik.

A javítás az, hogy még a felülírás előtt elmented a nextNode változót.

Még egy hasznos minta: törlés dummy node-dal

public class RemoveValueExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode removeAll(ListNode head, int target) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.value == target) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return dummy.next;
    }
}

Ez interjún különösen jó példa, mert eltünteti a head törlésének speciális esetét.

---

5. Trade-offok

Teljesítménybeli árnyalat

A Big-O önmagában kevés.

Lehet, hogy a beszúrás egy ismert node után O(1).

De ha előtte O(n) traversal kell, hogy odajuss, akkor a teljes művelet továbbra is lineáris jellegű.

Memóriabeli árnyalat

Minden node objektum overheadet jelent.

Ez az egyik fő oka annak, hogy valódi Java rendszerekben a linked list sokszor lassabb, mint amit az aszimptotikus történet sugall.

Olvashatósági árnyalat

A linked list kód akkor lesz olvasható, ha a változónevek az invariánst fejezik ki.

Az olyan nevek, mint previous, current, nextNode, slow, fast, dummy és tail nem díszítés.

A biztonság részei.

---

6. Gyakori hibák

1. Elveszíted a lista maradékát — A leggyakoribb bug, hogy felülírod current.next értékét mielőtt elmented az eredeti következő node-ot. Előbb ments, utána rewiring.
2. Nem kezeled a head edge case-et — Head törlésnél vagy head elé beszúrásnál könnyen szétesik a logika. Dummy node gyakran a legegyszerűbb megoldás.
3. Rosszul lépteted a pointert — Törlős ciklusokban egy rossz pointer advance node-okat ugorhat át.
4. Rosszat hasonlítasz — Néha node identitás kell, nem értékegyezés. Legyél tisztában vele, hogy referencia- vagy value-equality a kérdés.
5. Elfelejted a null boundary-t — fast.next.next csak akkor biztonságos, ha előtte bizonyítottad, hogy fast és fast.next sem null.
6. Tömbös intuícióval gondolkodsz — Nincs olcsó indexugrás. Ha a gondolatmenet középidexről beszél traversal nélkül, rossz a modell.
7. Eltöröd a tail invariánst — Ha tail pointert is tárolsz, append, delete és merge után is karban kell tartanod.

Debug tipp

Ha linked list bug van, négy dolgot rajzolj fel:

• a node értékeket,
• a nyilakat,
• a változóneveket,
• és a következő update-et.

Ez általában elég.

---

7. Mélyebb összefüggések

Miért veszít gyakran a linked list a tömb ellen, és miért szeretik mégis az interjúztatók?

Elméletben az O(1) insertion erősnek hangzik. A gyakorlatban viszont a tömb cache-barát, a primitív tömbök elkerülik az objektum overheadet, és az egybefüggő scan CPU-szinten nagyon gyors. A linked list sok kis heap objektumot hoz létre, a referencia-követés locality szempontból sokkal rosszabb — ezért az "aszimptotikusan jobb" struktúra productionben még lehet lassabb.

Mégis, az interjúztatók azért szeretik, mert három fontos készséget mutat meg: referencia-fegyelem, invariáns-alapú gondolkodás és edge case kontroll. Ha biztonságosan tudsz reverse, split, merge és cycle detection feladatokat megoldani, az általában azt jelzi, hogy jól kezeled az állapotátmeneteket.

Dummy node és fast/slow pointer mint algoritmikus gondolkodás

A dummy node valójában design pattern a speciális esetek eltüntetésére. A jó mérnöki gondolkodás sokszor arról szól, hogy úgy formálod át a problémát, hogy a fő ciklus egységes legyen.

A fast/slow pointer elegáns, mert a struktúrát mozgás segítségével teszi láthatóvá. Ha a fast kétszer olyan gyors, meeting esetén van ciklus; ha a fast eléri a végét, a slow a middle környékére jut; ha az egyik pointer később indul, a relatív mozgás kiegyenlíthet távolságokat. Ez algoritmikus gondolkodás, nem puszta bemagolás.

Rekurzió és pair-programming nézőpont

Sok feladatnak van elegáns rekurzív formája is, de a rekurzió call-stack extra space-t használ. Néha vállalható tisztaságért, máskor viszont gyengébb, mint az iteratív megoldás — interjún ezt mondd ki.

Egy "remove duplicates from sorted list" feladatnál az erős megoldás nem csak a kód, hanem az indoklás is: a lista rendezett, a duplikátumok szomszédosak, egy passz elég, a rewiring lokális, és a fő kockázat az, hogy törlés után node-okat ugorhatsz át. Ez a fajta magyarázat választja el a stabil jelöltet a pusztán gyors kódolótól.

---

8. Interjúkérdések

Q: Miért rossz a linked list random accessre? — A: Mert a node-okat egymás után kell bejárni. Nincs közvetlen index → cím ugrás, mint a tömbben, ezért a pozíció szerinti elérés O(n).

Q: Mikor valódi O(1) a beszúrás linked listben? — A: Akkor, ha már nálad van az a node, amely után vagy elé módosítani akarsz. Ha előtte traversal kell a pozíció megtalálására, a teljes művelet költsége ezt is tartalmazza.

Q: Miért ennyire hasznos a dummy node? — A: Mert eltünteti a head speciális esetét. A lista elején történő törlés vagy beszúrás is ugyanúgy kezelhető, mint a belső műveletek.

Q: Hogyan működik Floyd cycle detection? — A: A slow pointer egyet, a fast pointer kettőt lép. Ciklus esetén a gyors pointer utoléri a lassút. Ciklus nélkül a fast pointer eléri a null-t.

Q: Miért lehet gyorsabb productionben egy ArrayList, mint egy linked list, még ha a linked list beszúrása elméletben olcsóbb is? — A: Mert a tömbszerű struktúrák jobb localityt és kisebb objektum overheadet adnak. A valódi teljesítmény nem csak Big-O kérdés.

---

9. Fogalomtár

---

10. Cheatsheet

• Linked listnél node-okban gondolkodj, ne indexekben.
• Mentsd el a nextNode-ot mielőtt felülírod current.next-et.
• Használj dummy node-ot, ha a head változhat.
• A slow/fast pointer a standard eszköz middle és cycle feladatokra.
• Index szerinti elérés O(n), nem O(1).
• A lokális rewiring lehet O(1), ha már megvan a megfelelő node.
• Valódi Java teljesítményben a tömb gyakran veri a linked listet a locality miatt.
• A jó linked list kód a változónevekkel is az invariánst kommunikálja.
• Ha túl sok a speciális eset, dummy node vagy tail-builder segíthet.
• Interjún előbb mondd ki a pointer update sorrendjét, és csak utána írd le.