Share
Ce veți creaDouă dintre cele mai frecvent predate structuri de date din domeniul informaticii sunt lista singulară și lista dublă.
Când am fost învățați aceste structuri de date, am cerut colegilor noștri să facă analogii pentru a le conceptualiza. Ceea ce am auzit au fost câteva exemple, cum ar fi o listă cu alimente și un tren. Aceste analogii, după cum am aflat în cele din urmă, au fost inexacte. O listă de produse alimentare a fost mai asemănătoare cu o coadă; un tren a fost mai asemănător cu o matrice.
Pe măsură ce trece mai mult timp, am descoperit în cele din urmă o analogie care descria cu exactitate o listă cu un singur link și o listă dublu legată: o vânătoare de vânătoare. Dacă sunteți curioși de relația dintre o vânătoare de vânătoare și o listă legată, citiți mai jos răspunsul!
În domeniul informaticii, o listă cu un singur link este o structură de date care deține o secvență de noduri conectate. Fiecare nod, la rândul său, conține date și un pointer, care poate indica un alt nod.
Nodurile unei liste individuale sunt foarte asemănătoare cu pașii dintr-o vânătoare de măturători. Fiecare pas conține un mesaj (de ex. "Ați ajuns în Franța") și indicii la pasul următor (de ex., "Vizitați aceste coordonate latitudine și longitudine"). Când începem să realizăm succesiunea acestor pași individuali pentru a forma o secvență de pași, creăm o vânătoare de scafandru.
Acum, că avem un model conceptual al unei liste individuale, să explorăm operațiunile unei liste individuale.
Deoarece o listă cu un singur link conține noduri, care pot fi un constructor separat dintr-o listă cu un singur link, vom sublinia operațiunile ambelor constructori: Nodul și SinglyList.
Accentsconagua
date stochează o valoare.Următor → puncte către următorul nod din listă._lungime preia numărul de noduri dintr-o listă.cap atribuie un nod ca cap al unei liste.adaugă valoare) adaugă un nod la o listă.searchNodeAt (poziție) caută un nod în poziția n în lista noastră.îndepărtați (poziție) elimină un nod dintr-o listă.Pentru implementarea noastră vom defini mai întâi un constructor numit Nodul și apoi un constructor numit SinglyList.
Fiecare instanță a Nodul are nevoie de capacitatea de stocare a datelor și de capacitatea de a indica un alt nod. Pentru a adăuga această funcție, vom crea două proprietăți: date și Următor →, respectiv.
funcția Nod (date) this.data = date; this.next = null;
Mai departe, trebuie să definim SinglyList:
funcția SinglyList () this._length = 0; this.head = null;
Fiecare instanță a SinglyList vor avea două proprietăți: _lungime și cap. Primului îi este atribuit numărul de noduri dintr-o listă; acesta din urmă indică capul listei - nodul din partea frontală a listei. De la fiecare nouă instanță SinglyList nu conține un nod, valoarea implicită de cap este nul și valoarea implicită de _lungime este 0.
Trebuie să definim metode care pot adăuga, căuta și elimina un nod dintr-o listă. Să începem cu adăugarea unui nod.
1 din 3: adaugă valoare)
Minunat, să implementăm acum funcționalitatea pentru a adăuga noduri la o listă.
SinglyList.prototype.add = funcție (valoare) var node = nou Nod (valoare), currentNode = this.head; // primul caz de utilizare: o listă goală dacă (! CurrentNode) this.head = node; this._length ++; nod retur; // al doilea caz de utilizare: o listă non-goală în timp ce (currentNode.next) currentNode = currentNode.next; currentNode.next = nod; this._length ++; nod retur; ;
Adăugarea unui nod în lista noastră implică mai mulți pași. Să începem de la începutul metodei noastre. Noi folosim argumentul lui adaugă valoare) pentru a crea o nouă instanță a Nodul, care este atribuită unei variabile numite nodul. De asemenea, declarăm o variabilă numită currentNode și inițializați-l la _cap din lista noastră. Dacă nu există noduri în listă, atunci valoarea cap este nul.
După acest punct din codul nostru, gestionăm două cazuri de utilizare.
Primul caz de utilizare ia în considerare adăugarea unui nod într-o listă goală. Dacă cap nu indică un nod, apoi atribuie nodul ca șef al listei noastre, să creștem lungimea listei noastre cu unul și să ne întoarcem nodul.
Cel de-al doilea caz de utilizare ia în considerare adăugarea unui nod într-o listă care nu este goală. Intrăm în in timp ce și în fiecare iterație, evaluăm dacă currentNode.next puncte către un alt nod. (În prima repetare, currentNode indică mereu capul unei liste.)
Dacă răspunsul este negativ, noi atribuim nodul la currentNode.next și întoarcere nodul.
Dacă răspunsul este da, intrăm în corpul lui in timp ce buclă. În interiorul corpului, noi realocăm currentNode la currentNode.next. Acest proces este repetat până la currentNode.next nu mai indică un alt nod. Cu alte cuvinte, currentNode indică ultimul nod al listei noastre.
in timp ce bucla pauze. În cele din urmă, le atribuim nodul la currentNode.next, noi creștem _lungime de unul, și apoi ne întoarcem nodul.
2 din 3: searchNodeAt (poziție)
Acum putem adăuga noduri în lista noastră, dar nu putem căuta noduri la anumite poziții din lista noastră. Să adăugăm această funcție și să creați o metodă numită searchNodeAt (poziție), care acceptă un argument numit poziţie. Argumentul este de așteptat să fie un întreg care indică un nod la n-poziția din lista noastră.
SinglyList.prototype.searchNodeAt = funcție (poziție) var currentNode = this.head, length = this._length, count = 1, message = eșec: 'Eșec: nod inexistent din această listă.'; // primul caz de utilizare: o poziție nevalidă dacă (lungime === 0 || poziție < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: o poziție validă în timp ce (număr < position) currentNode = currentNode.next; count++; return currentNode; ;
dacă instrucțiuni de verificare pentru primul caz de utilizare: o poziție nevalidă este trecută ca argument.
Dacă indicele a trecut searchNodeAt (poziție) este valabil, atunci ajungem la cel de-al doilea caz de utilizare - in timp ce buclă. În timpul fiecarei iterații a in timp ce buclă, currentNode-care indică mai întâi cap-este reassigned la următorul nod din listă. Această iterație continuă până când numărul este egal cu poziția.
Când bucla se rupe în cele din urmă, currentNode este returnat.
3 din 3: îndepărtați (poziție)
Se numește metoda finală pe care o vom crea îndepărtați (poziție).
SinglyList.prototype.remove = funcția (poziția) var currentNode = this.head, length = this._length, count = 0, message = eșec: 'Eșec: nod inexistent în această listă', beforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // primul caz de utilizare: o poziție nevalidă dacă (poziția < 0 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: primul nod este eliminat dacă (position === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; returnează deletedNode; // 3rd use case: orice alt nod este eliminat în timp ce (count < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Implementarea noastră de îndepărtați (poziție) implică trei cazuri de utilizare:
cap a unei liste) este trecut ca argument.Primul și al doilea caz de utilizare sunt cele mai simple de manipulat. În ceea ce privește primul scenariu, dacă lista este goală sau este trecută o poziție inexistentă, o eroare este aruncată.
Cel de-al doilea caz de utilizare se ocupă de îndepărtarea primului nod din listă, care este de asemenea cap. În acest caz, apare următoarea logică:
cap este realocată currentNode.next.deletedNode arata spre currentNode. currentNode este realocată nul. _lungime din lista noastră de unul.deletedNode este returnat. Al treilea scenariu este cel mai greu de înțeles. Complexitatea provine din necesitatea urmăririi a două noduri în timpul fiecărei iterații a in timp ce buclă. În fiecare iterație a buclă, urmărim atât nodul, cât și nodul care urmează să fie șters și nodul care trebuie șters. Când bucla noastră ajunge în final la nodul din poziția pe care dorim să o eliminăm, bucla se termină.
În acest moment, avem referințe la trei noduri: beforeNodeToDelete, nodeToDelete, și deletedNode. Înainte de a șterge nodeToDelete, trebuie să atribuim valoarea lui Următor → la următoarea valoare din beforeNodeToDelete. Dacă scopul acestei etape pare neclar, reamintiți-vă că avem o listă de noduri conectate; doar eliminarea unui nod rupe legătura dintre primul nod al listei și ultimul nod al listei.
Apoi, alocăm deletedNode la nodeToDelete. Apoi am setat valoarea nodeToDelete la nul, decrementați lungimea listei cu una și întoarceți-o deletedNode.
Implementarea completă a listei noastre este prezentată aici:
funcția Nod (date) this.data = date; this.next = null; funcția SinglyList () this._length = 0; this.head = null; SinglyList.prototype.add = funcție (valoare) var node = nou Nod (valoare), currentNode = this.head; // primul caz de utilizare: o listă goală dacă (! CurrentNode) this.head = node; this._length ++; nod retur; // al doilea caz de utilizare: o listă non-goală în timp ce (currentNode.next) currentNode = currentNode.next; currentNode.next = nod; this._length ++; nod retur; ; SinglyList.prototype.searchNodeAt = funcție (poziție) var currentNode = this.head, length = this._length, count = 1, message = eșec: 'Eșec: nod inexistent din această listă.'; // primul caz de utilizare: o poziție nevalidă dacă (lungime === 0 || poziție < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: o poziție validă în timp ce (număr < position) currentNode = currentNode.next; count++; return currentNode; ; SinglyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: primul nod este eliminat dacă (position === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; returnează deletedNode; // 3rd use case: orice alt nod este eliminat în timp ce (count < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Awesome, implementarea noastră a unei liste singure legate este completă. Acum putem folosi o structură de date care adaugă, înlătură și caută noduri într-o listă care ocupă un spațiu necontins în memorie.
Cu toate acestea, în acest moment, toate operațiile noastre încep de la începutul unei liste și se execută până la sfârșitul unei liste. Cu alte cuvinte, acestea sunt unidirecționale.
Pot fi cazuri în care dorim ca operațiunile noastre să fie bidirecționale. Dacă ați considerat acest caz de utilizare, atunci tocmai ați descris o listă dublată.
O listă dublu legată ia toate funcționalitățile unei liste individuale și o extinde pentru o mișcare bidirecțională într-o listă. Putem traversa, cu alte cuvinte, o listă legată de la primul nod din listă la ultimul nod din listă; și putem traversa de la ultimul nod din listă la primul nod din listă.
În această secțiune, ne vom concentra în primul rând pe diferențele dintre o listă dublată și o listă singulară.
Lista noastră va include doi constructori: Nodul și DoublyList. Să le prezentăm operațiunile.
date stochează o valoare.Următor → puncte către următorul nod din listă.anterior puncte către nodul anterior din listă._lungime preia numărul de noduri dintr-o listă.cap atribuie un nod ca cap al unei liste.coadă atribuie un nod ca coada unei liste.adaugă valoare) adaugă un nod la o listă.searchNodeAt (poziție) caută un nod în poziția n în lista noastră.îndepărtați (poziție) elimină un nod dintr-o listă.Să scrie un cod!
Pentru implementarea noastră, vom crea un constructor numit Nodul:
funcție Nod (valoare) this.data = valoare; this.previous = null; this.next = null;
Pentru a crea mișcarea bidirecțională a unei liste dublu legate, avem nevoie de proprietăți care indică ambele direcții ale unei liste. Aceste proprietăți au fost numite anterior și Următor →.
Apoi, trebuie să punem în aplicare o DoublyList și adăugați trei proprietăți: _lungime, cap, și coadă. Spre deosebire de o singură listă, o listă dublu legată are o referință atât la începutul unei liste, cât și la sfârșitul unei liste. Deoarece fiecare instanță a DoublyList este instanțiată fără noduri, valorile implicite ale cap și coadă sunt setate la nul.
funcția DoublyList () this._length = 0; this.head = null; this.tail = null;
Vom explora acum următoarele metode: adaugă valoare), îndepărtați (poziție), și searchNodeAt (poziție). Toate aceste metode au fost utilizate pentru o listă individuală; totuși, ele trebuie rescrise pentru mișcări bidirecționale.
1 din 3: adaugă valoare)
DoublyList.prototype.add = funcție (valoare) var node = nou Nod (valoare); dacă (this.length) this.tail.next = nod; node.previous = this.tail; this.tail = nod; altceva this.head = nod; this.tail = nod; this._length ++; nod retur; ;
În această metodă, avem două scenarii. Mai întâi, dacă o listă este goală, atunci îi alocați cap și coadă nodul fiind adăugat. În al doilea rând, dacă lista conține noduri, găsiți coada listei și asignați-o tail.next nodul fiind adăugat; de asemenea, trebuie să configuram noua coadă pentru mișcarea bidirecțională. Trebuie să stabilim, cu alte cuvinte, tail.previous la coada originală.
2 din 3: searchNodeAt (poziție)
Implementarea sistemului searchNodeAt (poziție) este identic cu o listă cu un singur link. Dacă ați uitat să îl implementați, l-am inclus mai jos:
DoublyList.prototype.searchNodeAt = funcție (poziție) var currentNode = this.head, length = this._length, count = 1, message = eșec: 'Eșec: nod inexistent în această listă.'; // primul caz de utilizare: o poziție nevalidă dacă (lungime === 0 || poziție < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: o poziție validă în timp ce (număr < position) currentNode = currentNode.next; count++; return currentNode; ;
3 din 3: îndepărtați (poziție)
Această metodă va fi cea mai dificilă de înțeles. Voi afișa codul și apoi îl voi explica.
DoublyList.prototype.remove = funcția (poziția) var currentNode = this.head, length = this._length, count = 1, message = eșec: 'Eșec: nod inexistent în această listă', beforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // primul caz de utilizare: o poziție nevalidă dacă (lungime === 0 || poziție < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: primul nod este eliminat dacă (position === 1) this.head = currentNode.next; // al doilea caz de utilizare: există un al doilea nod dacă (! This.head) this.head.previous = null; // al doilea caz de utilizare: nu există un al doilea nod altceva this.tail = null; // al treilea caz de utilizare: ultimul nod este îndepărtat altceva dacă (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // al patrulea caz de utilizare: un nod de mijloc este eliminat altceva while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
îndepărtați (poziție) se ocupă de patru cazuri de utilizare:
îndepărtați (poziție) este inexistentă. În acest caz, aruncăm o eroare. îndepărtați (poziție) este primul nod (cap) a unei liste. În acest caz, vom aloca deletedNode la cap și apoi realocați cap la următorul nod din listă. În acest moment, trebuie să luăm în considerare dacă lista noastră are mai mult de un nod. Dacă răspunsul este nu, cap va fi alocat nul și vom intra în dacă o parte a noastră if-else afirmație. În corpul lui dacă, trebuie să stabilim și noi coadă la nul-cu alte cuvinte, revenim la starea inițială a unei liste goale dublu legate. Dacă eliminăm primul nod dintr-o listă și avem mai mult de un nod în lista noastră, intrăm altfel secțiunea noastră if-else afirmație. În acest caz, trebuie să setăm corect anterior proprietatea cap la nul-nu există noduri înaintea capului unei liste. îndepărtați (poziție) este coada unei liste. Primul, deletedNode este alocat coadă. Al doilea, coadă este realocată la nodul anterior coastei. În al treilea rând, noua coadă nu are nod după ea și are nevoie de valoarea sa Următor → pentru a fi setat la nul. in timp ce bucla o dată currentNode se îndreaptă spre nodul la poziția în care este transmis ca argument îndepărtați (poziție). În acest moment, realocăm valoarea beforeNodeToDelete.next la nod după nodeToDelete și, dimpotrivă, noi realocăm valoarea afterNodeToDelete.previous la nod înainte nodeToDelete. Cu alte cuvinte, eliminăm indicii la nodul îndepărtat și le realocăm nodurilor corecte. Apoi, alocăm deletedNode la nodeToDelete. În cele din urmă, le atribuim nodeToDelete la nul. În cele din urmă, reducem lungimea listei noastre și ne întoarcem deletedNode.
Iată întreaga implementare:
funcție Nod (valoare) this.data = valoare; this.previous = null; this.next = null; funcția DoublyList () this._length = 0; this.head = null; this.tail = null; DoublyList.prototype.add = funcție (valoare) var node = nou Nod (valoare); dacă (this.length) this.tail.next = nod; node.previous = this.tail; this.tail = nod; altceva this.head = nod; this.tail = nod; this._length ++; nod retur; ; DoublyList.prototype.searchNodeAt = funcție (poziție) var currentNode = this.head, length = this._length, count = 1, message = eșec: 'Eșec: nod inexistent în această listă.'; // primul caz de utilizare: o poziție nevalidă dacă (lungime === 0 || poziție < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: o poziție validă în timp ce (număr < position) currentNode = currentNode.next; count++; return currentNode; ; DoublyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > lungime) arunca o nouă eroare (message.failure); // al doilea caz de utilizare: primul nod este eliminat dacă (position === 1) this.head = currentNode.next; // al doilea caz de utilizare: există un al doilea nod dacă (! This.head) this.head.previous = null; // al doilea caz de utilizare: nu există un al doilea nod altceva this.tail = null; // al treilea caz de utilizare: ultimul nod este îndepărtat altceva dacă (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // al patrulea caz de utilizare: un nod de mijloc este eliminat altceva while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
Am acoperit o mulțime de informații în acest articol. Dacă oricare dintre acestea pare confuz, citiți-o din nou și experimentați codul. Când în cele din urmă are sens pentru tine, simți mândru. Tocmai ați descoperit misterele unei liste individuale și unei liste dublu legate. Puteți adăuga aceste structuri de date la centura de instrumente pentru codare!
