A láncolt listákat, hogyan tanuljam meg?

Ez egy elég hülye példa de képzeld azt, hogy a szobádban valaki elrejtette a cuccaid egy részét és úgy rejtette el, hogy minden cuccod mellé mellékelte, hogy hol találod a következőt (pl. íróasztal bal fiók). Az elrejtett cuccok és útmutatók együtt a láncolt listád. Az a valaki megmondja neked, hogy hol találod az első elrejtett cuccot(a többiről egyelőre nem tudsz), te odamész megnézed(esetleg csinálsz vele valamit), majd veszed a hozzátartozó útmutatót és mész tovább a második cucchoz, ezt is megnézed majd veszed a hozzátartozó útmutatót és mész harmadikhoz és így tovább egészen addig, amíg olyan cuccot nem találsz, amihez nincs útmutató. Ekkor elértél a listád végére. Ez a legegyszerűbb egyirányú láncolt lista. Lehet kétirányú, ekkor az első és utolsó cuccot kivéve, mindegyikhez 2 útmutató van, az előző és a következő cucc(az elsőnél ugye nincs előző cucc, az utolsónál nincs következő cucc).

Egyébként rajzolgass papíron és ha már valamennyire kapizsgálod akkor próbáld meg leprogramozni valamilyen nyelven (úgy szerintem könnyeben meg lehet éretni).

Nagyon remélem, hogy nem te vagy az, aki minden másnap megkérdi ezt!

A lista tagokból áll. Minden tag tartalmaz egy adatot, és egy linket a következő adatra. Az adatok pedig láncszerűek, a harmadik elem nem tudja az ötödik elem linkjét, se a hatodikét, CSAK a negyedikét. Ha egy kiesik, BOOM, volt-nincs lista. Ennyi! (legalábbis a klasszikus láncolt-lista)

G.

"BOOM, volt-nincs lista"

Ez mit jelent? Szerintem a "klasszikus" láncolt listán is értelmezve van a töröl művelet, ami ugye a elem törlésén kívül a referenciákat is karbantartja...

Sajnos ha gyakorlatban nem tudod megcsinálni, akkor az azt jelenti, hogy elméletben sem érted.

A lista csomópontokból áll, semmi másból. A csomópont 2 dologból áll: egy tetszőleges elem (szám, kiskutya, nagymacska stb.) és egy referencia a következő csomópontra. A fej a listád első csomópontja, ez kitüntett szerepű, hiszen ha ezt nem ismered nem tudod bejárni a listát. A vége pedig az utolsó csomópont, ennek annyi a jelentősége, hogy a refernciája null (ezt egyelőre képzeld úgy, hogy nincs referencia) és ekkor tudod, hogy a listád végére értél. Mondok még egy gyakorlati példát: van 10 dobozod, ezeket felszámozod 1-10-ig. Veszel egy tetszőleges dobozt (nem feltétlenül az 1-t), beleraksz egy kiskutyát és mondjuk beraksz mellé egy üres papírt. Ez dobozod reprezentál egy csomópontot, méghozzá a kitüntett szerepű fejet (a kiskutya az elem, a papír a referencia). Ezután veszel egy másik dobozt és beleraksz egy nagymacskát és egy üres papírt mellé, ez a doboz lesz a második csomópontod, viszont hogy ebből lista legyen az első doboz papírjára felírod a második doboz számát. Ekkor már van egy 2 csomópontú listád, veszel újra egy dobozt belepakolsz, és a 2 doboz üred papírjára felírod a számát. Az a doboz aminek a papírja üres marad, lesz a listád utolsó eleme.

Ennél jobban nem tudom elmagyarázni.

A listának nincs "farka".

Fejnek sem kell lennie feltétlenül.

Már linkeltem erről egy leírást, de megteszem újra: [link]

Többféle láncolt lista van.

Az egyik verziója az, amit itt írnak páran a fejelemes, ahol az első egy spec. elem. (Ennek van haszna, de most ezt nem részletezem.)

A használata nem nehéz.

Először is létrehozol egy elemet és ráállítod a lista mutatóját.

Ezzel kész is az első elem.

Ha további elemeket akarsz, akkor létrehozol egyet, majd szépen a lista mutatótól végiglépkedsz a listán amíg az egyik elem next-je nem lesz üres. (Null poninter.)

Ha ez megvan, akkor ezt a mutatót ráállítod a most létrehozott elemre és kész.

Máris van egy új elem a listán.

Egy elem úgy néz ki, hogy tárol egy értéket és egy "next" pontert.

Az elem létrehozásakor ez null pointer, viszont mint írtam, ha utána csatolsz egy elemet, akkor ez megkapja a rákövetkező címét.

Tehát újra, röviden lépésenként mondjuk csináljunk 3 elemet:

1. csinálsz egy mutatót, ami a list mutató lesz. (Egy sima egyszerű pointer, ez mutat a lista első elemére.)

2. csinálsz egy elemet és ráállítod a lista mutatót. (Ugye már is akkor van egy 1 elemes "lánc".)

3. létrehozol egy újabb elemet, majd a lánc végére fűzöd úgy, ahogy már írtam. (Végig mész a láncon a lista mutatótól addig, amíg a next nem lesz üres értékű, majd az új elem címét beteszed ide.)

4. létrehozod a harmadik elemet, majd szintén befűzöd a lánc végére.

...

Ezt lehet folytatni a végtelenségig.

Gyorsítható a dolog, ha tárolsz egy utolsó elemre mutató pointert is, így nem kell bejárni a teljes listát, de ebben az esetben a befűzés után ennek is frissíteni kell az értékét.

[link]

Itt a "3) Láncolt adatszerkezetek megvalósítása"-nál találsz példát. Böngészd át mindegyiket, és próbáld elképzelni a "dobozokat".

Ennél jobbat nem tudok mutatni, ha ezekből nem érted meg rövidesen és abból, amit a többiek leírtak, sajnos nem hiszem, hogy neked való.

Sok sikert!