Datastrukturer är en grundläggande aspekt av datavetenskap och programmering, oavsett vilket språk du använder. Att ha en grundlig kunskap om dem kan hjälpa dig att effektivt organisera, hantera, lagra och ändra data. Att identifiera rätt datastruktur för ditt användningsfall kan förbättra prestandan med stor marginal.
JavaScript kommer dock bara med primitiva datastrukturer som arrayer och objekt som standard. Men med introduktionen av ECMAScript 6 (ES6)-klasser kan du nu skapa anpassade datastrukturer som stackar och köer med hjälp av primitiva datastrukturer.
Stack datastruktur
Stackdatastrukturen tillåter dig att skjuta ny data ovanpå befintlig data på ett LIFO-sätt (sist in, först ut). Denna linjära datastruktur är lätt att visualisera med ett enkelt exempel. Tänk på en bunt tallrikar som står på ett bord. Du kan bara lägga till eller ta bort en tallrik från toppen av högen.
Så här kan du implementera stackdatastrukturen med JavaScript-matriser och ES6-klasser:
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}
Låt oss utforska och bygga några av operationerna som du kan utföra på en stack.
Push Operation
Push-operationen används för att infoga ny data i stacken. Du måste skicka data som en parameter medan du anropar push-metoden. Innan data infogas ökas den översta pekaren i stacken med en och den nya datan infogas i den översta positionen.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}
Pop Operation
Pop-operationen används för att ta bort det översta dataelementet i stacken. När du utför denna operation minskas den övre pekaren med 1.
pop() {
if (this.top < 0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}
Peek Operation
Peek-operationen används för att returnera värdet som finns överst i stacken. Tidskomplexiteten för att hämta dessa data är O(1).
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}
Länkad listdatastruktur
En länkad lista är en linjär datastruktur som består av ett flertal noder kopplade till varandra med hjälp av pekare. Varje nod i listan innehåller data och en pekarvariabel som pekar på nästa nod i listan.
Till skillnad från en stack kräver implementeringar av länkade listor i JavaScript två klasser. Den första klassen är Nod klass för att skapa en nod, och den andra klassen är Länkad lista klass för att utföra alla operationer på den länkade listan. Huvudpekaren pekar på den första noden i den länkade listan, och slutpekaren pekar på den sista noden i den länkade listan.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
Här är några primära operationer som du kan utföra på en länkad lista:
Lägg till Operation
Append-operationen används för att lägga till en ny nod i slutet av den länkade listan. Du måste skicka data som en parameter för att infoga en ny nod. Skapa först ett nytt nodobjekt med hjälp av ny nyckelord i JavaScript.
Om den länkade listan är tom kommer både huvud- och svanspekaren att peka på den nya noden. Annars kommer bara svanspekaren att peka på den nya noden.
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;
}
Insättningsoperation
För att infoga en ny nod vid ett visst index kan du använda infogningsoperationen. Den här metoden kräver två parametrar: data som ska infogas och index vid vilket den ska infogas. I värsta fall har denna metod en tidskomplexitet på O(N) eftersom den kan behöva gå igenom hela listan.
insert(data, index) {
if (index < 0 || 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;
}
Ta bort operation
Raderingsoperationen går igenom den länkade listan för att få referensen till den nod som ska raderas och tar bort länken till den föregående noden. I likhet med infogningsoperationen har raderingsoperationen också en tidskomplexitet på O(N) i värsta fall.
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 < 0 || 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;
}
Ködatastruktur
Ködatastrukturen liknar ett gäng människor som står i en kö. Den som kommer först i kön serveras före andra. På liknande sätt följer denna linjära datastruktur FIFO-metoden (först in, först ut) för att infoga och ta bort data. Denna datastruktur kan återskapas i JavaScript med hjälp av en länkad lista på detta sätt:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}
Så här kan du infoga och ta bort data från en kö i JavaScript:
Ködrift
Enqueue-operationen infogar ny data i kön. Medan den här metoden anropas, om ködatastrukturen är tom, pekar både de främre och bakre pekarna på den nyligen infogade noden i kön. Om kön inte är tom läggs den nya noden till i slutet av listan och den bakre pekaren pekar på denna nod.
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;
}
Ködrift
Avköningsoperationen tar bort det första elementet i kön. Under avköningsoperationen flyttas huvudpekaren framåt till den andra noden i listan. Denna andra nod blir nu huvudet i kön.
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;
}
Nästa steg efter datastrukturer
Datastrukturer kan vara ett knepigt koncept att förstå, särskilt om du är ny på programmering. Men precis som alla andra färdigheter kan övning hjälpa dig att verkligen förstå och uppskatta effektiviteten det ger för att lagra och hantera data i dina applikationer.
Algoritmer är lika användbara som datastrukturer och kan bli nästa logiska steg i din programmeringsresa. Så varför inte börja med en sorteringsalgoritm som bubbelsortering?
Om författaren
Nitin Ranganath (39 artiklar publicerade)
Nitin är en ivrig mjukvaruutvecklare och en datoringenjörsstudent som utvecklar webbapplikationer med JavaScript-teknik. Han arbetar som frilansande webbutvecklare och gillar att skriva för Linux och programmering i sin free tid.
Mer från Nitin Ranganath
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
