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

"Fogd már fel, ember! Arról van/volt szó, hogy vannak nyelvek, amelyekben nem létezik más út."

Te meg azt fogd fel, hogy ez nem kifogás, egy 45 éves nyelvvel való takarózás nem változtat azon, hogy a tömbösen megalkotott láncolt lista semmi érdemleges előnnyel nem kecsegtet.

A gond az, hogy az általad írtak, legalábbis amit kifejezésre juttattál, nem az igazságot, hanem a te elképzelésedet tükrözik, amely elképzelés, ha úgy tetszik, nézet, még csak nem is konstans.

A JAVA-ban pointerek programozói szinten (!) nincsenek. A referencia sem az. (gépi kód (v. byte kód) szinten meg csak az van, de mindenütt (!), nem csak a JAVA-ban. Erre irtam, hogy ebből a nézőpontból tök mindegy, mert ez a nyilatkozatod minden más nyelvre is igaz)

a láncolt lista java-s megvalósítása jellemzően egy 'ezeregyedik' osztály, amely tartalmazza a szükséges metódusokat, valamint a lista adatszerkezete

bizony nem egyéb, mint egy duplán indexált tömb. Tehát összességében, adatszerkezet szintjén nem több a BASIC-ben és más pointer-less nyelvekben elérhető megoldásnál.

Azt is írod, hogy tömbös megvalósításnál a tömb indexe sem más, mint pointer.

Nos, a pointer jellemzően egy 2 vagy 4 byte-os integer, amelynek hossza adott géphez igazodik. A pointer a memória legkisebb önállóan megcímezhető

egysége. Tehát egy 32 bites gépen 4 byte hosszú (valós módot most felejtsük el). Azonban a láncolt lista tömbös megvalósításánál lehetséges az indexelés akár byte-os adatokkal is, ami egészen biztos, hogy nem lehet pointer, hiszen csak 8 bit, a szükséges 32 helyett, de a feladatát mégis ellátja. Tehát ez a definíciód is hibásnak bizonyult.

Nézzük a sebességet, tömbös vs pointeres megvalósítás esetén:

Azt állítottad, hogy a tömbös az gyorsabb lesz a pointeresnél mert a tömb szekvenciális, stb.. Hát nézzük:

Ha a rekordméret mondjuk 136 byte, akkor az n-edik rekordot úgy fogja elérni a gép, hogy fogja magát és kiszámolja a címet. Ehhez kell ugye a tömb kezdőcíme, a rekordméret és a pozíció (n). Ha mondjuk 15 rekordot akarok kiolvasni a tömbből, akkor ez 15 * n-edik cím kiszámítását jelenti, viszont ha pointeres a megvalósítás, akkor direktben arra a címre jump-ol a gép ahova kell és olvas. Képzeld el a különbséget egy nem több, mint ezer elemű listánál, ahol a 15-ször n random bármi lehet 0 és 999 között.

Nem létezik, hogy nem látod, be, melyik a gyorsabb út.

A tömb beolvasás csak akkor gyorsabb, ha szekvenciálisan olvassa a gép végig az egészet lépésről lépésre, és a cím csak simán inkrementálva van adott értékkel (a rekordhosszal). Persze az a legjobb, ha a rekord hossza mindjárt azonos a gépi szóval, mert azzal tud a gép a leggyorsabban műveletet végezni. Minden más lassabb, bizony még a rövidebb rekordhossz is!

De a láncolt listánál ez persze nem lehetséges, mert azt ugye jellemzően nem szekvenciálisan, hanem meghatározott sorrendben, jobbára ide-oda ugorva (és címszámítva) kell olvasni, akkor meg mindjárt jön a sebességvesztés.

Ezért is van olyan compiler, amely megengedi, hogy a tömb szóhatárra (16,32,64), esetleg mindjárt szegmenshatárra (4k) legyen igazítva. Mert ezzel, bár memória-helyet veszít, sok gépidőt nyerhet, hiszen kíméli a címaritmetikát (csak eltolás kell).

A 45 éves nyelvvel való érvelésed sem helytálló, mert az nem úgy van, hogy te kitalálsz egy szabályt a programnyelvek halmazára, majd amire nem illik az kiveted a halmazból. Ugyanis ez a szabályod, definíciód attól még nem lesz univerzális.

A BASIC és a JAVA mellett, a jelenleg használt mintegy ezer nyelvben találni még egy párat, amely nem ismeri a pointereket. Az meg nyilván nem játszik, hogy te akkor megtiltod másoknak ezen nyelvek használatát, csak, hogy a definíciód megállja a helyét. A lényeg azért ne sikkadjon el:

