Как да приложите свързан списък в JavaScript

Програмиране

Ако изучавате структури от данни, свързаният списък е една структура от данни, която трябва да знаете. Ако наистина не го разбирате или как е внедрен в JavaScript, тази статия е тук, за да ви помогне.

В тази статия ще обсъдим какво е свързан списък, как се различава от масив и как да го внедрим в JavaScript. Да започваме.

Какво е свързан списък?

Свързаният списък е линейна структура от данни, подобна на масив. Въпреки това, за разлика от масивите, елементите не се съхраняват в определено място или индекс на паметта. По-скоро всеки елемент е отделен обект, който съдържа указател или връзка към следващия обект в този списък.

Всеки елемент (често наричан възли) съдържа два елемента: съхраняваните данни и връзка към следващия възел. Данните могат да бъдат всеки валиден тип данни. Можете да видите това илюстрирано на диаграмата по-долу.

Изображение на свързан списък

Входната точка към свързан списък се нарича глава. Главата е препратка към първия възел в свързания списък. Последният възел в списъка сочи към нула. Ако списъкът е празен, заглавката е нулева препратка.

В JavaScript свързан списък изглежда така:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

Предимство на свързаните списъци

  • Възлите могат лесно да бъдат премахнати или добавени от свързан списък, без да се реорганизира цялата структура на данните. Това е едно предимство, което има пред масивите.

Недостатъци на свързани списъци

  • Операциите за търсене са бавни в свързаните списъци. За разлика от масивите, случаен достъп до елементи от данни не е разрешен. Възлите се достъпват последователно, започвайки от първия възел.
  • Той използва повече памет, отколкото масиви, поради съхранението на указателите.

Видове свързани списъци

Има три типа свързани списъци:

  • Единично свързани списъци : Всеки възел съдържа само един указател към следващия възел. За това говорихме досега.
  • Двойно свързани списъци : Всеки възел съдържа два указателя, указател към следващия възел и указател към предишния възел.
  • Циркулярно свързани списъци : Циркулярно свързаните списъци са вариант на свързан списък, в който последният възел сочи към първия възел или който и да е друг възел преди него, като по този начин образува цикъл.

Внедряване на възел със списък в JavaScript

Както беше посочено по-рано, възел със списък съдържа два елемента: данните и указателя към следващия възел. Можем да приложим възел със списък в JavaScript, както следва:

class ListNode { constructor(data) { this.data = data this.next = null } }

Внедряване на свързан списък в JavaScript

Кодът по-долу показва изпълнението на свързан клас списък с конструктор. Забележете, че ако главният възел не бъде предаден, главата се инициализира до нула.

class LinkedList { constructor(head = null) { this.head = head } }

Събирайки всичко

Нека създадем свързан списък с току-що създадения клас. На първо място, ние създаваме две списък възли, node1и node2и показалец от връх 1 до възел 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

След това ще създадем свързан списък с node1.

let list = new LinkedList(node1)

Нека се опитаме да осъществим достъп до възлите в списъка, който току-що създадохме.

console.log(list.head.next.data) //returns 5

Някои методи на LinkedList

След това ще внедрим четири помощни метода за свързания списък. Те са:

  1. размер ()
  2. изчисти ()
  3. getLast ()
  4. getFirst ()

1. размер ()

Този метод връща броя на възлите, присъстващи в свързания списък.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; }

2. изчисти ()

Този метод изпразва списъка.

clear() { this.head = null; }

3. getLast ()

Този метод връща последния възел от свързания списък.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Този метод връща първия възел от свързания списък.

getFirst() { return this.head; }

Обобщение

В тази статия обсъдихме какво е свързан списък и как може да се приложи в JavaScript. Също така обсъдихме различните видове свързани списъци, както и общите им предимства и недостатъци.

Надявам се да ви е харесало да го прочетете.

Искате ли да получавате известия, когато публикувам нова статия? Натисни тук.