de Kevin Turney
Ca stive și cozi, Listele legate sunt o formă a unei colecții secvențiale. Nu trebuie să fie în ordine. O listă legată este alcătuită din noduri independente care pot conține orice tip de date. Fiecare nod are o referință la următorul nod din link.
Putem emula stive și cozi cu liste legate. La fel de bine îl putem folosi ca bază pentru a crea sau a mări alte structuri de date. Cu listele conectate, preocupările noastre principale sunt cu inserții și ștergeri rapide, care sunt mai performante peste matrice.
Blocul de construcție al acestei structuri este un nod.
const Node = function(value) { this.value = value; this.next = null;};Nodul nostru este construit cu două proprietăți, a value să dețină date și next, o referință setată inițial la nul. next proprietatea este utilizată pentru a „indica” următorul nod din legătură. Unul dintre dezavantajele listelor legate este că fiecare referință necesită o memorie mai mare decât o matrice.
Implementare
const LinkedList = function(headvalue) { // !! coerces a value to a Boolean if (!!headvalue) { return "Must provide an initial value for the first node" } else { this._head = new Node(headvalue); this._tail = this.head; }};În cel de-al doilea constructor, testăm o valoare pentru a furniza primul nod. Dacă este adevărat, continuăm să creăm un nou nod cu valoarea trecută și setăm capul la coadă inițial.
Inserare
LinkedList.prototype.insertAfter = function(node, value) { let newNode = new Node(value); let oldNext = node.next; newNode.next = oldNext; node.next = newNode; if (this._tail === node) { this._tail = newNode; } return newNode;};Pentru această metodă, creăm un nou nod și ajustăm referințele. Fosta următoare referință a nodului original este acum îndreptată către newNode. Următoarea referință a noului nod este „indicată” la ce se referea următorul nod anterior. În cele din urmă, verificăm și resetăm proprietatea coadă.
LinkedList.prototype.insertHead = function(value) { let newHead = new Node(value); let oldHead = this._head newHead.next = oldHead; this._head = newHead; return this._head;};LinkedList.prototype.appendToTail = function(value) { let newTail = new Node(value); this._tail.next = newTail; this._tail = newTail; return this._tail;};Inserarea la începutul sau la sfârșitul unei liste conectate este rapidă, funcționând în timp constant. Pentru aceasta, creăm un nou nod cu o valoare și rearanjăm variabilele noastre de referință. Resetăm nodul care este acum capul cu insertHead sau coada cu appendToTail.
Aceste operații reprezintă inserții rapide pentru colecții, împingere pentru stive și coadă pentru cozi. S-ar putea să vă vină în minte că neschimbarea pentru matrice este aceeași. Nu, pentru că, cu unshift, toți membrii colecției trebuie să fie mutați cu un singur index. Acest lucru îl face o operație liniară în timp.
Ștergere
LinkedList.prototype.removeAfter = function(node) { let removedNode = node.next; if (!!removedNode) { return "Nothing to remove" } else { let newNext = removedNode.next node.next = newNext; removedNode.next = null; // dereference to null to free up memory if (this._tail === removedNode) { this._tail = node; } } return removedNode;};Începând cu un test pentru eliminarea unui nod, procedăm la ajustarea referințelor. Diferențierea removedNode iar setarea la nul este importantă. Acest lucru eliberează memoria și evită să aibă mai multe referințe la același obiect.
LinkedList.prototype.removeHead = function() { let oldHead = this._head; let newHead = this._head.next; this._head = newHead; oldHead.next = null; return this._head;};Ștergerea unui cap și a unui nod specificat în, removeAfter, sunt îndepărtări constante de timp. În plus, dacă se cunoaște valoarea cozii, atunci îndepărtarea cozii se poate face în O (1). Altfel, trebuie să ne deplasăm liniar până la capăt pentru al elimina, O (N);
Buclă și pentru fiecare
Folosim următoarele pentru a itera printr-o listă legată sau pentru a opera pe fiecare valoare a nodului.
LinkedList.prototype.findNode = function(value) { let node = this._head; while(node) { if (node.value === value) { return node; } node = node.next; } return `No node with ${value} found`;};LinkedList.prototype.forEach = function(callback) { let node = this._head; while(node) { callback(node.value); node = node.next; }};LinkedList.prototype.print = function() { let results = []; this.forEach(function(value) { result.push(value); }); return result.join(', ');};
Principalul avantaj al Listelor conectate este inserarea și ștergerea rapidă fără a rearanja elementele sau realocarea spațiului. Când folosim o matrice, spațiul de memorie este contigu, adică îl păstrăm pe toate împreună. Cu listele legate, putem avea spații de memorie peste tot, stocare necontiguă prin utilizarea de referințe. Pentru tablouri, acea localitate de referințe înseamnă că tablourile au o mai bună stocare în cache a valorilor pentru o căutare mai rapidă. Cu listele conectate, stocarea în cache nu este optimizată, iar timpul de acces durează mai mult.
Un alt aspect al listelor legate este diferitele tipuri de configurație. Două exemple primare sunt circular legat, unde coada are o referință la cap și capul la coadă. De două ori legat este atunci când, pe lângă nodul care are o referință la nodul următor, are și o referință privind înapoi la nodul anterior.
Complexitatea timpului
Inserare
- insertHead, appendToTail – O (1)
- dacă este cunoscut un anumit nod, insertAfter – O (1)
Ștergere
- removeHead – O (1);
- dacă este cunoscut un anumit nod, removeAfter – O (1)
- dacă nodul nu este cunoscut – O (N)
Traversare
- findNode, forEach, print – O (N)
Resurse
Localitatea de referință
Răspunsuri grozave aici
si aici
Listă legată
Mulțumesc pentru lectură. Pentru practică, încercați să implementați o stivă sau o coadă cu o listă legată sau să stocați tablouri în fiecare nod și extrageți date. Întrebați-vă când ajung la o gamă, este, de fapt, cea mai bună alegere pentru nevoile mele?