Azon vitatkozni, hogy melyik út a jobb, csak a feladat ismeretében érdemes, ugyanis mindkét megoldásnak vannak

tulajdonságai, amelyek adott feladat ismeretének tükrében lesznek pozitívumok, vagy negatívumok.

"A listákat lehet tömbösen is ábrázolni, ahol a rákövetkező elemhez nem egy pointer, hanem egy index érték vezet. A megvalósítás tömbös eszközéhez folyamodunk például egy olyan programnyelv esetén, amely nem tartalmaz pointer nyelvi elemet."

forrás: [link]

"6.6. Listák tömbös ábrázolása

A lista típus természetes megvalósítása pointerek alkalmazásával történik. A pointerek valójában memóriacímeket tartalmaznak, amelyeket a számítógépes végrehajtás elfed előlünk. A lista tömbös ábrázolása esetén magunk kezeljük az elemek közötti rákövetkezést biztosító indexeket.

A 6.7. ábra egy olyan tömbös lista-ábrázolást mutat, amelyben a tömb szabad helyei is láncolt kapcsolatban állnak.

A kétdimenziós tömbben elhelyezett lista ugyanaz, amely a 6.1. és 6.2. ábrákon is szerepel. Az l=4 indexérték a lista első elemére mutat, az sz=2 érték pedig a szabad helyek listájának kezdő indexe. Ebben az ábrázolásban a két lista terjedelme együttesen teszi ki a tömb helyfoglalását. Mindkét lista a másik „rovására” terjeszkedik. Ha a listába új elemet szúrunk be, akkor az a szabad helyek listájából láncoljuk ki és töltjük ki a megfelelő tartalommal. Ha törlünk egy elemet a listából, akkor azt a szabad helyek közé láncoljuk be.

A szabad helyek listájába célszerű első elemként beszúrni a törléskor felszabaduló elemet és megfordítva: beszúrás esetén legjobb az első szabad elemet kiláncolni, és azt a lista megfelelő helyére átfűzni. Ebben a működésben az adattartalmak a helyükön maradnak a tömbben. Az adatszerkezet dinamizmusát, az egyes tömbelemek „közlekedését” a két lista között az indexek értékeinek megfelelő beállításával valósítjuk meg."

Forrás mint fentebb. Szöveg a linkelt lap alján.

# 49:

Siralmasan gyenge vagy, tanulgass inkább. Véleményezni majd akkor állj le, ha lesz is rá alapod.

Itt egy kis bemelegítő:

"Mivel a pointermûveletek gyorsabbak az indexeléseknél - ez utóbbiak gépi szinten szorzást is igényelnek - a fenti függvényt a gyakorlatban a következõképpen írnánk meg: "

[link]

"Demonstrating the Linked List Implementation using Array"

[link]

Talán ez is segíti a fejlődésedet:

"Bármely adatszerkezet esetében alkalmazható a folytonos és a szétszórt tárolás is, de vannak, amelyekhez célszerűbb az egyik, míg másokhoz a másik tárolási mód alkalmazása. Például a tömbök tárolása a programozási nyelvekben általában a folytonos a memóriában.

(Az egyes elemek tárbeli címének meghatározására szolgál az ún. címaritmetika. Ha ismerjük az első elem címét a tárban, és tudjuk, hogy az egyes elemek hány bájtot foglalnak, bármely elem memóriacíme könnyen meghatározható.)

Dinamikus adatszerkezetek esetében gyakori a szétszórt tárolás, hiszen a dinamikus adatszerkezetek elemszáma bármikor növelhető."

[link]

"... viszont ha pointeres a megvalósítás, akkor direktben arra a címre jump-ol a gép ahova kell és olvas."

Meséld már el nekem, hogyan fogsz egy 200 elemű lista 78. elemére azonnal ugrani. Egy 200 elemű tömb esetében ez nem probléma, megvan a tömb kezdetének címe, ismert a rekordméret, elemszám, kiszámolja, és eltolja. Egy láncolt listában először tudnod kéne a 79. elem memóriacímét, amit extra optimalizálások nélkül csak a 78. és a 80. elemen találsz meg, amiknek a 77, illetve 81. elem tartalmazza a memóriacímét, és így tovább. 78 hivatkozást kell feloldanod, mire megtalálod a 79. elemet. Még ha be is vezetünk optimalizációs lépéseket, gyorsítva az indexelést (ezzel lassítva a lista módosítását), akkor sem lesz olyan gyors, mint egy mezei tömb esetében, ahol konstans időben történik az indexelés. Nem létezik olyan, hogy konstans idejű indexelés láncolt listánál.