În 2009, m-am provocat să scriu o postare pe blog pe săptămână pe parcursul întregului an. Citisem că cel mai bun mod de a obține mai mult trafic pe un blog era să publici constant. O postare pe săptămână părea un obiectiv realist datorită tuturor ideilor de articole pe care le aveam, dar s-a dovedit că îmi lipseau cu mult 52 de idei. Am scotocit prin câteva capitole scrise pe jumătate din ceea ce avea să devină în cele din urmă Professional JavaScript și am găsit o mulțime de materiale pe teme clasice de informatică, inclusiv structuri de date și algoritmi. Am luat acel material și l-am transformat în mai multe postări în 2009 și (și câteva în 2012), și am primit o mulțime de feedback pozitiv în legătură cu ele.

Acum, la aniversarea de zece ani de la acele postări, am decis să le actualizez, să le republic și să le dezvolt folosind JavaScript în 2019. A fost interesant să văd ce s-a schimbat și ce nu s-a schimbat și sper să vă bucurați de ele.

Ce este o listă legată?

O listă legată este o structură de date care stochează mai multe valori într-un mod liniar. Fiecare valoare dintr-o listă legată este conținută în propriul său nod, un obiect care conține datele împreună cu o legătură către următorul nod din listă. Legătura este un pointer către un alt obiect nod sau null în cazul în care nu există un nod următor. În cazul în care fiecare nod are doar un singur pointer către un alt nod (cel mai frecvent numit next), atunci lista este considerată o listă cu o singură legătură (sau doar o listă legată), în timp ce dacă fiecare nod are două legături (de obicei previous și next), atunci este considerată o listă dublu legată. În această postare, mă concentrez pe listele legate simplu.

De ce să folosim o listă legată?

Beneficiul principal al listelor legate este că acestea pot conține un număr arbitrar de valori, utilizând în același timp doar cantitatea de memorie necesară pentru aceste valori. Păstrarea memoriei era foarte importantă pe calculatoarele mai vechi, unde memoria era limitată. La acea vreme, o matrice încorporată în C presupunea să specificați câte elemente poate conține matricea, iar programul rezerva acea cantitate de memorie. Rezervarea acelei memorii însemna că aceasta nu putea fi folosită pentru restul programului sau pentru orice alt program care rulează în același timp, chiar dacă memoria nu era niciodată umplută. Pe mașinile cu puțină memorie, puteți rămâne cu ușurință fără memorie disponibilă folosind array-uri. Listele legate au fost create pentru a rezolva această problemă.

Chiar dacă inițial au fost concepute pentru o mai bună gestionare a memoriei, listele legate au devenit, de asemenea, populare atunci când dezvoltatorii nu știau câte elemente va conține în cele din urmă o matrice. Era mult mai ușor să folosești o listă legată și să adaugi valori după cum era necesar decât să ghicești cu exactitate numărul maxim de valori pe care le-ar putea conține un array. Ca atare, listele legate sunt adesea folosite ca bază pentru structurile de date încorporate în diverse limbaje de programare.

Tipul încorporat în JavaScript Array nu este implementat ca o listă legată, deși dimensiunea sa este dinamică și este întotdeauna cea mai bună opțiune pentru început. S-ar putea să vă continuați întreaga carieră fără a fi nevoie să folosiți o listă legată în JavaScript, dar listele legate sunt totuși o modalitate bună de a învăța cum să vă creați propriile structuri de date.

Construcția unei liste legate

Cea mai importantă parte a unei liste legate este structura nodurilor sale. Fiecare nod trebuie să conțină anumite date și un pointer către următorul nod din listă. Iată o reprezentare simplă în JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

În clasa LinkedListNode, proprietatea data conține valoarea pe care trebuie să o stocheze elementul din lista legată, iar proprietatea next este un pointer către următorul element din listă. Proprietatea next începe ca null deoarece nu cunoașteți încă următorul nod. Puteți crea apoi o listă legată folosind clasa LinkedListNode astfel:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

Primul nod dintr-o listă legată se numește de obicei cap, astfel încât identificatorul head din acest exemplu reprezintă primul nod. Al doilea nod este creat și atribuit la head.next pentru a crea o listă cu două elemente. Se adaugă un al treilea nod prin atribuirea acestuia la head.next.next, care este pointerul next al celui de-al doilea nod din listă. Pointerul next al celui de-al treilea nod din listă rămâne null. Imaginea următoare prezintă structura de date rezultată.

