Якщо ви вивчаєте структури даних, зв’язаний список - це одна структура даних, яку ви повинні знати. Якщо ви насправді цього не розумієте або як це реалізовано в 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. Ми також обговорили різні типи пов'язаних списків, а також їх загальні переваги та недоліки.
Сподіваюся, вам сподобалось це читати.
Хочете отримувати повідомлення, коли я публікую нову статтю? Натисніть тут.