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

// 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);

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; } }}

A get() metódus először ellenőrzi, hogy index pozitív érték-e, különben undefined-t ad vissza. A i változót arra használjuk, hogy nyomon kövessük, milyen mélyre ment a listában a keresztezés. Maga a ciklus ugyanaz az alapvető traverzálás, mint amit korábban láttunk, azzal a hozzáadott feltétellel, hogy a ciklusnak ki kell lépnie, ha i egyenlő index-gyel. Ez azt jelenti, hogy a ciklus két feltétellel léphet ki:

1. current null, ami azt jelenti, hogy a lista rövidebb, mint index.
2. i egyenlő index, ami azt jelenti, hogy current a index pozícióban lévő csomópont.

Ha current null, akkor undefined, egyébként pedig current.data. Ez az ellenőrzés biztosítja, hogy a get() soha nem fog hibát dobni egy olyan index-re, amely nem található a listában (bár dönthetünk úgy is, hogy hibát dobunk ahelyett, hogy undefined-t adnánk vissza).

A get() módszer bonyolultsága az O(1)-től az első csomópont eltávolításakor (nincs szükség átjárásra) az O(n)-ig terjed, amikor az utolsó csomópontot távolítjuk el (a teljes lista átjárása szükséges). A bonyolultságot nehéz csökkenteni, mert mindig keresésre van szükség a helyes visszaadandó érték azonosításához.

Adatok eltávolítása egy összekapcsolt listából

Az adatok eltávolítása egy összekapcsolt listából egy kicsit trükkös, mert biztosítani kell, hogy az összes next mutató érvényes maradjon egy csomópont eltávolítása után. Ha például egy három csomópontos listából a második csomópontot akarjuk eltávolítani, akkor gondoskodnunk kell arról, hogy az első csomópont next tulajdonsága a második helyett a harmadik csomópontra mutasson. A második csomópont ilyen módon történő átugrása ténylegesen eltávolítja azt a listából.

Az eltávolítás művelet valójában két műveletből áll:

1. Keresd meg a megadott indexet (ugyanaz az algoritmus, mint a get()-ben)
2. Eltávolítsd a csomópontot ezen az indexen

A megadott index megtalálása ugyanaz, mint a get() módszerben, de ebben a ciklusban a current előtti csomópontot is követni kell, mert módosítani kell az előző csomópont next mutatóját.

Négy speciális esetet is figyelembe kell vennünk:

1. A lista üres (nem lehetséges a bejárás)
2. Az index kisebb, mint nulla
3. Az index nagyobb, mint a lista elemeinek száma
4. Az index nulla (a fej eltávolítása)

Az első három esetben az eltávolítási művelet nem fejezhető be, ezért van értelme hibát dobni; a negyedik speciális esetben a this tulajdonság átírása szükséges. A remove() metódus implementációja így néz ki:

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.`); }}

A remove() metódus először két speciális esetet ellenőriz, az üres listát (this null) és a nullánál kisebb index értéket. Mindkét esetben hibát dob.

A következő speciális eset az, amikor index 0, ami azt jelenti, hogy eltávolítjuk a lista fejét. Az új listafejnek a lista második csomópontjának kell lennie, tehát this egyenlő this.next-gyel. Nem számít, ha csak egy csomópont van a listában, mert this végül null lesz egyenlő, ami azt jelenti, hogy a lista az eltávolítás után üres. Az egyetlen bökkenő az, hogy az eredeti fejből származó adatokat egy helyi változóban, a data-ban kell tárolni, hogy vissza lehessen adni.

A négy speciális esetből háromról gondoskodtunk, most már folytathatjuk a get() módszerben találhatóhoz hasonló traverzálást. Mint korábban említettük, ez a ciklus némileg különbözik annyiban, hogy a previous változót arra használjuk, hogy nyomon kövessük a current előtt közvetlenül megjelenő csomópontot, mivel ez az információ szükséges egy csomópont valószínű eltávolításához. A get()-hez hasonlóan a ciklus kilépésekor a current null lehet, jelezve, hogy az indexet nem találták meg. Ha ez megtörténik, akkor hibaüzenetet kapunk, ellenkező esetben previous.next current.next lesz, ami ténylegesen eltávolítja current-et a listából. A current-en tárolt adatok utolsó lépésként visszakerülnek.

A remove() módszer bonyolultsága megegyezik a get() módszerével, és az O(1)-től az első csomópont eltávolításakor az O(n)-ig terjed, amikor az utolsó csomópontot távolítja el.

A lista iterálhatóvá tétele

A JavaScript for-of ciklusával és a tömbök destruktúrálásával való használathoz az adatgyűjteményeknek iterálhatónak kell lenniük. A beépített JavaScript-gyűjtemények, például a Array és Set alapértelmezés szerint iterálhatóak, és a saját osztályainkat is iterálhatóvá tehetjük, ha megadunk egy Symbol.iterator generáló metódust az osztályon. Én inkább először egy values() generáló metódust implementálok (a beépített gyűjteményosztályokon található metódusnak megfelelően), majd a Symbol.iterator közvetlenül hívja meg a values() metódust.

A values() metódusnak csak a lista alapvető átszelését és yield az egyes csomópontok által tartalmazott adatok

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

A values() metódust csillaggal (*) jelöljük, hogy ez egy generátor metódus. A metódus végigjárja a listát, és yield segítségével minden egyes adatot, amellyel találkozik, visszaad. (Megjegyezzük, hogy a Symbol.iterator metódus nincs generátorként jelölve, mert a values() generátor metódusból egy iterátort ad vissza.)

Az osztály

Ha elkészült, a linkelt lista implementációját így használhatjuk:

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 = ;

A linkelt lista ezen alapvető implementációja kiegészíthető egy size tulajdonsággal, amely megszámolja a listában lévő csomópontok számát, és más ismert módszerekkel, mint például a indexOf(). A teljes forráskód elérhető a GitHubon a Computer Science in JavaScript projektemben.

Következtetés

A linkelt listákat valószínűleg nem használjuk minden nap, de a számítástechnikában alapvető adatszerkezetek. Az egymásra mutató csomópontok használatának koncepcióját számos más adatszerkezetben használják, amelyek számos magasabb szintű programozási nyelvbe vannak beépítve. Az összekapcsolt listák működésének jó megértése fontos más adatszerkezetek létrehozásának és használatának általános megértéséhez.

A JavaScript programozáshoz szinte mindig jobban jár, ha a beépített gyűjteményosztályokat használja, mint például a Array, mintha sajátot hozna létre. A beépített gyűjtőosztályok már optimalizálva vannak a termelési használatra, és jól támogatottak a különböző végrehajtási környezetekben.