Home-theater-designers
Dátové štruktúry sú základným aspektom informatiky a programovania bez ohľadu na jazyk, ktorý používate. Ich dôkladná znalosť vám môže pomôcť efektívne organizovať, spravovať, ukladať a upravovať údaje. Identifikácia správnej dátovej štruktúry pre váš prípad použitia môže výrazne zvýšiť výkon.
JavaScript však štandardne obsahuje iba primitívne dátové štruktúry, ako sú polia a objekty. Ale so zavedením tried ECMAScript 6 (ES6) teraz môžete vytvárať vlastné dátové štruktúry, ako sú zásobníky a fronty, pomocou primitívnych dátových štruktúr.
prečítajte si pevný disk mac v systéme Windows
Štruktúra údajov zásobníka
Štruktúra zásobníkových údajov vám umožňuje posúvať nové údaje nad existujúce údaje spôsobom LIFO (posledný vstup, prvý výstup). Túto lineárnu dátovú štruktúru je možné ľahko zobraziť na jednoduchom príklade. Uvažujte o stohu tanierov položených na stole. Platňu môžete pridať alebo odstrániť iba z hornej časti stohu.
Tu je návod, ako môžete implementovať štruktúru údajov zásobníka pomocou polí JavaScript a Triedy ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Poďme preskúmať a zostaviť niektoré z operácií, ktoré môžete vykonať na zásobníku.
Operácia tlačenia
Operácia push sa používa na vloženie nových údajov do zásobníka. Pri volaní metódy push musíte údaje odovzdať ako parameter. Pred vložením údajov sa horný ukazovateľ stohu zvýši o jednu a nové údaje sa vložia do hornej polohy.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Popová operácia
Operácia pop sa používa na odstránenie horného dátového prvku zo zásobníka. Pri tejto operácii sa horný ukazovateľ zníži o 1.
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Operácia Peek
Operácia peek sa používa na vrátenie hodnoty prítomnej v hornej časti zásobníka. Časová náročnosť získavania týchto údajov je O (1).
Uč sa viac: Čo je to Big-O notácia?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Štruktúra údajov prepojeného zoznamu
Prepojený zoznam je lineárna dátová štruktúra pozostávajúca z mnohých uzlov, ktoré sú navzájom prepojené pomocou ukazovateľov. Každý uzol v zozname obsahuje údaje a premennú ukazovateľa, ktorá ukazuje na nasledujúci uzol v zozname.
Zistite viac: Úvod do ukazovateľov pre programátorov
Na rozdiel od zásobníka vyžadujú implementácie prepojeného zoznamu v JavaScripte dve triedy. Prvá trieda je Uzol trieda na vytvorenie uzla a druhá trieda je LinkedList triedy na vykonanie všetkých operácií v prepojenom zozname. Hlavný ukazovateľ ukazuje na prvý uzol prepojeného zoznamu a chvostový ukazovateľ ukazuje na posledný uzol prepojeného zoznamu.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Tu je niekoľko primárnych operácií, ktoré môžete vykonávať v prepojenom zozname:
Pripojiť operáciu
Operácia pripojenia sa používa na pridanie nového uzla na koniec prepojeného zoznamu. Údaje musíte odovzdať ako parameter na vloženie nového uzla. Najprv vytvorte nový objekt uzla pomocou Nový kľúčové slovo v JavaScripte.
Ak je prepojený zoznam prázdny, ukazovateľ hlavy aj chvosta bude ukazovať na nový uzol. V opačnom prípade bude na nový uzol ukazovať iba chvostový ukazovateľ.
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;
}Vložiť operáciu
Ak chcete vložiť nový uzol do konkrétneho indexu, môžete použiť operáciu vloženia. Táto metóda vyžaduje dva parametre: vložené údaje a index, do ktorého sa majú vložiť. V najhoršom prípade má táto metóda časovú zložitosť O (N), pretože bude pravdepodobne musieť prejsť celým zoznamom.
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;
}Odstrániť operáciu
Operácia odstránenia prechádza prepojeným zoznamom, aby získala odkaz na uzol, ktorý sa má odstrániť, a odstráni prepojenie predchádzajúceho uzla. Podobne ako pri operácii vkladania, aj operácia vymazania má v najhoršom prípade časovú náročnosť 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;
}Štruktúra údajov frontu
Štruktúra údajov frontu je podobná skupine ľudí stojacich vo fronte. Osoba, ktorá vstúpi do poradia ako prvá, je obsluhovaná pred ostatnými. Podobne táto lineárna dátová štruktúra dodržiava prístup FIFO (prvý dovnútra, prvý von) na vkladanie a odstraňovanie údajov. Túto dátovú štruktúru je možné znova vytvoriť v JavaScripte pomocou prepojeného zoznamu týmto spôsobom:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Tu je návod, ako môžete vkladať a odstraňovať údaje z frontu v jazyku JavaScript:
ako resetovať imessage na mac
Operácia zaradenia
Operácia zaradenia vkladá nové údaje do frontu. Ak je pri volaní tejto metódy prázdna dátová štruktúra frontu, predný aj zadný ukazovateľ smerujú na novo vložený uzol vo fronte. Ak front nie je prázdny, nový uzol sa pridá na koniec zoznamu a zadný ukazovateľ ukáže na tento uzol.
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;
}Prevádzka odstávky
Operácia odstránenia poradia odstráni prvý prvok vo fronte. Počas operácie vyraďovania sa ukazovateľ hlavy presunie dopredu k druhému uzlu v zozname. Tento druhý uzol sa teraz stáva vedúcim frontu.
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;
}Ďalší krok po dátových štruktúrach
Dátové štruktúry môžu byť chúlostivým konceptom, najmä ak s programovaním začínate. Ale ako každá iná zručnosť, aj táto prax vám môže skutočne pomôcť porozumieť a oceniť účinnosť, ktorú poskytuje pri ukladaní a správe údajov vo vašich aplikáciách.
Algoritmy sú rovnako užitočné ako dátové štruktúry a mohli by sa stať ďalším logickým krokom na vašej ceste programovania. Prečo teda nezačať s triediacim algoritmom, akým je napríklad triedenie podľa bublín?
zdieľam zdieľam Tweet E -mail Úvod do algoritmu triedenia bublínAlgoritmus Bubble Sort: vynikajúci úvod do triediacich polí.
Čítajte ďalej Súvisiace témy- Programovanie
- JavaScript
- Programovanie
- Návody na kódovanie
Nitin je vášnivý vývojár softvéru a študent počítačového inžinierstva vyvíjajúci webové aplikácie pomocou technológií JavaScript. Pracuje ako webový vývojár na voľnej nohe a vo voľnom čase rád píše pre Linux a programovanie.
Viac od Nitina Ranganathaprihlásiť sa ku odberu noviniek
Pripojte sa k nášmu bulletinu a získajte technické tipy, recenzie, bezplatné elektronické knihy a exkluzívne ponuky!
Kliknutím sem sa prihlásite na odber