Linkelt lista

A linkelt lista  egy alapvető dinamikus adatstruktúra a számítástechnikában, amely adatokat tartalmazó csomópontokból és a lista következő és/vagy előző csomópontjára mutató hivatkozásokból ("hivatkozásokból") áll. [1] A tömbhöz képest alapvető előnye a szerkezeti rugalmasság: a linkelt lista elemeinek sorrendje nem feltétlenül esik egybe a számítógép memóriájában lévő adatelemek sorrendjével [2] , és a lista bejárásának sorrendje mindig belső linkjei kifejezetten beállítják.

Hivatkozott listák típusai

Lineáris linkelt lista

Egyedül linkelt lista (egyedül linkelt lista)

A lineáris, egyszeresen irányított lista olyan adatstruktúra, amely azonos típusú elemekből áll, amelyek egymás után mutatókon keresztül kapcsolódnak egymáshoz. A lista minden eleméhez tartozik egy mutató a következő elemre. A lista utolsó eleme a NULL -ra mutat . A nem mutatott elem a lista első (fej) eleme. Itt az egyes csomópontokon lévő hivatkozások a lista következő csomópontjára mutatnak. Egyedül linkelt listában csak a lista vége felé lehet haladni. Az aktuális csomópont tartalma alapján nem lehet kideríteni az előző elem címét.

A számítástechnikában a lineáris listát általában absztrakt adattípusként (ADT) definiálják, amely formalizálja a rendezett adatgyűjtemény fogalmát . A gyakorlatban a lineáris listákat általában tömbök és linkelt listák segítségével valósítják meg. Néha a "lista" kifejezést informálisan is használják a "linked list" szinonimájaként. Például egy tipizálatlan mutálható ADT lista konstruktor és alapműveletek halmazaként definiálható :

  • Művelet, amely ellenőrzi, hogy egy lista üres-e.
  • Három művelet egy objektum hozzáadásához a listához (a lista elejére, végére vagy a lista bármely (n-edik) eleme után belülre);
  • Egy lista első (fej) elemét kiértékelő művelet;
  • Művelet az eredeti lista összes elemét tartalmazó lista eléréséhez, kivéve az elsőt.
Jellemzők
  • Lista hossza . A lista elemeinek száma.
  • A listák lehetnek gépelt vagy gépeletlenek . Ha egy listát gépelünk, akkor az elemeinek típusa adott, és minden elemének olyan típusúnak kell lennie, amely kompatibilis az adott típusú listaelemekkel. A legtöbb lista gépelt.
  • A lista lehet rendezett vagy rendezetlen .
  • A megvalósítástól függően véletlenszerű hozzáférés is lehetséges a lista elemeihez.
Egyedül linkelt lista programozási nyelveken

Xi

struktúra lista { int mező ; // adatmező struct lista * next ; // mutató a következő elemre };

egyedileg linkelt lista segítségével:

struct list * l1 = ( struct list * ) malloc ( sizeof ( struct list )); l1 -> mező = 1 ; l1 -> next = ( struct lista * ) malloc ( sizeof ( struct list )); l1 -> következő -> mező = 2 ; l1 -> next -> next = ( struct lista * ) malloc ( sizeof ( struct list )); /* stb. */ Duplán linkelt lista (duplán linkelt lista)

Itt az egyes csomópontokban lévő hivatkozások a lista előző és következő csomópontjára mutatnak. Az egyszeresen linkelt listához hasonlóan a duplán linkelt lista is csak egymás utáni hozzáférést tesz lehetővé az elemekhez, de lehetővé teszi mindkét irányú mozgást is. Ebben a listában egyszerűbb az elemek törlése és átrendezése, mivel a lista azon elemeinek címe, amelyek mutatói a módosítandó elemre mutatnak, könnyen elérhetők.

XOR linkelt lista

Ritkán használt.

Körlevél linkelt lista

A linkelt lista egyfajta gyűrűs (ciklikus, zárt) lista. Lehet egyszeres vagy dupla linkes is. A körlista utolsó eleme az elsőre, az első (kétszeresen linkelt lista esetén) pedig az utolsóra mutat mutatót.

Általában egy ilyen struktúra lineáris lista alapján valósul meg. Minden kör alakú lista emellett tárol egy mutatót az első elemre. Ebben a listában nincs hivatkozás a NULL-ra.

Vannak körkörös listák is, amelyekben külön fejelem található, hogy megkönnyítsék a teljes listát.

Lista kihagyása

Kibővített linkelt lista

Előnyök

  • hatékony (állandó időben) elemek hozzáadása és eltávolítása
  • a méretnek csak a számítógép memória mennyisége és a mutatók bitmélysége szab határt
  • elemek dinamikus hozzáadása és eltávolítása

Hátrányok

A linkelt listák hátrányai a fő tulajdonságukból – az adatokhoz való szekvenciális hozzáférésből – erednek:

  • az elemhez való közvetlen hozzáférés bonyolultsága, nevezetesen a fizikai cím meghatározása annak indexe (sorszáma) alapján a listában
  • a mutatómezők (a következő és előző elemre mutató mutatók) több memóriát fogyasztanak (például a tömbökben nincs szükség mutatókra)
  • egyes listákkal végzett műveletek lassabbak, mint a tömbökkel, mivel a lista egy tetszőleges eleme csak az azt megelőző összes elemen keresztül érhető el
  • a szomszédos listaelemek nem lokálisan foglalhatók le a memóriában, ami csökkenti az adatgyorsítótárazás hatékonyságát a processzorban
  • a tömbökhöz képest sokkal nehezebb (bár lehetséges) párhuzamos vektorműveleteket végrehajtani a csatolt listákon, mint például az összeg kiszámítása: az elemek feletti iteráció többletterhelése csökkenti a párhuzamosítás hatékonyságát.

Lásd még

Jegyzetek

  1. ↑ Cormen, Leiserson, Rivest és Stein. Bevezetés az algoritmusokba, 2. kiadás. The MIT Press, 2001. ISBN 0-262-03293-7
  2. ↑ Adatigazítás
 Adatstruktúrák
Listák
fák
Számít
Egyéb