Як реалізувати зв’язаний список у 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. Ми також обговорили різні типи пов'язаних списків, а також їх загальні переваги та недоліки.

Сподіваюся, вам сподобалось це читати.

Хочете отримувати повідомлення, коли я публікую нову статтю? Натисніть тут.