ehhez a gyakorlathoz egy egyszeresen Linkelt lista egyszerű változatát valósítjuk meg. De először nézzük meg, mi a Linkelt lista, és miért kell törődnie.
Linkelt lista a gyors és memória hatékony beillesztésekhez és törlésekhez használt adatszerkezet. A tömböktől eltérően, amelyek egyetlen objektumok, a csatolt listák több ‘csomópont’ objektumot tartalmaznak, amelyek hivatkozásokon keresztül kapcsolódnak egymáshoz.
a kapcsolt listák egyenként vagy kétszeresen is összekapcsolhatók. Most az egyenként összekapcsolt listákra összpontosítunk.
Singly Linked List
ha a linkelt listák több objektum összekapcsolása, ideális esetben szükségünk van egy pár különböző objektumra.
-
LinkedList objektum, amely a lista összes objektumát tartalmazza
-
a csomópont objektum, amely tartalmazza az adatokat az elem, valamint a hivatkozás a következő csomópont a listában.
várj, miért nem használ tömbök helyett?
alacsonyabb szintű nyelvekben a tömbök blokkokban vannak allocatd. Ezért a tömbök statikus méretűek, és csak egy adott adattípust tudnak tárolni. A csatolt listák adatokat tárolnak a kupacban, ami azt jelenti, hogy az adatok nem szervezett módon tárolhatók. Mivel minden csomópont a következőre mutat, továbbra is lehetséges a listaszerkezet fenntartása.
első lépések
a legjobb módja annak, hogy megértsük, hogyan kapcsolódik listák munka, hogy egy! Tegyük ezt Ruby – ban. Itt van a folyamat.
-
Kezdje egy
Nodeosztály létrehozásával. Lesznek attribútumaink az adatok ábrázolására (hívjuk ezt@data– nek) és a következő csomópontra való hivatkozásra (hívjuk ezt@next– nak). -
hozzon létre egy
LinkedListosztályt. Ennek az osztálynak két értéke lesz:@headés@tail. Ezek jelentik a lista elejét és végét. Inicializálja mindkettőtnil– re. Van egy üres listánk! -
most a két osztály összekapcsolására. Hozzon létre egy módszert a
LinkedListosztályban, amelynek neveinsert_front. A kihívás egy elem hozzáadása a lista elejéhez. Ezt egy újNodelétrehozásával lehet megtenni, majd a következőket kell tennie: -
tárolja a
@headértéket egy temp változóba -
állítsa a
@headértéket az újonnan létrehozottNodeértékre. Vegye figyelembe, hogy jelenlegnexthivatkozásanil. -
gondoljon arra, hogy mit kellene tennünk, ha új elemet adunk hozzá a csatolt lista elejéhez. Tekintse meg a diagramot (tipp: tennünk kell valamit az új csomópont
nextreferenciájával) -
végül kezelje a
@tailspeciális esetét. A@tailmindig az utolsóNodelegyen a linkelt listában. -
hozzon létre egy másik módszert a
LinkedListvagyNodenévento_sa lista kinyomtatásához a konzolra.
a linkelt listák felett történő iterálás
a while loops használatával a linkelt listák felett iterálhat. Míg a hurkok jobbak, mint a hurkok itt, mert a csatolt listák nem rendelkeznek hossz tulajdonsággal. A for bizonyos számú iteráció helyett egyszerűen a while iteráció helyett a current mutatónk nem nil.
hozzon létre egy current nevű helyi változót, amely a lista gyökércsomópontjára mutat. A hurok belsejében két dolgot tehet:
-
nyissa meg az aktuális csomópont értékét
current.data -
mutasson az aktuális változóra a következő elemre
current = current.next
bónusz: hozzon létre egy insert_end módszert csomópontok hozzáadásához a lista végéhez.
SUPER BONUS: hozzon létre egy sokoldalúbb insert módszert egy csomópont hozzáadásához bárhol a csatolt listában, amely indexet biztosít az új elemhez.