A összekapcsolt lista a számítástechnikában egy olyan adatstruktúrát jelöl, amely tetszőleges méretű, azonos típusú elemek tetszőleges méretű elrendezését mutatja, és amelyeknek a számítógépes memóriában való ábrázolása tartalomból és egy másik cellába mutató cellákból áll. Képes módon a sejtek halmaza úgy néz ki, mint egy lánc, amelynek összekapcsolódása a sejteké lenne.
A lista elemeihez való hozzáférés egymást követõen történik: minden elem hozzáférést biztosít a következõhöz (ellentétben azzal a táblával , amelyben a hozzáférés közvetlenül történik, az említett tábla minden cellájának címzésével).
A csatolt lista alapelve az, hogy minden elemnek az adatok mellett van egy mutatója egy elemre, amely szomszédos vele a listában. A felsorolás használatát gyakran a feldolgozás gyorsasága érdekében javasoljuk, amikor az elemek sorrendje fontos, és bármely elem beillesztése és törlése gyakoribb, mint a hozzáférés.
Valójában a lista elején vagy végén lévő beillesztések és a törlések állandó időben történnek, mert csak két írást igényelnek. Másrészt bármely elem eléréséhez meg kell böngészni a listát a kezdetektől a kiválasztott elem indexéig.
Eredeti neve NSS memória , láncolt listák alakultak ki az évek 1955-ös - 1956-os , a Allen Newell , (in) Cliff Shaw és Herbert Simon a RAND Corporation . Az összekapcsolt listák megkapják nyelvük (az) Information Processing Language (IPL) alapstruktúráját . Az IPL-t szerzői számos mesterséges intelligencia program , például Logic Theory Machine , General Problem Solver és sakkjáték fejlesztésére használták fel . Munkájuk a kapcsolt listák tették közzé IRE Transactions on Information Theory in 1956 és számos konferencián tartott időszakban 1957-es , hogy 1959-es . A kapcsolt listák mára híres ábrázolása, ahol a csomópontok nyilakkal összekötött blokkok, 1957 februárjában jelent meg a Logikai elméleti gép programozása című cikkben . Allen Newell és Herbert Simon kapott a Turing-díjat az 1975 az „alapvető hozzájárulását a mesterséges intelligencia, a pszichológia az emberi megértés és a manipuláció listák” .
A kapcsolt listáknak több típusa van, amelyeket főleg két attribútum jellemez:
Amint az a szemközti ábrán látható, két információ alkotja a linkelt lista minden elemét:
Mivel a listában csak egy elem van hegyezve, a hozzáférés csak egy út. A lista végét egy őrszem érték jelöli , itt NULL . Az őrszem csomópont használata is lehetséges, különösen a ciklikus listák esetében.
Kétszer linkelt listaA különbség az egyszerűen összekapcsolt listával az, hogy ezúttal egy mutatót adunk az előző (vagy előd) elemhez. A hozzáférés tehát bármilyen módon történhet: az utódtól az utódig, vagy az elődtől az elődig.
Ez a szerkezet drágább a memóriában (elemenként további mutató) és a frissítéshez szükséges utasítások számában: a beszúrás négy példányba kerül, míg egyszerűen összekapcsolt lista esetén kettőbe kerül.
Másrészt ez lehetővé teszi a beillesztés működtetését egy elem előtt vagy után anélkül, hogy szükségszerűen lenne mutatója a szomszédra, míg az egyszerűen összekapcsolt lista csak az elemhez képest egyetlen helyen engedélyezi a beillesztést.: Utódként vagy (kizárólag) elődként.
A kettősen összekapcsolt lista integritásának ellenőrzése a kettős láncolás ellenőrzésével is lehetséges.
Az őrszem csomópont használata kétszeresen összekapcsolt listákhoz használható, akár ciklikusak, akár nem, a végtelen bejárások és a memóriaelérési hibák elkerülése érdekében.
A ciklus az a tulajdonság, amely egy összekapcsolt listán belül ciklust (vagy zárt láncot) alkot. A lánc kezdetének vagy a lánc végének fogalma eltűnik.
Ciklikus (vagy körkörös) lista akkor jön létre, amikor az utolsó elem hivatkozik az első elemre (ha a lista kettős összekapcsolás, akkor az első elem hivatkozik az utolsóra is).
Az ilyen típusú listák használata óvintézkedéseket igényel a végtelen bejárások elkerülése érdekében, például egy tétel sikertelen keresése során.
Bizonyos számú primitív van meghatározva, amelyek teszt, olvasás vagy írás hozzáférési függvények, amelyek felsorolása lehetővé teszi a hatékony végrehajtást.
A lista manipulációs primitívekre nincs szabványosítás. Nevüket ezért informálisan jelzik. Itt található a leggyakrabban használt lista:
Itt látható sematikusan egy új f elem hozzáadása egy e elem után egy egyszerűen összekapcsolt listában. Az eljárás két szakaszban történik:
Itt van egy példa egy elem megvalósítására Pascal nyelven (egyszerűen összekapcsolva az egészek listáját):
type liste = ^jonction; jonction = record contenu: longint; suivant: liste; end;És egy másik példa a C-ben a kétszeresen összekapcsolt egészlista elemének megvalósítására:
struct liste { int donnee; struct liste * precedent; struct liste * suivant; };Ez a C ++ példa egy listás osztályt mutat be, mozgatható indexel, amely alapvető módon mozgatható (első és utolsó elem, következő és előző elem). Csak az elején beszúrás, a végén törlés és a módosítás megengedett. Először is, egy elemszerkezet, amely megegyezik az előző listaszerkezettel, de átnevezve, hogy elkerülje a listaosztályral való összetévesztést:
// Structure element struct element { int var; element * suivant; element * precedent; };Ezután a lista osztály, amely az indexet számít egyetlen mezőként. A példa egyszerűsítése érdekében az osztálynak nincs destruktora, és memóriaszivárgást okoz. Hasonlóképpen, a másolásért és áthelyezésért felelős kivitelezőket és hozzárendelési operátorokat helyes kóddal kell megírni. A konstruktortól eltérő összes tagfunkciót a következő szakaszokban részletezzük. Az osztályban le kell másolni őket.
// Classe liste, chargée d'accéder aux différents éléments class liste { public: liste() = default; bool est_vide() const { return index == nullptr; } private: element * index = nullptr; };A start tag funkció lehetővé teszi, hogy az indexet a lista első elemére tegye.
void debut() { if (est_vide()) return; while (index->precedent != nullptr) { index = index->precedent; } }A végtag funkció lehetővé teszi, hogy az indexet felsorolja a lista utolsó elemére.
void fin() { if (est_vide()) return; while (index->suivant != nullptr) { index = index->suivant; } }A tag függvény beszúrja a startot, hozzáad egy elemet a lista elejéhez, és az indexet erre az új elemre helyezi.
void insertion_debut(int var) { element * n = new element; debut(); n->precedent = nullptr; n->suivant = index; n->var = var; if (not est_vide()) index->precedent = n; index = n; }A tag függvény eltávolítja a végét, eltávolítja az utolsó elemet a listából, és az indexet a lista utolsó elemére helyezi.
void supprimer_fin() { assert(not est_vide()); fin(); index = index->precedent; delete index->suivant; index->suivant = nullptr; }A mozgó tag függvény az indexet a következő elemre helyezi, ha az argumentuma igaz, vagy az előző elemre, ha az argumentum hamis.
void deplacer(bool en_avant) { if (est_vide()) return; if (en_avant) { if (index->suivant == nullptr) return; index = index->suivant; } else { if (index->precedent == nullptr) return; index = index->precedent; } }Az olvasott tag függvény visszaadja az elem értékét.
int lire() const { if (est_vide()) return 0; return index->var; }A tag módosítása függvény módosítja az elem értékét.
void modifier(int var) { if (est_vide()) return; index->var = var; }