Structura unei liste legate vă permite să parcurgeți toate datele urmărind pointerul next de pe fiecare nod. Iată un exemplu simplu de parcurgere a unei liste legate și de tipărire a fiecărei valori pe consolă:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Acest cod utilizează variabila current ca pointer care se deplasează prin lista legată. Variabila current este inițializată la capul listei, iar bucla while continuă până când current este null. În interiorul buclei, valoarea stocată în nodul current este tipărită și apoi pointerul next este urmărit până la nodul următor.

Majoritatea operațiilor cu liste legate utilizează acest algoritm de traversare sau ceva similar, astfel încât înțelegerea acestui algoritm este importantă pentru a înțelege listele legate în general.

Clasa LinkedList

Dacă ați scrie o listă înlănțuită în C, v-ați putea opri în acest punct și ați putea considera sarcina dvs. încheiată (deși ați folosi un struct în loc de o clasă pentru a reprezenta fiecare nod). Cu toate acestea, în limbajele orientate pe obiecte, cum ar fi JavaScript, este mai obișnuit să creați o clasă pentru a încapsula această funcționalitate. Iată un exemplu simplu:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

Clasa LinkedList reprezintă o listă legată și va conține metode de interacțiune cu datele pe care le conține. Singura proprietate este o proprietate simbol numită head care va conține un pointer la primul nod din listă. O proprietate simbol este utilizată în locul unei proprietăți de tip șir de caractere pentru a clarifica faptul că această proprietate nu este destinată a fi modificată în afara clasei.

Aducerea de date noi în listă

Aducerea unui element într-o listă legată necesită parcurgerea structurii pentru a găsi locația corectă, crearea unui nou nod și inserarea acestuia la locul său. Singurul caz special este atunci când lista este goală, caz în care se creează pur și simplu un nou nod și se atribuie la head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

Metoda add() acceptă un singur argument, orice bucată de date, și o adaugă la sfârșitul listei. Dacă lista este goală (this este null), atunci se atribuie this egal cu noul nod. Dacă lista nu este goală, atunci trebuie să parcurgeți lista deja existentă pentru a găsi ultimul nod. Traversarea are loc într-o buclă while care începe la this și urmărește legăturile next ale fiecărui nod până când se găsește ultimul nod. Ultimul nod are o proprietate next egală cu null, deci este important să se oprească parcurgerea în acel punct și nu atunci când current este null (ca în secțiunea anterioară). Puteți apoi să atribuiți noul nod acelei proprietăți next pentru a adăuga datele în listă.

Complexitatea metodei add() este O(n) deoarece trebuie să parcurgeți întreaga listă pentru a găsi locația în care să inserați un nou nod. Puteți reduce această complexitate la O(1) urmărind capătul listei (numit de obicei coadă) în plus față de cap, ceea ce vă permite să inserați imediat un nou nod în poziția corectă.

Retragerea datelor din listă

Listele legate nu permit accesul aleatoriu la conținutul său, dar puteți totuși să recuperați date în orice poziție dată prin parcurgerea listei și returnarea datelor. Pentru a face acest lucru, veți adăuga o metodă get() care acceptă un index bazat pe zero al datelor de recuperat, astfel:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

Metoda get() verifică mai întâi dacă index este o valoare pozitivă, altfel returnează undefined. Variabila i este utilizată pentru a ține evidența adâncimii la care a ajuns traversarea în listă. Bucla în sine este aceeași parcurgere de bază pe care ați văzut-o mai devreme, cu condiția suplimentară ca bucla să iasă atunci când i este egală cu index. Aceasta înseamnă că există două condiții în care bucla poate ieși:

1. current este null, ceea ce înseamnă că lista este mai scurtă decât index.
2. i este egal cu index, ceea ce înseamnă că current este nodul din poziția index.

Dacă current este null atunci se returnează undefined, iar în caz contrar se returnează current.data. Această verificare asigură faptul că get() nu va arunca niciodată o eroare pentru un index care nu se găsește în listă (deși ați putea decide să aruncați o eroare în loc să returnați undefined).

Complexitatea metodei get() variază de la O(1) atunci când se elimină primul nod (nu este necesară traversarea) la O(n) atunci când se elimină ultimul nod (este necesară traversarea întregii liste). Este dificil de redus complexitatea deoarece este întotdeauna necesară o căutare pentru a identifica valoarea corectă care trebuie returnată.

Îndepărtarea datelor dintr-o listă legată

Îndepărtarea datelor dintr-o listă legată este un pic mai complicată deoarece trebuie să vă asigurați că toți indicatorii next rămân valabili după ce un nod este îndepărtat. De exemplu, dacă doriți să eliminați al doilea nod dintr-o listă cu trei noduri, va trebui să vă asigurați că proprietatea next a primului nod indică acum al treilea nod în loc de al doilea. Trecerea peste al doilea nod în acest mod îl elimină efectiv din listă.

