Vuonna 2009 haastoin itseni kirjoittamaan yhden blogikirjoituksen viikossa koko vuoden ajan. Olin lukenut, että paras tapa saada lisää liikennettä blogiin oli kirjoittaa johdonmukaisesti. Yksi viesti viikossa tuntui realistiselta tavoitteelta kaikkien niiden artikkeli-ideoiden vuoksi, joita minulla oli, mutta kävi ilmi, että 52 ideaa jäi reilusti vajaaksi. Kaivoin läpi joitakin puoliksi kirjoitettuja lukuja, joista lopulta tulisi Professional JavaScript, ja löysin paljon materiaalia klassisista tietotekniikan aiheista, kuten tietorakenteista ja algoritmeista. Otin tuon materiaalin ja muutin sen useiksi postauksiksi vuosina 2009 ja (ja muutamaksi vuonna 2012), ja sain niistä paljon myönteistä palautetta.

Nyt, kun noista postauksista on kulunut kymmenen vuotta, olen päättänyt päivittää, julkaista ne uudelleen ja laajentaa niitä JavaScriptin avulla vuonna 2019. On ollut mielenkiintoista nähdä, mikä on muuttunut ja mikä ei, ja toivon, että pidät niistä.

Mikä on linkitetty lista?

Linkitetty lista on tietorakenne, joka tallentaa useita arvoja lineaarisesti. Jokainen linkitetyn listan arvo on omassa solmussaan, objektissa, joka sisältää datan sekä linkin listan seuraavaan solmuun. Linkki on osoitin toiseen solmukohteeseen tai null, jos seuraavaa solmua ei ole. Jos kullakin solmulla on vain yksi osoitin toiseen solmuun (useimmiten next), listaa pidetään yksittäisesti linkitettynä listana (tai pelkkänä linkitettynä listana), kun taas jos kullakin solmulla on kaksi linkkiä (yleensä previous ja next), listaa pidetään kaksinkertaisesti linkitettynä listana. Tässä postauksessa keskityn yksinkertasesti linkitettyihin listoihin.

Miksi käyttää linkitettyä listaa?

Linkitettyjen listojen ensisijainen hyöty on se, että ne voivat sisältää mielivaltaisen määrän arvoja samalla kun ne käyttävät vain näiden arvojen tarvitsemaa muistimäärää. Muistin säilyttäminen oli erittäin tärkeää vanhemmissa tietokoneissa, joissa muistia oli niukasti. Tuohon aikaan C:n sisäänrakennettu joukko vaati, että määrittelit, kuinka monta kohdetta joukko voi sisältää, ja ohjelma varasi kyseisen määrän muistia. Muistin varaaminen tarkoitti, että sitä ei voitu käyttää muuhun ohjelmaan tai muihin samaan aikaan käynnissä oleviin ohjelmiin, vaikka muistia ei koskaan täytettäisikään. Muistipulassa olevilla koneilla käytettävissä oleva muisti saattoi helposti loppua kesken, kun käytettiin matriiseja. Linkitetyt listat luotiin tämän ongelman kiertämiseksi.

Vaikka linkitetyt listat oli alun perin tarkoitettu parempaan muistinhallintaan, niistä tuli suosittuja myös silloin, kun kehittäjät eivät tienneet, kuinka monta elementtiä joukko lopulta sisältäisi. Oli paljon helpompaa käyttää linkitettyä listaa ja lisätä arvoja tarpeen mukaan kuin arvailla tarkasti, kuinka monta arvoa matriisi voisi enintään sisältää. Näin ollen linkitettyjä listoja käytetään usein eri ohjelmointikielten sisäänrakennettujen tietorakenteiden perustana.

Javaskriptin sisäänrakennettua Array tyyppiä ei ole toteutettu linkitettynä listana, vaikka sen koko on dynaaminen ja se on aina paras vaihtoehto aloittaa. Saatat kulkea koko urasi tarvitsematta käyttää linkitettyä listaa JavaScriptissä, mutta linkitetyt listat ovat silti hyvä tapa oppia luomaan omia tietorakenteita.

Linkitetyn listan rakenne

Linkitetyn listan tärkein osa on sen solmurakenne. Jokaisen solmun on sisällettävä jotakin tietoa ja osoitin listan seuraavaan solmuun. Tässä on yksinkertainen esitys JavaScriptissä:

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

Luokassa LinkedListNode data-ominaisuus sisältää arvon, joka linkitetyn listan solmun tulee tallentaa, ja next-ominaisuus on osoitin listan seuraavaan solmuun. next-ominaisuus on aluksi null, koska seuraavaa solmua ei vielä tiedetä. Tämän jälkeen voit luoda linkitetyn listan käyttämällä LinkedListNode-luokkaa seuraavasti:

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

