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

Az a baj veled, hogy féligazságokra, vagy avitt, ma már csak részben érvényes információkra támaszkodva érvelsz.

A láncolt listának egyik jellemzője, hogy bármely eleméig csak a lista bejárásával juthaszt el. Tehát a fejelem és az utána következők - a láncolat miatt - nem kerülhetők meg.

Tehát, ahhoz, hogy érdemi eredményre jussunk, azt kellene megtudnom, hogy mit akarsz? Mert az eredeti vita a láncolt listákról szólt, nem a tömbökről. És nem a tömbök előnyeiről a láncolt listákkal összehasonlítva. Mivel ez eleve értelmetlen volna.

Ezt írod:

" 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."

A tömböt most felejtsd el. Láncolt listáról van szó, akár tömbös akár pointeres megvalósításról beszélünk.

Mindkettőt be kell járni n-edik elemig, ha n-edik elemet el akarjuk érni.

Azonban a tömb esetében lassít a címaritmetika, mert ki kell számolni az elemek címét, hogy eljussunk az n-edikig.

A pointeres megvalósításnál ezt nem kell megtennünk, elég csak lépkedni pointercímtől pointercímig, amíg n-ig el nem jutunk.

A lépések száma mindkét esetben ugyanannyi, csak hát, a lépések költsége különböző, a pointeres megvalósítás javára (ez a gyorsabb). Fentebb írtak (címaritmetika) okán.

#53 Te most szórakozol? Te voltál az, aki idefurakodott a tömbösen megalkotott láncolt listával, és most te próbálsz érvelni ellene? Felfrissítem a memóriádat, okés?

- Bedobtad a tömbösen létrehozott láncolt listát

- Megjegyeztem, hogy nincs sok értelme, mert elveszi a láncolt lista egyik fő erényét, a bővíthetőségét

- Ekkor elkezdtél arról papolni, hogy nem, mert tömbös változatban tudsz úgy elemet hozzáadni, hogy a tömböt csak kiegészíted a végén, és az indextömbben felveszed a megfelelő indexre az új elemet.

- Ezután elmagyaráztam neked, hogyan is működik a tömb, és miért rettentő költséges a bővítése, és megemlítettem, hogy a tömbös szerkezet előnye a láncolt listával szemben a gyors indexelhetősége, amit a tömbös láncolt lista újfent nem élvez. (itt hívnám fel a figyelmet, hogy a 'tömb' és 'láncolt lista' kifejezéseket használtam, és NEM 'tömbös láncolt lista' és 'pointeres láncolt lista'. A pointer szó konkrétan nem is szerepelt a kommentben).

- Erre te elkezdtél érvelni, hogy de nem, mert a pointer gyorsabb mint a címaritmetika.

- És most megpróbálod bemagyarázni, hogy te nem is tömbökről beszélsz.

Az nem az én hibám, hogy neked nem megy a szövegértés, az ellenben nem érvelés logika, hogy kényed-kedved szerint próbálod csavarni hogy épp mi is a téma. Ott a téma, le van vezetve. Arra tessék válaszolni.

"és megemlítettem, hogy a tömbös szerkezet előnye a láncolt listával szemben a gyors indexelhetősége, amit a tömbös láncolt lista újfent nem élvez."

Már megbocsáss, de én abból vagyok kénytelen érteni, amit te írsz. Az pedig ez volt, idézlek:

"De én most egy mezei tömbös szerkezetről beszélek, nem a tömbösen megoldott láncolt listáról. SZóval mi az előnye a láncolt listának a tömbös szerkezettel szemben?"

egy másik:

"Szerinted mi a láncolt lista előnye egy mezei tömbös szerkezettel szemben?"

Továbbá:

"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,"

A tömb is egy adatszerkezet és a láncolt lista is.

A kettő egymástól eltér. Akkor is eltér, ha a láncolt lista tömbösen van implementálva, hiszen a tömbnél van index, lehet lépni közvetlenül a 78. elemre, a láncolt listánál nincs ilyen, mert nem is tudjuk, hogy a 78. elem hol helyezkedik el, a második az, avagy az utolsó.

Sajnos az a megállapításod is helytelen, hogy a dinamikus tömböket újra kellene allokálni. Nem kell. Már elég rég óta nem kell. Pláne a mai, sok szegmenses, eleve virtuális címtérben futó programok idejében.

De ki az a suta fejlesztő, aki ne dimenzionálna túl egy tömböt, ha egyszer tudja, hogy bővíteni fogja a user? Tehát reallokálni még ebben az esetben sem kell, hiába nincs hatalmas címtér, csak mondjuk valós mód a maga hülye memória és egyéb korlátaival (szegmens offset, stb.).

Az is látszik, hogy ez nem egy egyedi dolog, és nem kell hozzá BASIC vagy JAVA sem, mert rákerestem és találtam számos megoldást, weblapot, ahol tárgyalva lett ez a téma, implementálva is, klf nyelveken, C-ben is. Íme:

[link]

Végezetül, hidd el, vagy olvass utána ha nem hiszel nekem, de a pointer sokkal gyorsabb mint a tömb egy-egy rekordja, még akkor is gyorsabb, ha a tömböt szekvenciálisan olvasod.

Ennek oka abban áll, hogy a tömbelem olvasását megelőzi a címszámítás, az meg igényli az alábbiakat:

Tömb báziscíme,

elem vagy rekord mérete,

elérendő elem indexe.

Az indexet felszorozza a rekord mérettel, ezt követően a kapott értéket hozzáadja a báziscímhez. Így fogja megtudni hova megy kiolvasni.

A pointer viszont direktben szolgáltatja a címet.

Ezt a címszámítást - mint költséget - még tetézi az, hogy a szorzó sem fix, minden lépésnél változik egy láncolt lista esetében.

Ezért előny, ha a rekordhossz (sima tömb esetében) egyezik a gépi szóhosszal, mert akkor szekvenciális kiolvasásnál a báziscímet elég inkrementálni, ami elég gyors művelet a szorzáshoz képest.

a caching stratégiákat is vegyétek számításba!!!

heterogén kollekciókra gondoltatok?

"Azonban a tömb esetében lassít a címaritmetika, mert ki kell számolni az elemek címét, hogy eljussunk az n-edikig."

A címaritmetika az egyik legjobban optimalizálható, nagyon gyors műveletsor, amit csak egyszer kell elvégezni egy elem eléréséhez, és még hardveresen is támogatott (ld. indexelt címzés.) Ha minden egyes elemet fel kell dolgozni, akkor kezd érdekes lenni, de ha tömbcímzésnél a szükséges adatokat regiszterekben tudjuk tartani, akkor nem is biztos, hogy lassabb, mint a listaelem memória elérések. (A lista adott elemén belül a pointer helyét is ki kell számolni, mert nem biztos, hogy az elem, mint struktúra első mezője lesz. Főleg ha prev és next címek is vannak.)

"A tehetség könnyedén csinálja azt, amit mások nehéznek találnak.

A zseni könnyedén csinálja azt, amit mások lehetetlennek találnak."

Avagy az adott egyén képességeitől függ, hogy mennyire nehéz.

Szerintem elég sokan vannak akiknek nincs vagy nem volt lehetősége egyetemre menni, én ehhez mindenképpen pozitívan állnék hozzá.