Láncolt lista - most akkor hol az igazság?

a 80-as játékos igazán kitartóan próbálja teljesíteni a lehetetlen küldetést :D

a láncolt lista közepébe is tudsz beszúrni elemeket

tömb esetén ilyenkor csúsztatni kell az elemeket

tömb esetén új elem beszúrásakor a teljes tartalmat újjonan foglalt tömbe kell átmásolni (az okos array több helyet foglal mint sükséges így ez kevesebbszer fordul elő)

tömbbe ba pakolt listával csak lábon lőtted magad

Igen, le is fárasztott rendesen a 80 %-os.

De neked sincs igazad. Ezt írod:

"tömb esetén új elem beszúrásakor a teljes tartalmat újjonan foglalt tömbe kell átmásolni"

1. Az gondolom tiszta, hogy láncolt listára olyan nyelvekben is szükség van, amelyek nem ismerik a pointert.

Tehát, nem az van, hogy valaki direkt tömbösen oldja meg a láncolt listát, hanem tömbösen kényszerül megoldani, mert a nyelv lehetőségei korlátosak.

2. Amit írsz, és amit idézek, az fölösleges, legalábbis láncolt listánál, mert a tömbös implementációnál elég a tömb végére illeszteni az új adatelemet (beszúrás), hiszen éppen ezért láncolt lista, ez a lényege, hogy a tömb elemeiből tetszőleges láncot képezhetünk. A listaelemek sorrendjét átrendezhetjük úgy, hogy azok pozíciója nem változik, csak az indexük mutat majd másik listaelemre.

Tegyük fel, hogy valaki ír egy regényt.

Azt nyilván számtalan helyen át és át fogja írni, bemásol, vagy töröl belőle sok helyen. Ekkor a sorokat láncolt listában eltárolva, ha mondjuk a szöveg közepére másol, akkor elég a tömb végére illeszteni az új sorokat, vagy sort, és az indexeket átírni.

Remélem így már megértetted, mi értelme van a tömbös variánsnak. Sőt, esetleg belátod azt is, hogy van értelme.

Példa (a sor elején álló index mutat a lista köv. elemére, tehát egy másik sorra (tömbindex szerint, alsó indexhatár itt 1, hogy könnyebb legyen értelmezni). beolvasáskor, a listaindexet (ez az első szám a sorok elején) követve a vers az eredeti, általunk is ismert állapotát tükrözi majd), hiába van "össze-vissza" letárolva. Az alábbi lista a fizikailag tárolt sorrend. :

2 : Este van, este van: kiki nyugalomba! (1)

6 : Feketén bólingat az eperfa lombja,(2)

4 : Mintha lába kelne valamennyi rögnek,(3)

5 : Lomha földi békák szanaszét görögnek,(4)

8 : Csapong a denevér az ereszt sodorván,(5)

7 : Zúg az éji bogár, nekimegy a falnak,(6)

3 : Nagyot koppan akkor, azután elhallgat.(7)

- : Rikoltoz a bagoly csonka, régi tornyán.(8)

Eredeti:

1. Este van, este van: kiki nyugalomba!

2. Feketén bólingat az eperfa lombja,

3. Zúg az éji bogár, nekimegy a falnak,

4. Nagyot koppan akkor, azután elhallgat.

5. Mintha lába kelne valamennyi rögnek,

6. Lomha földi békák szanaszét görögnek,

7. Csapong a denevér az ereszt sodorván,

8. Rikoltoz a bagoly csonka, régi tornyán.

"Igen, le is fárasztott rendesen a 80 %-os."

én azon csodálkozom hogy milyen jól bírja a hülyeségeidet

"De neked sincs igazad." mégis mér' ne lenne

"mégis mér' ne lenne"

Azért, mert hülyeségeket beszélsz. A láncolt lista lényegét meg fel sem fogtad. Erről árulkodik az is, ahogy te erről vélekedsz. (beszúrás, meg, hogy szerinted "tömb esetén ilyenkor csúsztatni kell az elemeket")

OMG..

Hát nem kell csúsztatni semmit.

