Implementacja połączonych list w JavaScript

Lista połączona to struktura danych bardzo podobna do tablicy, z wyjątkiem faktu, że dane nie są przechowywane w jednym miejscu pamięci. W JavaScript każdy element (węzeł) połączonej listy jest obiektem wskazującym na następny element (węzeł), który również wskazuje na następny element połączonej listy, dopóki ostatni element nie będzie wskazywał na nic (koniec połączonej listy) .

Punkt wejścia do połączonej listy nazywany jest głową. Głowa jest odniesieniem do pierwszego węzła na połączonej liście. Ostatni węzeł na liście wskazuje wartość null. Jeśli lista jest pusta, nagłówek jest odwołaniem o wartości null.

Obrazowo, najlepiej przeglądać połączone listy w następujący sposób;

Można to również postrzegać jako;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Music Player — Utwory w odtwarzaczu muzyki są połączone z poprzednimi i następnymi utworami. Możesz więc odtwarzać utwory z początku lub końca listy.
2. Przeglądarka obrazów — poprzednie i następne obrazy są połączone i można uzyskać do nich dostęp za pomocą przycisków następny i poprzedni.
3. Poprzednia i następna strona w przeglądarce internetowej — Możemy uzyskać dostęp do poprzedniego i następnego adresu URL wyszukiwanego w przeglądarce internetowej, naciskając przyciski Wstecz i Dalej, ponieważ są one połączone jako połączona lista.

Istnieją trzy główne rodzaje list połączonych, którymi są lista pojedynczo połączona, lista podwójnie połączona i lista połączona cyklicznie. Na potrzeby tej nauki będziemy wdrażać listę pojedynczo połączoną.

Jak wspomniano wcześniej, połączona lista jest po prostu kombinacją elementów (węzłów), które wskazują na siebie nawzajem. Podstawową jednostką połączonej listy jest węzeł. Węzeł zawiera dane i wskaźnik do następnego węzła, zaimplementowany w następujący sposób;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

Usunięcie węzła z połączonej listy jest realizowane poprzez usunięcie jego wskaźnika. Oznacza to, że poprzedni węzeł wskazujący na węzeł (do usunięcia) zostałby zmuszony do pominięcia węzła (do usunięcia), a tym samym do następnego węzła.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Mam nadzieję, że pomogło ci to w zrozumieniu połączonej listy i jej implementacji.

Jeśli potrzebujesz dalszych wyjaśnień, możesz skontaktować się ze mną na LinkedIn:https://www.linkedin.com/in/joshua-ajagbe/lub napisz do mnie na adres [email protected].

Miłej nauki