Redan 2009 utmanade jag mig själv att skriva ett blogginlägg i veckan under hela året. Jag hade läst att det bästa sättet att få mer trafik till en blogg var att skriva konsekventa inlägg. Ett inlägg per vecka verkade vara ett realistiskt mål på grund av alla artikelidéer jag hade, men det visade sig att jag var långt ifrån 52 idéer. Jag grävde igenom några halvt skrivna kapitel som så småningom skulle bli Professional JavaScript och hittade en hel del material om klassiska datavetenskapliga ämnen, bland annat datastrukturer och algoritmer. Jag tog det materialet och gjorde det till flera inlägg 2009 och (och några 2012), och fick mycket positiv feedback på dem.

Nu, på tioårsdagen av dessa inlägg, har jag bestämt mig för att uppdatera, återpublicera och utöka dem med hjälp av JavaScript 2019. Det har varit intressant att se vad som har förändrats och vad som inte har förändrats, och jag hoppas att du gillar dem.

Vad är en länkad lista?

En länkad lista är en datastruktur som lagrar flera värden på ett linjärt sätt. Varje värde i en länkad lista finns i en egen nod, ett objekt som innehåller data tillsammans med en länk till nästa nod i listan. Länken är en pekare till ett annat nodobjekt eller null om det inte finns någon nästa nod. Om varje nod bara har en pekare till en annan nod (oftast next) anses listan vara en singelkopplad lista (eller bara länkad lista) medan om varje nod har två länkar (vanligtvis previous och next) anses den vara en dubbelt länkad lista. I det här inlägget fokuserar jag på singly linked lists.

Varför använda en länkad lista?

Den främsta fördelen med länkade listor är att de kan innehålla ett godtyckligt antal värden samtidigt som de endast använder den mängd minne som behövs för dessa värden. Att bevara minnet var mycket viktigt på äldre datorer där minnet var knappt. På den tiden krävde en inbyggd array i C att du angav hur många objekt som arrayen kunde innehålla och programmet skulle reservera den mängden minne. Att reservera detta minne innebar att det inte kunde användas för resten av programmet eller andra program som kördes samtidigt, även om minnet aldrig fylldes. På maskiner som har ont om minne kunde man lätt få slut på tillgängligt minne om man använde matriser. Länkade listor skapades för att lösa detta problem.

Och även om de ursprungligen var avsedda för bättre minneshantering blev länkade listor också populära när utvecklare inte visste hur många objekt en matris i slutändan skulle innehålla. Det var mycket enklare att använda en länkad lista och lägga till värden vid behov än att exakt gissa det maximala antalet värden som en array kunde innehålla. Därför används länkade listor ofta som grund för inbyggda datastrukturer i olika programmeringsspråk.

Den inbyggda JavaScript Array-typen implementeras inte som en länkad lista, även om dess storlek är dynamisk och alltid är det bästa alternativet att börja med. Du kanske går hela din karriär utan att behöva använda en länkad lista i JavaScript, men länkade listor är ändå ett bra sätt att lära sig att skapa egna datastrukturer.

Designen av en länkad lista

Den viktigaste delen av en länkad lista är dess nodstruktur. Varje nod måste innehålla vissa data och en pekare till nästa nod i listan. Här är en enkel representation i JavaScript:

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

I klassen LinkedListNode innehåller egenskapen data det värde som den länkade listpunkten ska lagra och egenskapen next är en pekare till nästa punkt i listan. Egenskapen next börjar som null eftersom du ännu inte känner till nästa nod. Du kan sedan skapa en länkad lista med hjälp av LinkedListNode-klassen så här:

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

Den första noden i en länkad lista kallas vanligtvis för huvudet, så head-identifieraren i det här exemplet representerar den första noden. Den andra noden skapas och tilldelas head.next för att skapa en lista med två objekt. En tredje nod läggs till genom att tilldela den till head.next.next, som är next-pekaren för den andra noden i listan. next-pekaren för den tredje noden i listan förblir null. Följande bild visar den resulterande datastrukturen.

Strukturen i en länkad lista gör det möjligt att gå igenom alla data genom att följa next-pekaren på varje nod. Här är ett enkelt exempel på hur man kan gå igenom en länkad lista och skriva ut varje värde till konsolen:

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

