En mild introduktion til datastrukturer: Sådan fungerer sammenkædede lister

Har du nogensinde bygget en Rube Goldberg-maskine? Hvis ikke, har du måske bygget en detaljeret række dominoer?

Okay, måske var du ikke så nørdet af et barn som mig. Så være det. For dem af jer, der har haft fornøjelsen at gøre noget af det ovenstående, har du allerede forstået essensen af ​​dagens datastruktur: sammenkædede lister!

Hvordan linkede lister fungerer

Den enkleste form for sammenkædede lister - en enkelt linket liste - er en række noder, hvor hver enkelt node indeholder både en værdi og en markør til den næste node på listen.

Tilføjelser ( Tilføj ) udvider listen ved at tilføje varer til slutningen af ​​listen.

Fjernelse ( Fjern) fjernes altid fra en given position på listen.

Søgning ( Indeholder ) søger på listen efter en værdi.

Eksempel på brugssager:

  • Lagring af værdier i en hash-tabel for at forhindre kollisioner (mere om dette i et par indlæg)
  • Genskaber det fantastiske løb!

Lad os holde denne artikel pæn og let ved at arbejde på et værktøj, som CBS-netværket kan bruge til at planlægge deres næste fantastiske race-tv-show.

Når du går igennem dette, vil jeg gerne have, at du bliver ved med at spørge dig selv: ”Hvordan adskiller lister sig fra arrays? Hvordan er de ens? ”

Lad os komme igang.

Først skal du oprette repræsentationen af ​​vores linkede liste:

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

For at holde styr på startpunktet og slutpunktet for løbet opretter du egenskaber for hoved og hale.

Derefter opretter du en længdeegenskab og størrelsesmetode for at sikre, at du ikke gør løbet for langt eller for kort til sæsonen. På denne måde kan du altid holde styr på nøjagtigt hvor lang løbet er.

Nu hvor du har en måde at gemme løbslisten på, skal du oprette en måde at føje til denne liste. Spørgsmålet er, hvad tilføjer du specifikt?

Husk, at en linket liste er en række noder, hvor hver node har en værdi og en markør til den næste node på listen. Når du ved dette, indser du, at en node bare er et objekt med en værdi og næste egenskab.

Da du skal oprette en ny node, hver gang du føjer til listen, beslutter du at oprette en konstruktør, der gør det lettere at oprette en ny node for hver værdi, der føjes til din liste.

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

Når du har denne konstruktør tilgængelig, kan du oprette din tilføjelsesmetode.

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

Nu hvor du har tilføjet denne metode, vil du være i stand til at tilføje en masse placeringer til din Amazing Race-liste. Sådan ser det ud. Bemærk, at jeg har tilføjet noget ekstra hvidt rum for at gøre det lettere at forstå.

{ _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 }

Okay, så nu hvor du har oprettet denne liste og en måde at tilføje, indser du, at du vil have hjælp til at tilføje placeringer til denne liste, fordi du har Decidophobia (ja, det er en ting).

Du beslutter dig for at dele det med din kollega, Kent og bede ham om at tilføje et par steder mere. Det eneste problem er, at når du giver ham det, fortæller du ham ikke, hvilke steder du allerede har tilføjet. Desværre har du også glemt det efter at have lidt hukommelsestab forårsaget af beslutningsangst.

Selvfølgelig kunne han bare køre console.log (AmazingRace) og læse igennem, hvad konsollen udsender. Men Kent er en doven programmør og har brug for en måde at kontrollere, om der findes noget, så han kan forhindre duplikater. Med det i tankerne bygger du ud en indeholder- metode til at kontrollere for eksisterende værdier.

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

Awesome, nu har Kent en måde at kontrollere værdier på, før han tilføjer dem, for at undgå dubletter.

Som en sidebemærkning undrer du dig måske over, hvorfor du ikke bare brugte metoden indeholder i tilføjelsesmetoden for at forhindre dobbelt tilføjelser? Når du implementerer en linket liste - eller en hvilken som helst datastruktur for den sags skyld - kan du teoretisk tilføje den ekstra funktionalitet, du ønsker.

Du kan endda gå ind og ændre native metoder på eksisterende strukturer. Prøv nedenstående i en REPL:

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

Årsagen til, at vi ikke gør nogen af ​​disse ting, er på grund af aftalte standarder. I det væsentlige har udviklere en forventning om, hvordan bestemte metoder skal fungere.

Da vores sammenkædede listeklasse ikke er hjemmehørende i JavaScript, har vi mere frihed til at implementere den, men der er stadig grundlæggende forventninger til, hvordan datastrukturer som disse skal fungere. Tilknyttede lister gemmer ikke i sig selv unikke værdier. Men de har metoder som indeholder, der giver os mulighed for at præ-kontrollere og opretholde unikhed på vores liste.

Kent vender tilbage til dig med sin liste over destinationer, men nogle af dem er tvivlsomme. For eksempel er Nordpolen måske ikke det bedste Amazing Race destination.

Så du beslutter dig for at opbygge en metode for at kunne fjerne en node. Det er vigtigt at huske, at når du fjerner noden, fjerner du linket til listen og bliver nødt til at linke igen, hvad der kom før og efter den fjernede node.

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

There’s a lot of code in that remove function up there. Essentially it boils down to the following:

  1. if the value exists in the list…
  2. iterate over the linked list, keeping track of the previous and current node
  3. then, if there’s a match →

4A . if it’s the head

  • reset the head to the next node in the list
  • update the length
  • break out of the loop

4B. if it’s the tail

  • reset the tail to the previous node in the list
  • unlink the node by resetting the pointers as seen below

4C. If it’s not a match → continue iterating

  • make the next node current
  • make the current node previous

One last thing to note: you may have realized that you didn’t actually delete the node. You just removed the references to it. Well, that’s OK because once all references to an object are removed, the garbage collector helps us remove it from memory. You can read up on the garbage collection here.

With the remove method now implemented, you can run this little piece of code below to make sure contestants don’t freeze to death, or accidentally bother Santa as he’s prepping for this year’s festivities.

AmazingRace.remove('North Pole');

You’ve done it! You’ve created a simple implementation of a linked list. And you can grow the list by adding items, and shrink it by removing items — all based on the item’s value.

See if you can add you can expand the linked list to allow you to insert values at the beginning, end, or any point in between.

You have all you need to implement those methods. The names and arguments for these methods should look a little like this:

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

Feel free to share your implementations in the comments below ?

A time complexity analysis on the queue methods

Here’s the code again:

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){
}

Add is O(1): Since you always know the last item in the list thanks to tail property, you don’t have to iterate over the list.

Remove is O(n): In the worst case scenario you’re going to have to iterate over the entire list to find the value to be removed. Great part though is the actual removal of the node is O(1) because you’re just resetting pointers.

Contains is O(n): You have to iterate over the entire list to check if the value exists in your list.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

Endelig skrev Ian Elliot en gennemgang, der hjælper dig med at implementere alle metoderne. Men se om du kan implementere addHead () og insertAfter () til din linkede liste, før du kigger på dette?