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

#19 "A láncolt lista nem azért láncolt lista, mert a következő vagy előző listaelem pozícióját pointerként tároljuk, hanem azért, mert a következő vagy előző listaelem [pozíciója] egyáltalán letárolásra kerül."

És ha letárolod a következő elem pozícióját, az micsoda? Egy referencia. A referencia pedig egy speciális pointer. Vagy ha így jobban tetszik, a pointer egy fajtája a refrenciáknak. Sokat nem számít, ami számít az az, hogy minden elem mutat a következő/előző/stb elemre a listában, ezen a szinten a pointer és a referencia egy kalap alá vehető.

"És ha letárolod a következő elem pozícióját, az micsoda? Egy referencia. A referencia pedig egy speciális pointer."

Hát, pointerből véleményem és tanulmányaim szerint nincs speciális.

A polémia lényege, hogy egy álítás szerint láncolt listát csak pointerekkel lehet megvalósítani. Ez a kijelentés implicit tartalmazza azt a vélelmet, hogy láncolt listát olyan nyelven nem lehet implementálni, amely nem ismeri a pointer adattipust.

Ezt a tévedést cáfoltam én azzal, hogy pointer helyett attól különböző, tehát, mondjuk integer adattipussal is lehet láncolt listát létrehozni.

Egyébként ez része a hivatalos felsőoktatási tananyagnak is. Csak mivel azon nyelvek, amelyek nem ismerik a pointer fogalmát, kiveszőben vannak, így nem kerül a téma fókuszba.

[link]

Arra mindenesetre jó a tömbös példa, hogy azok az érdeklődők is megismerhessék a láncolt lista lényegét, fontosságát, gyakorlati jelentőségét, akik a pointerekkel egyelőre még hadilábon állnak.

#24 "A polémia lényege, hogy egy álítás szerint láncolt listát csak pointerekkel lehet megvalósítani. Ez a kijelentés implicit tartalmazza azt a vélelmet, hogy láncolt listát olyan nyelven nem lehet implementálni, amely nem ismeri a pointer adattipust."

Egész pontosan:

- Egy ember említette, hogy pointerekkel ijesztgetik a hallgatókat ezért tűnik nehéznek a láncolt lista

- Egy ember emíltette, hogy jellemzően pointerekkel érdemes implementálni

- És egy ember kérdezte, hogy hogyan csinálsz láncolt listát pointerek nélkül

Állítást nem láttam, hogy nem tudsz pointerek nélkül láncolt listát készíteni, egészen amíg #16 elő nem állt, hogy "hát a Javaban nincs pointer, és láss csodát, lehet referenciákkal láncolt listát készíteni", mint aki a spanyol viaszt találta fel. Csakhogy a referencia és a pointer majdnem ugyanaz, működését tekintve a referencia ugyanazt csinálja, mint a pointer, csak jobban le van korlátozva. És a kalapom tenném rá, hogy aki korábban pointert említett, az általánosan hivatkozásra/mutatóra gondolt, amit teljesen mindegy, hogy egy konkrét nyelvben pointerrel, vagy referenciával valósítasz meg. Kellő abssztrakció felett ez egy érték, ami valaminek a címére mutat. Ilyen tekintetben a pointer és a referencia egy és ugyanaz. Ahogy az integer is ami egy tömb offset-jeit tárolja. Attól, hogy az adott nyelv kontextusában nem pointernek nevezzük, még effektíve ugyanazt a működést valósítja meg.

"Ezt a tévedést cáfoltam én azzal, hogy pointer helyett attól különböző, tehát, mondjuk integer adattipussal is lehet láncolt listát létrehozni."

Lényegtelen. A pointer is csak egy int érték alacsony szinten, a pointer léte csak annyit változtat, hogy egy memóriacímre mutat a tárolt értéke. Teljesen lényeg, hogy a konkrét implementációban mit használsz, pointert, referenciát, int értéket, memóriacímet, tömb indexet, vagy mást tárolsz. A lényeg, hogy mutatsz egy következő elemre valamilyen módon. Ezért is érzem azt, hogy aki a Java-s referenciás példáját írta, az nem igazán van tisztában azzal, hogy bordó helyett sötétvöröset írt, és azt hiszi feltalált egy új színt. Referencia vagy pointer, ebben a kontextusban egyenértékű a kettő.

A tömbös példa meg lehet, hogy tanulásnak jó, de azért szúrja a szemem, hogy a láncolt lista lényegi előnyét dobja ki az ablakon. Erre azért remélem felhívják a hallgatók figyelmét mikor mutogatják nekik.

"Állítást nem láttam, hogy nem tudsz pointerek nélkül láncolt listát készíteni"

Ez alább már pedig az. Te írtad:

"Szóval igen, a láncolt lista továbbra is pointereken alapszik, ezen nem nagyon tudsz változtatni."

"de azért szúrja a szemem, hogy a láncolt lista lényegi előnyét dobja ki az ablakon."

Nem annyira, mert sok esetben semmi szükség a pointeres megvalósításból eredő sebességi hozadékra.

Például egy szövegszerkesztő implementálásánál sincs érdemi hozadéka a pointernek. Ahol meg a pointer végképp nem is létezik, ott más út nincs is.

"hogy a konkrét implementációban mit használsz, pointert, referenciát, int értéket, memóriacímet, tömb indexet, vagy mást tárolsz. A lényeg, hogy mutatsz egy következő elemre valamilyen módon."

Na, ezt állítottam eddig én is.

"Ez alább már pedig az. Te írtad:"

És azt is írtam, hogy ebben a kontextusban a pointer, referencia, miegyéb egy és ugyanaz, nincs a jelen kontextusban releváns különbség. Tehát igen, amikor pointert mondok, azt értsd általánosan. A pointer mutatót jelent, és ez az a tulajdonság, ami releváns. Mutat valamire. Tehát pointer.

"Nem annyira, mert sok esetben semmi szükség a pointeres megvalósításból eredő sebességi hozadékra." Mit értesz sebességi hozadék alatt?

A pointer sokkal gyorsabb. Próbálj meg egy képet tükrözni. Meg fogod látni.

De egy szövegszerkesztőnél ez a gyorsaság nem hoz előnyt, mert senki nem képes olyan gyorsan szveget manipulálni, hogy azt ne szolgálná ki a sima, tömbös megvalósítás is.

Vagy egy RR ütemezőnél, ahol limitálva van a processzek száma mondjuk 4-ben, hát ott ugyan gyorsabb a pointer, de annyira kevéssel, hogy említést sem érdemel. Utóbbinál is érdemesebb a pointeres megvalósításban gondolkodni, de egy példa rá, hogy hozadékát nem nagyon látjuk majd.

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

A mezei tömbös szerkezet IS láncolt lista, csak nem pointerrel van megoldva a láncolás.

Nézd. Én eddig a láncolt lista pointeres és tömbös megvalósíthatóságáról beszéltem.

Fogalmam sincs, hogy te mit értesz "mezei tömbös szerkezeten" és azt sem tudom, hogy jön ez ide?