de Michael Olorunnisola

O introducere ușoară a structurilor de date: modul în care funcționează listele legate

1612087268 223 O introducere usoara a structurilor de date modul in care
Pinterest

Ați construit vreodată o mașină Rube Goldberg? Dacă nu, poate ați construit o linie elaborată de domino?

Bine, poate că nu erai la fel de ticălos de copil ca mine. Așa să fie. Pentru cei dintre voi care au avut plăcerea de a face oricare dintre cele de mai sus, ați înțeles deja esența structurii de date de astăzi: listele legate!

O introducere usoara a structurilor de date modul in care

Cum funcționează listele legate

Cea mai simplă formă de liste legate – a listă legată individual – este o serie de noduri în care fiecare nod individual conține atât o valoare, cât și un indicator către următorul nod din listă.

Adăugări (Adăuga) creșteți lista adăugând elemente la sfârșitul listei.

Mutări (Elimina) va elimina întotdeauna dintr-o poziție dată din listă.

Căutare (Conține) va căuta în listă o valoare.

Exemple de cazuri de utilizare:

  • Stocarea valorilor într-un tabel hash pentru a preveni coliziunile (mai multe despre acest lucru în câteva postări)
  • Refacând cursa uimitoare!
1612087269 513 O introducere usoara a structurilor de date modul in care

Să păstrăm acest articol frumos și ușor, lucrând la un instrument pe care rețeaua CBS îl poate folosi pentru a-și planifica următoarea emisiune TV de curse uimitoare.

Pe măsură ce treceți prin acest lucru, vreau să vă întrebați în continuare: „Cum diferă listele legate de matrici? Cum sunt similare? ”

Să începem.

Mai întâi, trebuie să creați reprezentarea listei noastre conectate:

class LinkedList{  constructor(){    this._head = null;    this._tail = null;    this._length = 0;  }
  size(){    return this._length;  }}

Pentru a urmări punctul de plecare și punctul final al cursei, creați proprietățile capului și cozii.

Apoi, pentru a vă asigura că nu faceți cursa prea lungă sau prea scurtă pentru sezon, creați o metodă de lungime și dimensiune. În acest fel, puteți urmări întotdeauna exact cât de lungă este cursa.

Acum că aveți o modalitate de a stoca lista de curse, ar trebui să creați o modalitate de a adăuga la această listă. Întrebarea este, ce adăugați în mod specific?

Amintiți-vă, o listă legată este o serie de noduri în care fiecare nod are o valoare și un pointer către următorul nod din listă. Știind acest lucru, vă dați seama că un nod este doar un obiect cu o valoare și o proprietate următoare.

Deoarece veți crea un nod nou de fiecare dată când adăugați la listă, decideți să creați un constructor care să faciliteze crearea unui nou nod pentru fiecare valoare adăugată la listă.

class Node{  constructor(value){    this.value = value;    this.next = null;  }}