Operația de eliminare este de fapt două operații:

1. Căutarea indicelui specificat (același algoritm ca în get())
2. Îndepărtarea nodului de la acel indice

Căutarea indicelui specificat este aceeași ca în metoda get(), dar în această buclă trebuie să urmăriți și nodul care vine înainte de current, deoarece va trebui să modificați pointerul next al nodului anterior.

Există, de asemenea, patru cazuri speciale care trebuie luate în considerare:

1. Lista este goală (nu este posibilă traversarea)
2. Indexul este mai mic decât zero
3. Indexul este mai mare decât numărul de elemente din listă
4. Indexul este zero (eliminarea capului)

În primele trei cazuri, operația de eliminare nu poate fi finalizată și, prin urmare, este logic să se arunce o eroare; al patrulea caz special necesită rescrierea proprietății this. Iată cum arată implementarea unei metode remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

Metoda remove() verifică mai întâi două cazuri speciale, o listă goală (this este null) și un index care este mai mic decât zero. În ambele cazuri se aruncă o eroare.

Următorul caz special este atunci când index este 0, ceea ce înseamnă că se elimină capul listei. Noul cap de listă ar trebui să fie al doilea nod din listă, astfel încât puteți seta this egal cu this.next. Nu contează dacă există un singur nod în listă, deoarece this ar sfârși prin a fi egal cu null, ceea ce înseamnă că lista este goală după eliminare. Singura capcană este de a stoca datele din capul original într-o variabilă locală, data, astfel încât acestea să poată fi returnate.

Cu trei din cele patru cazuri speciale rezolvate, puteți continua acum cu o traversare similară cu cea găsită în metoda get(). După cum s-a menționat mai devreme, această buclă este ușor diferită prin faptul că variabila previous este utilizată pentru a ține evidența nodului care apare chiar înainte de current, deoarece această informație este necesară pentru a elimina în mod propice un nod. Similar cu get(), la ieșirea buclei current poate fi null, indicând că indexul nu a fost găsit. Dacă se întâmplă acest lucru, atunci se aruncă o eroare, în caz contrar, previous.next este setat la current.next, eliminând efectiv current din listă. Datele stocate pe current sunt returnate în ultimul pas.

Complexitatea metodei remove() este aceeași cu cea a metodei get() și variază de la O(1) atunci când se elimină primul nod la O(n) atunci când se elimină ultimul nod.

Facerea listei iterabile

Pentru a putea fi utilizate cu bucla JavaScript for-of și destructurarea tablourilor, colecțiile de date trebuie să fie iterabile. Colecțiile încorporate în JavaScript, cum ar fi Array și Set, sunt iterabile în mod implicit și puteți face propriile clase iterabile prin specificarea unei metode generatoare Symbol.iterator pe clasă. Eu prefer să implementez mai întâi o metodă generatoare values() (pentru a se potrivi cu metoda găsită pe clasele de colecții încorporate) și apoi să fac ca Symbol.iterator să apeleze direct values().

Metoda values() trebuie doar să facă o traversare de bază a listei și să yield datele pe care le conține fiecare nod:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

Metoda values()este marcată cu un asterisc (*) pentru a indica faptul că este o metodă generatoare. Metoda parcurge lista, folosind yield pentru a returna fiecare bucată de date pe care o întâlnește. (Rețineți că metoda Symbol.iterator nu este marcată ca fiind un generator deoarece returnează un iterator de la metoda generatoare values().)

Utilizarea clasei

După ce este completă, puteți utiliza implementarea listei legate astfel:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Această implementare de bază a unei liste legate poate fi completată cu o proprietate size pentru a număra numărul de noduri din listă și cu alte metode cunoscute, cum ar fi indexOf(). Codul sursă complet este disponibil pe GitHub la proiectul meu Computer Science in JavaScript.

Concluzie

Listele legate nu sunt ceva ce probabil veți folosi în fiecare zi, dar ele sunt o structură de date fundamentală în informatică. Conceptul de utilizare a nodurilor care indică unul către altul este utilizat în multe alte structuri de date sunt integrate în multe limbaje de programare de nivel superior. O bună înțelegere a modului în care funcționează listele legate este importantă pentru o bună înțelegere generală a modului de creare și utilizare a altor structuri de date.

Pentru programarea JavaScript, este aproape întotdeauna mai bine să utilizați clasele de colecții încorporate, cum ar fi Array, decât să vă creați propriile clase. Clasele de colecții încorporate au fost deja optimizate pentru utilizarea în producție și sunt bine susținute în toate mediile de execuție.

.