Ако изучавате структури от данни, свързаният списък е една структура от данни, която трябва да знаете. Ако наистина не го разбирате или как е внедрен в 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
След това ще внедрим четири помощни метода за свързания списък. Те са:
- размер ()
- изчисти ()
- getLast ()
- 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. Също така обсъдихме различните видове свързани списъци, както и общите им предимства и недостатъци.
Надявам се да ви е харесало да го прочетете.
Искате ли да получавате известия, когато публикувам нова статия? Натисни тук.