Denna kod använder variabeln current som pekare som rör sig genom den länkade listan. Variabeln current initialiseras till listans huvud och slingan while fortsätter tills current är null. Inne i slingan skrivs värdet som är lagrat på noden current ut och därefter följs next-pekaren till nästa nod.

De flesta länkade listoperationer använder den här traversalgoritmen eller något liknande, så det är viktigt att förstå den här algoritmen för att förstå länkade listor i allmänhet.

Klassen LinkedList

Om du skulle skriva en länkad lista i C skulle du kanske stanna vid den här punkten och betrakta din uppgift som slutförd (även om du skulle använda en struct istället för en klass för att representera varje nod). I objektorienterade språk som JavaScript är det dock vanligare att skapa en klass för att kapsla in den här funktionaliteten. Här är ett enkelt exempel:

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

Klassen LinkedList representerar en länkad lista och kommer att innehålla metoder för att interagera med de data den innehåller. Den enda egenskapen är en symbolegenskap kallad head som kommer att innehålla en pekare till den första noden i listan. En symbolegenskap används i stället för en strängegenskap för att klargöra att den här egenskapen inte är avsedd att ändras utanför klassen.

Lägga till nya data till listan

För att lägga till ett objekt i en länkad lista krävs att man går igenom strukturen för att hitta rätt plats, skapar en ny nod och lägger in den på plats. Det enda specialfallet är när listan är tom, då skapar du helt enkelt en ny nod och tilldelar den till 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; } }}

Metoden add() tar emot ett enda argument, en valfri data, och lägger till den i slutet av listan. Om listan är tom (this är null) tilldelar du this lika med den nya noden. Om listan inte är tom måste du gå igenom den redan existerande listan för att hitta den sista noden. Detta sker i en while-slinga som börjar vid this och följer next-länkarna för varje nod tills den sista noden hittas. Den sista noden har en next-egenskap som är lika med null, så det är viktigt att stoppa traverseringen vid den punkten snarare än när current är null (som i föregående avsnitt). Du kan sedan tilldela den nya noden till den next-egenskapen för att lägga till data i listan.

Komplexiteten hos add()-metoden är O(n) eftersom du måste traversera hela listan för att hitta platsen för att infoga en ny nod. Du kan minska denna komplexitet till O(1) genom att spåra slutet av listan (vanligtvis kallad svansen) utöver huvudet, vilket gör att du omedelbart kan infoga en ny nod i rätt position.

Hämtning av data från listan

Länkade listor tillåter inte slumpmässig åtkomst till dess innehåll, men du kan ändå hämta data i en given position genom att traversera listan och returnera data. För att göra det lägger du till en get()-metod som accepterar ett nollbaserat index för de data som ska hämtas, så här:

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

Metoden get() kontrollerar först att index är ett positivt värde, annars returnerar den undefined. Variabeln i används för att hålla reda på hur djupt traverseringen har gått i listan. Själva slingan är samma grundläggande traversal som du såg tidigare med det tillagda villkoret att slingan ska avslutas när i är lika med index. Det innebär att det finns två villkor under vilka slingan kan avslutas:

1. current är null, vilket innebär att listan är kortare än index.
2. i är lika med index, vilket innebär att current är noden i index-positionen.

Om current är null returneras undefined och annars current.data. Denna kontroll säkerställer att get() aldrig kommer att kasta ett fel för en index som inte finns i listan (även om du kan bestämma dig för att kasta ett fel i stället för att returnera undefined).

Komplexiteten hos get()-metoden sträcker sig från O(1) när den första noden tas bort (ingen traversering behövs) till O(n) när den sista noden tas bort (traversering av hela listan krävs). Det är svårt att minska komplexiteten eftersom det alltid krävs en sökning för att identifiera rätt värde att returnera.

Hämtning av data från en länkad lista

Hämtning av data från en länkad lista är lite knepigt eftersom man måste se till att alla next pekare förblir giltiga efter att en nod tagits bort. Om du till exempel vill ta bort den andra noden i en lista med tre noder måste du se till att den första nodens next-egenskap nu pekar på den tredje noden i stället för den andra. Genom att hoppa över den andra noden på detta sätt tas den effektivt bort från listan.

