Home-theater-designers
Gegevensstructuren zijn een fundamenteel aspect van informatica en programmeren, ongeacht de taal die u gebruikt. Een grondige kennis hiervan kan u helpen om gegevens efficiënt te organiseren, beheren, opslaan en wijzigen. Het identificeren van de juiste datastructuur voor uw use case kan de prestaties met een enorme marge verbeteren.
JavaScript wordt echter standaard alleen geleverd met primitieve gegevensstructuren zoals arrays en objecten. Maar met de introductie van ECMAScript 6 (ES6) klassen, kunt u nu aangepaste gegevensstructuren zoals stapels en wachtrijen maken met behulp van primitieve gegevensstructuren.
marges wijzigen in google docs
Gegevensstructuur stapelen
Met de stapelgegevensstructuur kunt u nieuwe gegevens op de bestaande gegevens op een LIFO-manier (last-in, first-out) pushen. Deze lineaire datastructuur is eenvoudig te visualiseren aan de hand van een eenvoudig voorbeeld. Beschouw een stapel borden op een tafel. U kunt alleen een bord aan de bovenkant van de stapel toevoegen of verwijderen.
Hier leest u hoe u de stapelgegevensstructuur kunt implementeren met behulp van JavaScript-arrays en: ES6 klassen :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Laten we enkele van de bewerkingen die u op een stapel kunt uitvoeren, onderzoeken en bouwen.
Drukbediening
De push-bewerking wordt gebruikt om nieuwe gegevens in de stapel in te voegen. U moet de gegevens als parameter doorgeven tijdens het aanroepen van de push-methode. Voordat de gegevens worden ingevoegd, wordt de bovenste aanwijzer van de stapel met één verhoogd en worden de nieuwe gegevens op de bovenste positie ingevoegd.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Pop-operatie
De pop-bewerking wordt gebruikt om het bovenste gegevenselement van de stapel te verwijderen. Tijdens het uitvoeren van deze bewerking wordt de bovenste aanwijzer met 1 verminderd.
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Peek-operatie
De peek-bewerking wordt gebruikt om de waarde bovenaan de stapel te retourneren. De tijdscomplexiteit voor het ophalen van deze gegevens is O(1).
Kom meer te weten: Wat is Big-O-notatie?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Gegevensstructuur gekoppelde lijst
Een gelinkte lijst is een lineaire datastructuur die bestaat uit een groot aantal knooppunten die met behulp van pointers met elkaar zijn verbonden. Elk knooppunt in de lijst bevat de gegevens en een aanwijzervariabele die naar het volgende knooppunt in de lijst verwijst.
Meer informatie: een inleiding tot aanwijzers voor programmeurs
In tegenstelling tot een stapel, vereisen implementaties van gekoppelde lijsten in JavaScript twee klassen. De eerste klas is de Knooppunt klasse voor het maken van een knooppunt, en de tweede klasse is de Gelinkte lijst class om alle bewerkingen op de gekoppelde lijst uit te voeren. De hoofdaanwijzer wijst naar het eerste knooppunt van de gekoppelde lijst en de staartaanwijzer wijst naar het laatste knooppunt van de gekoppelde lijst.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Hier zijn enkele primaire bewerkingen die u op een gekoppelde lijst kunt uitvoeren:
Bewerking toevoegen
De toevoegbewerking wordt gebruikt om een nieuw knooppunt toe te voegen aan het einde van de gekoppelde lijst. U moet de gegevens doorgeven als parameter voor het invoegen van een nieuw knooppunt. Maak eerst een nieuw knooppuntobject met behulp van de nieuwe trefwoord in JavaScript.
Als de gekoppelde lijst leeg is, wijzen zowel de kop- als de staartaanwijzer naar het nieuwe knooppunt. Anders wijst alleen de staartaanwijzer naar het nieuwe knooppunt.
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}Invoegbewerking
Om een nieuw knooppunt bij een bepaalde index in te voegen, kunt u gebruik maken van de invoegbewerking. Deze methode heeft twee parameters nodig: de gegevens die moeten worden ingevoegd en de index waarop ze moeten worden ingevoegd. In het ergste geval heeft deze methode een tijdcomplexiteit van O(N) omdat deze mogelijk de hele lijst moet doorlopen.
insert(data, index) {
if (index this.size) return undefined;
if (index === 0) {
this.head = new Node(data, this.head);
!this.tail ? (this.tail = this.head) : null;
this.size++;
return this;
}
if (index === this.size) return this.append(data);
let count = 0;
let beforeNode = this.head;
while (count !== index) {
beforeNode = beforeNode.next;
count++;
}
const newNode = new Node(data);
let afterNode = beforeNode.next;
newNode.next = afterNode;
beforeNode.next = newNode;
this.size++;
return this;
}Bewerking verwijderen
De verwijderbewerking doorloopt de gekoppelde lijst om de verwijzing te krijgen naar het knooppunt dat moet worden verwijderd en verwijdert de koppeling van het vorige knooppunt. Net als bij de invoegbewerking, heeft de verwijderbewerking in het ergste geval ook een tijdcomplexiteit van O(N).
deleteNode(index) {
if (index === 0) {
const removedHead = this.head;
this.head = this.head.next;
this.size--;
this.size === 0 ? (this.tail = null) : null;
return removedHead;
}
if (index === this.size - 1) {
if (!this.head) return undefined;
let currentNode = this.head;
let newTail = currentNode;
while (currentNode.next) {
newTail = currentNode;
currentNode = currentNode.next;
}
this.tail = newTail;
this.tail.next = null;
this.size--;
this.size === 0 ? ([this.head, this.tail] = [null, null]) : null;
return currentNode;
}
if (index this.size - 1) return undefined;
let count = 0;
let beforeNode = this.head;
while (count !== index - 1) {
beforeNode = beforeNode.next;
count++;
}
const removedNode = beforeNode.next;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
removedNode.next = null;
this.size--;
return removedNode;
}Gegevensstructuur in wachtrij
De wachtrijgegevensstructuur is vergelijkbaar met een groep mensen die in een wachtrij staan. De persoon die als eerste in de wachtrij komt, wordt eerder bediend dan anderen. Evenzo volgt deze lineaire gegevensstructuur de FIFO-benadering (first in, first out) om gegevens in te voegen en te verwijderen. Deze gegevensstructuur kan op deze manier opnieuw worden gemaakt in JavaScript met behulp van een gekoppelde lijst:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}U kunt als volgt gegevens invoegen en verwijderen uit een wachtrij in JavaScript:
hoe video's van websites te downloaden
In wachtrij plaatsen
De wachtrijbewerking voegt nieuwe gegevens in de wachtrij in. Als deze methode wordt aangeroepen en de wachtrijgegevensstructuur leeg is, wijzen zowel de voor- als achteraanwijzers naar het nieuw ingevoegde knooppunt in de wachtrij. Als de wachtrij niet leeg is, wordt het nieuwe knooppunt toegevoegd aan het einde van de lijst en wijst de achterste aanwijzer naar dit knooppunt.
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this;
}Operatie uit de wachtrij
De dequeue-bewerking verwijdert het eerste element in de wachtrij. Tijdens de dequeue-bewerking wordt de hoofdaanwijzer vooruit verplaatst naar het tweede knooppunt in de lijst. Dit tweede knooppunt wordt nu de kop van de wachtrij.
dequeue() {
if (!this.front) return undefined;
if (this.front === this.rear) this.rear = null;
const dequeuedNode = this.front;
this.front = this.front.next;
this.size--;
return dequeuedNode;
}De volgende stap na datastructuren
Gegevensstructuren kunnen een lastig concept zijn om te begrijpen, vooral als je nieuw bent in programmeren. Maar net als bij elke andere vaardigheid, kan oefening u helpen de efficiëntie die het biedt voor het opslaan en beheren van gegevens in uw toepassingen echt te begrijpen en te waarderen.
Algoritmen zijn net zo nuttig als datastructuren en kunnen de volgende logische stap in uw programmeerreis worden. Dus waarom niet beginnen met een sorteeralgoritme zoals bellensorteren?
Deel Deel Tweeten E-mail Een inleiding tot het bellensorteeralgoritmeHet Bubble Sort-algoritme: een uitstekende introductie tot het sorteren van arrays.
Lees volgende Gerelateerde onderwerpen- Programmeren
- JavaScript
- Programmeren
- Codeerhandleidingen
Nitin is een enthousiaste softwareontwikkelaar en een student computertechniek die webapplicaties ontwikkelt met behulp van JavaScript-technologieën. Hij werkt als freelance webontwikkelaar en schrijft in zijn vrije tijd graag voor Linux en Programmeren.
Meer van Nitin RanganathAbonneer op onze nieuwsbrief
Word lid van onze nieuwsbrief voor technische tips, recensies, gratis e-boeken en exclusieve deals!
Klik hier om je te abonneren