Având acest constructor disponibil vă permite să creați metoda de adăugare.

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}
class LinkedList {   constructor() {    this._head = null;    this._tail = null;    this._length = 0;  }    add(value) {    let node = new Node(value);         //we create our node    if(!this._head && !this._tail){     //If it's the first node      this._head = node;                //1st node is head & tail      this._tail = node;    }else{    this._tail.next = node;             //add node to the back    this._tail = this._tail.next;       //reset tail to last node    }    this._length++;  }    size() {    return this._length;  }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

Acum, după ce ați adăugat această metodă, veți putea adăuga o grămadă de locații în lista dvs. Amazing Race. Așa va arăta. Rețineți că am adăugat un spațiu alb suplimentar pentru a ușura înțelegerea.

{ _head:    { value: 'Colombo, Sri Lanka',     next: { value: 'Lagos, Nigeria',              next: { value: 'Surat, India',                     next: { value: 'Suzhou, China',                             next: null                            }                   }           }    },  _tail: { value: 'Suzhou, China', next: null },  _length: 4 }

Bine, deci acum că ați creat această listă și o modalitate de a adăuga, vă dați seama că doriți ajutor pentru adăugarea de locații în această listă, deoarece aveți decidofobie (da, este o lucru).

Decizi să îl împărtășești colegului tău de muncă, Kent, cerându-i să mai adauge câteva locuri. Singura problemă este că, atunci când i-o dai, nu îi spui ce locuri ai adăugat deja. Din păcate, ai uitat și tu după ce ai suferit de amnezie cauzată de anxietatea decizională.

Bineînțeles că ar putea fugi console.log (AmazingRace) și citiți ce rezultă consola. Dar Kent este un programator leneș și are nevoie de o modalitate de a verifica dacă există ceva, astfel încât să poată preveni duplicatele. Având în vedere acest lucru, construiți un conține metoda de verificare a valorilor existente.

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}class LinkedList {   constructor() {    this._head = null;    this._tail = null;    this._length = 0;  }    add(value) {    let node = new Node(value);             if(!this._head && !this._tail){           this._head = node;                      this._tail = this._head;    }else{    this._tail.next = node;                 this._tail = this._tail.next;           }    this._length++;  }    contains(value){    let node = this._head;    while(node){      if(node.value === value){        return true;      }      node = node.next;    }    return false;  }    size() {    return this._length;  }  }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

Minunat, acum Kent are o modalitate de a verifica valorile înainte de a le adăuga, pentru a evita duplicatele.

Ca o parte, s-ar putea să vă întrebați de ce nu ați folosit pur și simplu metoda conține în metoda adăugare pentru a preveni adăugările duplicate? Când implementați o listă legată – sau orice structură de date, de altfel – ați putea adăuga teoretic orice funcționalitate suplimentară doriți.

Puteți chiar să intrați și să modificați metodele native pe structurile existente. Încercați cele de mai jos într-un REPL:

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

Motivul pentru care nu facem niciuna dintre aceste lucruri este din cauza standarde convenite. În esență, dezvoltatorii au o așteptare a modului în care ar trebui să funcționeze anumite metode.

1612087270 123 O introducere usoara a structurilor de date modul in care

Întrucât clasa noastră de listă legată nu este nativă din JavaScript, avem mai multă libertate în implementarea acestuia, dar există încă așteptări de bază cu privire la modul în care ar trebui să funcționeze structuri de date precum acestea. Listele conectate nu stochează în mod inerent valori unice. Dar au metode de genul conține care ne permit să verificăm în prealabil și să menținem unicitatea în lista noastră.

Kent vă revine cu lista sa de destinații, dar unele dintre ele sunt îndoielnice. De exemplu, Polul Nord ar putea să nu fie cea mai bună destinație Amazing Race.

Deci, decideți să construiți o metodă pentru a putea elimina un nod. Este important să ne amintim că, odată ce eliminați nodul, deconectați lista și va trebui să reconectați ceea ce a venit înainte și după nodul eliminat.

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}class LinkedList {   constructor() {    this._head = null;    this._tail = null;    this._length = 0;  }    add(value) {    let node = new Node(value);             if(!this._head && !this._tail){           this._head = node;                      this._tail = this._head;    }else{    this._tail.next = node;                 this._tail = this._tail.next;           }    this._length++;  }    remove(value) {    if(this.contains(value)){          // see if our value exists      let current = this._head;           // begin at start of list      let previous = this._head;        while(current){                   // check each node          if(current.value === value){            if(this._head === current){   // if it's the head              this._head = this._head.next;  // reset the head              this._length--;              // update the length              return;                      // break out of the loop            }            if(this._tail === current){   // if it's the tail node              this._tail = previous;       // make sure to reset it            }            previous.next = current.next;  // unlink (see img below)            this._length--;            // update the length            return;                    // break out of           }          previous = current;          // look at the next node          current = current.next;      // ^^        }     }    }      contains(value){    let node = this._head;    while(node){      if(node.value === value){        return true;      }      node = node.next;    }    return false;  }    size() {    return this._length;  }  }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

Există o mulțime de cod în asta elimina funcționează acolo sus. În esență, se reduce la următoarele:

  1. dacă valoarea există în listă …
  2. iterați peste lista legată, ținând evidența nodului anterior și actual
  3. atunci, dacă există un meci →

4A. dacă este capul

  • resetați capul la următorul nod din listă
  • actualizați lungimea
  • ieși din buclă

4B. dacă este coada

  • resetați coada la nodul anterior din listă
  • deconectați nodul resetând pointerele așa cum se vede mai jos
1612087270 411 O introducere usoara a structurilor de date modul in care
Wikipedia

4C. Dacă nu este un meci → continuați iterația

  • faceți următorul nod curent
  • faceți ca nodul curent să fie anterior

Un ultim lucru de remarcat: este posibil să fi realizat că nu ați șters nodul. Tocmai ați eliminat referințele la acesta. Ei bine, este în regulă, deoarece odată ce toate referințele la un obiect sunt eliminate, colectorul de gunoi ne ajută să îl eliminăm din memorie. Puteți citi mai multe despre colectarea gunoiului Aici.

Cu metoda de eliminare implementată acum, puteți rula acest mic fragment de cod de mai jos pentru a vă asigura că concurenții nu îngheță până la moarte sau îl deranjează accidental pe Moș Crăciun în timp ce se pregătește pentru festivitățile din acest an.

AmazingRace.remove('North Pole');

Ai făcut-o! Ați creat o implementare simplă a unei liste conectate. Și puteți crește lista adăugând articole și micșorați-o prin eliminarea articolelor – totul pe baza valorii articolului.

Vedeți dacă puteți adăuga, puteți extinde lista legată pentru a vă permite să inserați valori la începutul, sfârșitul sau orice punct intermediar.

Aveți tot ce aveți nevoie pentru a implementa aceste metode. Numele și argumentele pentru aceste metode ar trebui să arate cam așa:

addHead(value) {
}
insertAfter(target, value){
}

Sunteți liber să împărtășiți implementările dvs. în comentariile de mai jos?

O analiză a complexității timpului asupra metodelor cozii

1612087271 79 O introducere usoara a structurilor de date modul in care

Iată codul din nou:

class LinkedList {   constructor() {    this._head = null;    this._tail = null;    this._length = 0;  }    add(value) {    let node = new Node(value);             if(!this._head && !this._tail){           this._head = node;                      this._tail = this._head;    }else{    this._tail.next = node;                 this._tail = this._tail.next;           }    this._length++;  }    remove(value) {    if(this.contains(value)){                let current = this._head;              let previous = this._head;        while(current){                   if(current.value === value){            if(this._head === current){               this._head = this._head.next;              this._length--;                            return;                                  }            if(this._tail === current){               this._tail = previous;                }            previous.next = current.next;            this._length--;                        return;                              }          previous = current;                    current = current.next;              }     }    }     contains(value){    let node = this._head;    while(node){      if(node.value === value){        return true;      }      node = node.next;    }    return false;  }    size() {    return this._length;  }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Adăuga este O (1): Deoarece știți întotdeauna ultimul element din listă datorită proprietății tail, nu trebuie să repetați lista.

Elimina este Pe): În cel mai rău caz, va trebui să iterați pe întreaga listă pentru a găsi valoarea de eliminat. O mare parte este că îndepărtarea efectivă a nodului este O (1), deoarece doar resetați indicii.

Conține este Pe): Trebuie să iterați pe întreaga listă pentru a verifica dacă valoarea există în lista dvs.

addHead este O (1): Similar metodei noastre de adăugare de mai sus, știm întotdeauna poziția capului, deci nu este necesară nicio iterație.

insertAfter este Pe): Similar metodei noastre de Eliminare de mai sus, va trebui să iterați pe întreaga listă pentru a găsi nodul țintă după care ar trebui inserată valoarea dvs. La fel, inserția efectivă este O (1), deoarece doar resetați pointerii.

Listă legată vs matrice?

De ce ați utiliza o listă legată în loc de matrice? Tablourile vă permit în mod tehnic să faceți toate lucrurile pe care le fac listele legate, cum ar fi adăugări, inserții și eliminări. De asemenea, toate aceste metode sunt deja disponibile pentru noi în JavaScript.

Ei bine, cea mai mare diferență vine în inserții și înlăturări. Deoarece matricile sunt indexate, atunci când efectuați o inserare sau eliminare în mijlocul matricei, trebuie să resetați poziția tuturor valorilor următoare la noii lor indici.

Imaginați-vă că introduceți la începutul sau la mijlocul unui tablou lung de 100.000 de valori! Inserturile și îndepărtările de acest gen sunt extrem de scumpe. Din această cauză, listele legate sunt adesea preferate pentru seturile de date mari, care sunt adesea mutate.

Pe de altă parte, tablourile sunt excelente atunci când vine vorba de găsirea articolelor (acces aleatoriu), deoarece acestea sunt indexate. Dacă cunoașteți poziția unui articol, îl puteți accesa în timp O (1) prin matrice[position].

Listele conectate necesită întotdeauna să iterați pe listele conectate secvențial. Având în vedere acest lucru, tablourile sunt de obicei preferate fie pentru seturi de date mai mici, fie pentru seturi de date care nu sunt deplasate la fel de des.

Este timpul pentru o recapitulare rapidă

Liste legate:

  1. au o proprietate coadă și cap pentru a urmări capetele listei
  2. aveți o metodă add, addHead, insertAfter și remove pentru a gestiona conținutul listei dvs.
  3. aveți o proprietate de lungime pentru a urmări cât de lungă este lista dvs. legată

Lecturi suplimentare

Există, de asemenea, structurile de date cu listă dublă și listă circulară. Puteți citi despre ele pe Wikipedia.

De asemenea, iată un model solid, rapid Prezentare generală de Vivek Kumar.

În cele din urmă, Ian Elliot a scris un plimbare care vă ajută să implementați toate metodele. Dar vezi dacă poți implementa addHead () și insertAfter () pentru lista dvs. legată înainte de a arunca o privire la asta?