Operationen borttagning är egentligen två operationer:

1. Hitta det angivna indexet (samma algoritm som i get())
2. Ta bort noden vid det indexet

Hitta det angivna indexet är samma sak som i get()-metoden, men i den här slingan måste du också spåra noden som kommer före current eftersom du måste ändra next-pointern för den föregående noden.

Det finns också fyra specialfall att ta hänsyn till:

1. Listan är tom (ingen traversering är möjlig)
2. Indexet är mindre än noll
3. Indexet är större än antalet objekt i listan
4. Indexet är noll (ta bort huvudet)

I de tre första fallen kan borttagningen inte fullföljas och det är därför vettigt att kasta ett fel; det fjärde specialfallet kräver att egenskapen this skrivs om. Så här ser implementeringen av en remove()-metod ut:

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

Metoden remove() kontrollerar först två specialfall, en tom lista (this är null) och en index som är mindre än noll. Ett fel kastas i båda fallen.

Nästa specialfall är när index är 0, vilket innebär att du tar bort listhuvudet. Den nya listhuvudet ska vara den andra noden i listan, så du kan sätta this lika med this.next. Det spelar ingen roll om det bara finns en nod i listan eftersom this skulle sluta lika med null, vilket innebär att listan är tom efter borttagningen. Den enda haken är att lagra data från det ursprungliga huvudet i en lokal variabel, data, så att den kan returneras.

Med tre av de fyra specialfallen omhändertagna kan du nu fortsätta med en traversal som liknar den som finns i get()-metoden. Som tidigare nämnts är den här slingan något annorlunda eftersom variabeln previous används för att hålla reda på den nod som dyker upp strax före current, eftersom den informationen är nödvändig för att kunna ta bort en nod. I likhet med get() kan current när slingan avslutas vara null, vilket indikerar att indexet inte hittades. Om detta inträffar kastas ett fel, annars sätts previous.next till current.next, vilket effektivt tar bort current från listan. De data som är lagrade på current returneras som sista steg.

Komplexiteten för remove()-metoden är densamma som för get() och sträcker sig från O(1) när den första noden tas bort till O(n) när den sista noden tas bort.

Makar listan iterabel

För att kunna användas med JavaScript for-of-slingan och array-destrukturering måste samlingar av data vara iterabla. De inbyggda JavaScript-samlingarna som Array och Set är iterabla som standard, och du kan göra dina egna klasser iterabla genom att ange en Symbol.iteratorgeneratormetod på klassen. Jag föredrar att först implementera en values()-generatormetod (för att matcha den metod som finns på inbyggda samlingsklasser) och sedan låta Symbol.iterator anropa values() direkt.

Metoden values() behöver bara göra en grundläggande traversering av listan och yield de data som varje nod innehåller:

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

Metoden values() är markerad med en asterisk (*) för att visa att det är en generatormetod. Metoden går igenom listan och använder yield för att returnera varje data som den möter. (Observera att Symbol.iterator-metoden inte är markerad som en generator eftersom den returnerar en iterator från values()-generatormetoden.)

Användning av klassen

När du är klar kan du använda implementeringen av den länkade listan så här:

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

Denna grundläggande implementering av en länkad lista kan avrundas med en size-egenskap för att räkna antalet noder i listan, och andra välkända metoder som indexOf(). Den fullständiga källkoden finns på GitHub i mitt projekt Computer Science in JavaScript.

Slutsats

Länkade listor är inte något som du troligen använder varje dag, men de är en grundläggande datastruktur inom datavetenskap. Konceptet att använda noder som pekar på varandra används i många andra datastrukturer är inbyggda i många högre programmeringsspråk. En god förståelse för hur länkade listor fungerar är viktig för en god övergripande förståelse för hur man skapar och använder andra datastrukturer.

För JavaScript-programmering är det nästan alltid bättre att använda de inbyggda samlingsklasserna som Array än att skapa egna. De inbyggda samlingsklasserna har redan optimerats för produktionsanvändning och har ett bra stöd i alla exekveringsmiljöer.