för att få en klar förståelse för singly linked list, implementerar jag LinkedList-klassen i JavaScript.

varje nod i länkad lista kommer att ha två attribut: värde & nästa, och länkad lista kommer att ha huvud, svans och längd attribut.

tryck

hur kan vi driva en ny nod i slutet av vår lista? Låt oss göra en push-funktion. Först måste vi skapa en ny nod med det angivna värdet, kontrollera om listan har ett huvud (är det tomt?) och glöm inte att öka storleken på listan.

Pop

med pushing måste vi tänka på popping, radera det sista elementet. Om det inte finns någon nod, returnera odefinierad, annars, slinga genom listan tills vi når svansen, Ställ in nästa egenskap för den näst sista noden för att vara null, gör den näst sista för att vara svansen, glöm inte att minska storleken på listan.

Skift

för att radera det första elementet, skifta, som vanligt, kontrollera om listan är tom. Först lagra det aktuella huvudet i en variabel, Ställ in huvudet för att vara det aktuella huvudets nästa, minska längden.

Unshift

om du vill infoga en nod i början av listan, kontrollera om listan är tom, om inte, ställer vi in det aktuella huvudet för att vara det nästa attribut för den inkommande noden, öka storleken.

Get

Även om länkad lista inte har index, kan vi fortfarande hitta noden med givet index. Kontrollera först att det angivna indexet är större än noll och mindre eller lika med längden på listan. Än vi slingrar igenom listan tills vi når indexet.

Set

Vad händer om vi vill ändra en nod i vår lista? Vi hittar noden med get () och ställer in noden med givna data.

infoga

När vi vill infoga en ny nod i listan, kontrollera först om indexet är större än 0 och mindre än längden. Om index är längden använder vi bara push(), om indexet är 0 använder vi unshift(). För andra index måste vi få noden vid index-1 och ställa in nästa egenskap för den noden för att vara den nya noden och nästa egenskap för den nya noden för att vara den föregående nästa egenskapen, då ökar vi längden.

Ta bort

Till skillnad från pop och unshift, tar bort funktionen bort noden med givet index. Kontrollera som vanligt om indexet är giltigt, om index är lika med Längd-1 eller 0, använd pop eller shift. Annars får vi noden vid index-1, Ställ in nästa egenskap på den noden för att vara nästa av nästa egenskap, efter minskar vi storleken.

omvänd

den ultimata omvända frågan! Hur vänder vi listan? Först byter vi huvud och svans, förklarar nästa och föregående, ställer in föregående som null. Vi går igenom listan.