Linkitetyn listan ensimmäistä solmua kutsutaan yleensä headiksi, joten head-tunniste tässä esimerkissä edustaa ensimmäistä solmua. Toinen solmu luodaan ja osoitetaan head.next:lle, jotta luodaan luettelo, jossa on kaksi kohtaa. Kolmas solmu lisätään osoittamalla se head.next.next:lle, joka on listan toisen solmun next-osoitin. Luettelon kolmannen solmun next-osoitin jää null:ksi. Seuraavassa kuvassa näkyy tuloksena syntyvä tietorakenne.

Linkitetyn listan rakenteen avulla voidaan käydä läpi kaikki tiedot seuraamalla kunkin solmun next-osoitinta. Seuraavassa on yksinkertainen esimerkki linkitetyn listan läpikäymisestä ja jokaisen arvon tulostamisesta konsoliin:

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

Tässä koodissa käytetään muuttujaa current osoittimena, joka liikkuu linkitetyn listan läpi. Muuttuja current alustetaan listan päähän ja while-silmukka jatkuu, kunnes current on null. Silmukan sisällä current-solmuun tallennettu arvo tulostetaan ja sen jälkeen next-osoitinta seurataan seuraavaan solmuun.

Useimmat linkitetyn listan operaatiot käyttävät tätä tai jotain vastaavaa läpikulkualgoritmia, joten tämän algoritmin ymmärtäminen on tärkeää linkitettyjen listojen ymmärtämiseksi yleensä.

LinkitettyLista-luokka

Jos olisit kirjoittamassa linkitettyä listaa C:llä, voisit ehkä lopettaa tähän kohtaan ja pitää tehtävääsi suoritettuna (vaikka käyttäisitkin luokan sijasta rakennetta (struct) kuvaamaan jokaista solmua). Oliopohjaisissa kielissä, kuten JavaScriptissä, on kuitenkin tavallisempaa luoda luokka, joka kapseloi tämän toiminnallisuuden. Tässä on yksinkertainen esimerkki:

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

Luokka LinkedList edustaa linkitettyä listaa, ja se sisältää metodeja vuorovaikutukseen sen sisältämien tietojen kanssa. Ainoa ominaisuus on symboliominaisuus head, joka sisältää osoittimen listan ensimmäiseen solmuun. Symboli-ominaisuutta käytetään merkkijono-ominaisuuden sijasta, jotta olisi selvää, että tätä ominaisuutta ei ole tarkoitus muokata luokan ulkopuolella.

Uuden datan lisääminen listaan

Elementin lisääminen linkitettyyn listaan vaatii rakenteen kävelemistä oikean paikan etsimiseen, uuden solmun luomista ja solmun lisäämistä paikalleen. Yksi erikoistapaus on, kun lista on tyhjä, jolloin yksinkertaisesti luodaan uusi solmu ja osoitetaan se 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; } }}

Metodi add() hyväksyy yhden argumentin, minkä tahansa tiedon, ja lisää sen listan loppuun. Jos lista on tyhjä (this on null), osoitetaan this yhtä suuri kuin uusi solmu. Jos lista ei ole tyhjä, jo olemassa olevaa listaa on käytävä läpi viimeisen solmun löytämiseksi. Kulkeminen tapahtuu while-silmukassa, joka alkaa this:stä ja seuraa jokaisen solmun next-linkkejä, kunnes viimeinen solmu löytyy. Viimeisen solmun next-ominaisuus on yhtä suuri kuin null, joten on tärkeää pysäyttää läpikäynti siihen kohtaan eikä silloin, kun current on null (kuten edellisessä osassa). Tämän jälkeen voit määrittää uuden solmun tuohon next-ominaisuuteen lisätäksesi tiedot luetteloon.

Menetelmän add() monimutkaisuus on O(n), koska sinun on käytävä läpi koko luettelo löytääksesi paikan, johon lisätä uusi solmu. Voit pienentää tämän monimutkaisuuden O(1):een seuraamalla listan pään lisäksi myös listan loppua (jota yleensä kutsutaan hännäksi), jolloin voit lisätä uuden solmun heti oikeaan paikkaan.

Datan hakeminen listasta

Linkitetyt listat eivät salli satunnaista pääsyä listan sisältöön, mutta voit silti hakea datan mistä tahansa tietystä kohdasta kulkemalla listan läpi ja palauttamalla datan. Tätä varten lisäät get()-metodin, joka hyväksyy nollapohjaisen indeksin haettavasta datasta, näin:

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

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

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

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