Home-theater-designers
Structurile de date sunt un aspect fundamental al informaticii și al programării, indiferent de limbajul pe care îl utilizați. Cunoașterea aprofundată a acestora vă poate ajuta să organizați, să gestionați, să stocați și să modificați în mod eficient datele. Identificarea structurii de date adecvate pentru cazul dvs. de utilizare poate îmbunătăți performanța cu o marjă imensă.
Cu toate acestea, JavaScript vine doar cu structuri de date primitive, cum ar fi matrici și obiecte în mod implicit. Dar odată cu introducerea claselor ECMAScript 6 (ES6), puteți crea acum structuri de date personalizate, cum ar fi stive și cozi, cu ajutorul structurilor de date primitive.
vizionați filme gratuite fără înregistrări sau descărcare
Structura datelor stivei
Structura de date a stivei vă permite să împingeți date noi deasupra datelor existente într-un mod LIFO (ultima intrare, prima ieșire). Această structură de date liniară este ușor de vizualizat folosind un exemplu simplu. Luați în considerare un teanc de farfurii păstrate pe o masă. Puteți adăuga sau elimina o placă numai din partea superioară a stivei.
Iată cum puteți implementa structura de date a stivei utilizând matricele JavaScript și Clase ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Să explorăm și să construim câteva dintre operațiile pe care le puteți efectua pe un teanc.
Operațiunea Push
Operația de împingere este utilizată pentru a insera date noi în stivă. Trebuie să transmiteți datele ca parametru în timp ce apelați metoda push. Înainte de a insera datele, indicatorul superior al stivei este incrementat cu unul, iar noile date sunt inserate în poziția de sus.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Operație Pop
Operația pop este utilizată pentru a elimina elementul de date de sus al stivei. În timpul efectuării acestei operații, indicatorul superior este redus cu 1.
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Operațiunea Peek
Operațiunea peek este utilizată pentru a returna valoarea prezentă în partea de sus a stivei. Complexitatea de timp pentru recuperarea acestor date este O (1).
Aflați mai multe: Ce este notația Big-O?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Structura de date a listei legate
O listă legată este o structură de date liniară formată din numeroase noduri conectate între ele cu ajutorul pointerilor. Fiecare nod din listă conține datele și o variabilă de pointer care indică următorul nod din listă.
Aflați mai multe: o introducere în indicatori pentru programatori
Spre deosebire de o stivă, implementările listelor legate în JavaScript necesită două clase. Prima clasă este Nodul clasa pentru crearea unui nod, iar a doua clasă este LinkedList clasa pentru a efectua toate operațiunile de pe lista legată. Pointerul cap indică primul nod al listei conectate, iar indicatorul coadă indică ultimul nod al listei conectate.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Iată câteva operații principale pe care le puteți efectua pe o listă legată:
Atașați operațiunea
Operațiunea de adăugare este utilizată pentru a adăuga un nou nod la sfârșitul listei conectate. Trebuie să transmiteți datele ca parametru pentru inserarea unui nou nod. În primul rând, creați un nou obiect nod folosind nou cuvânt cheie în JavaScript.
Dacă lista legată este goală, atât indicatorul cap, cât și indicatorul coadă vor indica spre noul nod. În caz contrar, doar indicatorul cozii va indica noul nod.
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;
}Operațiunea de inserare
Pentru a insera un nod nou la un anumit index, puteți utiliza operația de inserare. Această metodă ia doi parametri: datele de inserat și indexul la care urmează să fie inserat. În cel mai rău caz, această metodă are o complexitate temporală de O (N), deoarece poate fi necesar să traverseze întreaga listă.
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;
}Ștergeți operațiunea
Operația de ștergere parcurge lista conectată pentru a obține referința la nodul care urmează să fie șters și elimină legătura nodului anterior. Similar operației de inserare, operația de ștergere are, de asemenea, o complexitate de timp de O (N) în cel mai rău caz.
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;
}Structura datelor cozii
Structura datelor cozii este similară cu o grămadă de oameni care stau în coadă. Persoana care intră prima în coadă este servită înaintea altora. În mod similar, această structură de date liniară urmează abordarea FIFO (primul intrat, primul ieșit) pentru a insera și a elimina date. Această structură de date poate fi recreată în JavaScript folosind o listă legată în acest mod:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Iată cum puteți insera și elimina date dintr-o coadă în JavaScript:
cum să ecranizați înregistrarea cu sunet
Operațiunea cu stânga
Operațiunea de coadă inserează date noi în coadă. În timp ce apelați această metodă, dacă structura de date a cozii este goală, atât indicatorii din față, cât și cei din spate indică nodul nou introdus în coadă. Dacă coada nu este goală, noul nod este adăugat la sfârșitul listei și indicatorul din spate indică acest 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;
}Operațiunea de așteptare
Operațiunea de coadă elimină primul element din coadă. În timpul operației dequeue, indicatorul principal este deplasat înainte la al doilea nod din listă. Acest al doilea nod devine acum capul cozii.
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;
}Pasul următor după structuri de date
Structurile de date pot fi un concept dificil de înțeles, mai ales dacă sunteți nou în programare. Dar, la fel ca orice altă abilitate, practica vă poate ajuta să înțelegeți și să apreciați cu adevărat eficiența pe care o oferă pentru stocarea și gestionarea datelor în aplicațiile dvs.
Algoritmii sunt la fel de utili ca structurile de date și ar putea deveni următorul pas logic în călătoria dvs. de programare. Deci, de ce nu începeți cu un algoritm de sortare, cum ar fi sortarea cu bule?
Acțiune Acțiune Tweet E-mail O introducere în algoritmul de sortare cu buleAlgoritmul Bubble Sort: o introducere excelentă în matricile de sortare.
Citiți în continuare Subiecte asemănătoare- Programare
- JavaScript
- Programare
- Tutoriale de codare
Nitin este un dezvoltator avid de software și un student în ingineria computerelor care dezvoltă aplicații web folosind tehnologii JavaScript. Lucrează ca dezvoltator web independent și îi place să scrie pentru Linux și Programare în timpul liber.
Mai multe de la Nitin RanganathAboneaza-te la newsletter-ul nostru
Alăturați-vă newsletter-ului pentru sfaturi tehnice, recenzii, cărți electronice gratuite și oferte exclusive!
Faceți clic aici pentru a vă abona