A láncolt lista lényege, hogy a köv. (vagy az előző) rekordra (listaelemre) mutat az elem mellett egy pointer, vagy egy index, egy szám. Ezzel lehet ugyanis a listát láncolni. Ezáltal válik indiferenssé a listaelem helye. Ezért nem kell mozgani sem, ahogy te azt feltételezted, rosszul. A lista láncolatának megváltoztatásához elég a mutatót, vagy indexet átírni. Így lehet listát rendezni, vagy szűrni, például. És ehhez, a hagyományos rendezéstől eltérően, nem kell a rendezendő elemeket mozgatni. Ez akkor válik különösen jelentőssé, ha a rekordméret is és az elemszám is elég nagy, tehát a lista mozgatásos rendezése sok sok processzoridőbe telne.

De van olyan eset, amikor egyáltalán nem is szabad mozgatni a listaelemeket, azok számától totál függetlenül.

[1, 1, 2, 3, 5, 8]

szúrj be 0-át a 0. elem elé ;)

Tessék:

[1, 1, 2, 3, 5, 8]

  0  1   2   3   4   5

[1, 1, 2, 3, 5, 8, 0]

  1   2   3   4   5   6   0

🤦🤦🤦

[1, 1, 2, 3, 5, 8]

[0, 1, 1, 2, 3, 5, 8]

#35 "2. Amit írsz, és amit idézek, az fölösleges, legalábbis láncolt listánál, mert a tömbös implementációnál elég a tömb végére illeszteni az új adatelemet (beszúrás), hiszen éppen ezért láncolt lista, ez a lényege, hogy a tömb elemeiből tetszőleges láncot képezhetünk."

Na ez az, ami nem létezik. Egy tömb mérete alapvetően statikus, lefoglalsz x hosszú egybefüggő memóriaterületet, és ott van a tömböd. Emiatt nagyon gyors az indexelés, mivel a tömb elejét jelző memóriacímtől meghatározott offset-re találod a tömböd n-edik elemét. Namost, ha ezt a tömböt te bővíteni akarod (elölről, hátulról, középről, mindegy), akkor gondba vagy. A tömbnek ugyanis EGYBEFÜGGŐ memóriaterületen kell helyet foglalnia, és semmi garancia nincs arra, hogy az aktuális memóriaterület következő szegmense elérhető számára. Ilyenkor tehát az történik, hogy a megnövelt méretű tömböd reallokálja egy megfelelő méretű memóriaterületre, ez viszont azt jelenti, hogy a teljes tömböt újra létre kell hoznia az új memóriacímen. Megsúgom, Assembly-től C-ig pontosan ezt kell csinálnod manuálisan. Magasabb szintű nyelvekben elérhetőek különböző okos tömbszerkezetek, container osztályok (pl vector) amelyek egyrészt helyetted kezelik a memória újraallokálását, illetve optimalizálják az újraallokálások számát azzal, hogy a kelleténél nagyobb területet foglalnak le az esetleges bővítések miatt.

És ITT lép be a láncolt lista, ami mivel az elemek maguk hivatkoznak az előző/következő elemre, nem szorul efféle korlátozások közé, a lista elemei szanaszét helyezkedhetnek el a memóriában, ezzel sokat optimalizálva a beszúráson, hozzáfűzésen, illetve elemek eltávolításán, cserébe mivel csak iteratívan érhetőek el az egyes elemei, lassabb az indexelés művelete. És épp ezért SEMMI értelme nincs egy láncolt listát tömbbel emgvalósítani, mivel az egyetlen érdemi előnyét dobjuk ki az ablakon - a bővíthetőségét.

"És épp ezért SEMMI értelme nincs egy láncolt listát tömbbel emgvalósítani, mivel az egyetlen érdemi előnyét dobjuk ki az ablakon - a bővíthetőségét."

Fogd már fel, ember! Arról van/volt szó, hogy vannak nyelvek, amelyekben nem létezik más út. Ezért nincs értelme a kötözködésednek. Ráadásul, a bővíthetőség igénye esetleges, tehát ne akarj már kritériumokat szabni és ezekből általánosítani, csak azért, hogy igazad legyen.

Az meg vicc, hogy te a láncolt lista egyetlen érdemi előnyének nevezed a bővíthetőséget.

Bővíteni, már ha éppen igény mutatkozik rá, lehet egy túldimenzionált tömbbel is. Mi több, csak azzal lehet egyes nyelvekben, mert hát, dinamikus tömb sem létezik mindegyikben.

De van sok más gond is azzal, amit írsz, úgy hogy én majd ezekre holnap válaszolok. Mert most megyek -végre- aludni.