Home-theater-designers
Структурите на данните са основен аспект на компютърните науки и програмирането, независимо от езика, който използвате. Наличието на задълбочени познания за тях може да ви помогне ефективно да организирате, управлявате, съхранявате и променяте данни. Идентифицирането на правилната структура на данните за вашия случай на използване може да подобри производителността с огромен марж.
JavaScript обаче идва само с примитивни структури от данни като масиви и обекти по подразбиране. Но с въвеждането на класове ECMAScript 6 (ES6) вече можете да създавате персонализирани структури от данни като стекове и опашки с помощта на примитивни структури от данни.
бутонът за начало не работи iphone 8
Структура на стекови данни
Структурата на стекови данни ви позволява да избутвате нови данни върху съществуващите данни по начин LIFO (последно влизане, първо излизане). Тази линейна структура от данни е лесна за визуализация, като се използва прост пример. Помислете за куп чинии, държани на маса. Можете да добавяте или премахвате плоча само от горната част на купчината.
Ето как можете да внедрите структурата от стекови данни, използвайки JavaScript масиви и ES6 класове :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Нека разгледаме и изградим някои от операциите, които можете да извършите върху стека.
Операция с натискане
Операцията за натискане се използва за вмъкване на нови данни в стека. Трябва да предадете данните като параметър, докато извиквате метода push. Преди да вмъкнете данните, горният показалец на стека се увеличава с един, а новите данни се вмъкват в горната позиция.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Поп операция
Операцията поп се използва за премахване на най -горния елемент от данни на стека. Докато изпълнявате тази операция, горният показалец се намалява с 1.
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Peek Operation
Операцията peek се използва за връщане на стойността, присъстваща в горната част на стека. Времевата сложност за извличане на тези данни е O (1).
Научете повече: Какво е Big-O нотация?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Структура на данни от свързан списък
Свързан списък е линейна структура от данни, състояща се от множество възли, свързани помежду си с помощта на указатели. Всеки възел в списъка съдържа данните и променлива на показалеца, която сочи към следващия възел в списъка.
Научете повече: Въведение в указанията за програмисти
За разлика от стека, реализациите на свързани списъци в JavaScript изискват два класа. Първият клас е Възел клас за създаване на възел, а вторият клас е LinkedList class за изпълнение на всички операции в свързания списък. Указателят на главата сочи към първия възел на свързания списък, а показалецът към опашката сочи към последния възел на свързания списък.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Ето някои основни операции, които можете да извършите в свързан списък:
Операция за добавяне
Операцията за добавяне се използва за добавяне на нов възел в края на свързания списък. Трябва да предадете данните като параметър за вмъкване на нов възел. Първо, създайте нов обект на възел с помощта на нов ключова дума в JavaScript.
Ако свързаният списък е празен, и главата, и указателят на опашката ще сочат към новия възел. В противен случай само указателят на опашката ще сочи към новия възел.
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;
}Операция за вмъкване
За да вмъкнете нов възел в определен индекс, можете да използвате операцията за вмъкване. Този метод приема два параметъра: данните за вмъкване и индекса, при който те трябва да бъдат вмъкнати. В най -лошия случай този метод има времева сложност O (N), тъй като може да се наложи да премине през целия списък.
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;
}Операция за изтриване
Операцията за изтриване преминава през свързания списък, за да получи препратката към възела, който трябва да бъде изтрит, и премахва връзката на предишния възел. Подобно на операцията за вмъкване, операцията за изтриване също има времева сложност 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;
}Структура на данните на опашката
Структурата на данните на опашката е подобна на куп хора, стоящи на опашка. Лицето, което първо влезе в опашката, се обслужва преди другите. По подобен начин тази линейна структура от данни следва подхода на FIFO (първи вход, първи изход) за вмъкване и премахване на данни. Тази структура от данни може да бъде пресъздадена в JavaScript с помощта на свързан списък по следния начин:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Ето как можете да вмъквате и премахвате данни от опашка в JavaScript:
Windows xp безплатно изтегляне на пълната версия
Операция на опашката
Операцията enqueue вмъква нови данни в опашката. Докато извиквате този метод, ако структурата на данните на опашката е празна, предните и задните указатели сочат към ново вмъкнатия възел в опашката. Ако опашката не е празна, новият възел се добавя в края на списъка и задният показалец сочи към този възел.
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;
}Операция на опашката
Операцията dequeue премахва първия елемент от опашката. По време на операцията за подреждане показалецът на главата се премества напред към втория възел в списъка. Този втори възел сега става глава на опашката.
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;
}Следващата стъпка след структурите на данните
Структурите на данните могат да бъдат трудна концепция за разбиране, особено ако сте нови в програмирането. Но както всяко друго умение, практиката може да ви помогне наистина да разберете и оцените ефективността, която предоставя за съхранение и управление на данни във вашите приложения.
Алгоритмите са също толкова полезни, колкото структурите на данни и биха могли да се превърнат в следващата логическа стъпка във вашето програмиране. И така, защо не започнете с алгоритъм за сортиране, като сортиране на балончета?
Дял Дял Туит електронна поща Въведение в алгоритъма за сортиране на балончетаАлгоритъмът за сортиране на балончета: отлично въведение в сортиращите масиви.
Прочетете Напред Свързани теми- Програмиране
- JavaScript
- Програмиране
- Уроци по кодиране
Нитин е запален разработчик на софтуер и студент по компютърно инженерство, разработващ уеб приложения, използващи JavaScript технологии. Той работи като уеб разработчик на свободна практика и обича да пише за Linux и програмиране в свободното си време.
Още от Nitin RanganathАбонирайте се за нашия бюлетин
Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и изключителни оферти!
Щракнете тук, за да се абонирате