Jak zaimplementować połączoną strukturę danych listy w JavaScript?

JavaScript to język programowania internetowego, który służy do uczynienia naszych stron internetowych i aplikacji internetowych dynamicznym i interaktywnym, dając im możliwość myślenia i działania. Jak każdy inny język programowania, JavaScript oferuje nam tablice, które są zbiorem różnych elementów przechowywanych w jednej zmiennej. Ograniczenie tablicy polega na tym, że jest ona przechowywana kolejno w określonej pamięci w naszym systemie, a tym samym w celu rozwiązania tego problemu używamy linkowanej listy.

Połączona lista

Połączone listy są jak tablice, z wyjątkiem tego, że na połączonej liście elementy nie są zapisywane w określonej lokalizacji lub indeksie pamięci, a każdy element jest osobnym niezależnym obiektem podłączonym do następnego elementu poprzez posiadanie wskaźnika lub linku do tego elementu.

Każda powiązana lista zawiera głowę (pierwszy węzeł), długość (rozmiar linkowanej listy) i właściwość ogona (ostatni węzeł), a każdy element na połączonej liście nazywa się węzłem, a każdy węzeł ma wartość przechowywaną w nim i link do następnego węzła. Jeśli bieżącym węzłem jest ogon, link będzie zerowy, który nie wskazuje na żaden inny węzeł. Połączona lista nie zawiera indeksów w przeciwieństwie do tablic, które mają indeksy E.G 0,1,2… i tak dalej.

Połączone listy w JavaScript można wykazać w następujący sposób:

// Połączona lista
const linkedList =
// Każdy węzeł ma wartość i wskaźnik
// Pierwszy wskaźnik to nagłówek
głowa:
Wartość: 6
Następny:
Wartość: 10
Następny:
Wartość: 12
Następny:
Wartość: 3
Dalej: Null





;

Zaletą listy powiązanej polega na tym, że elementy (węzły) są łatwo dodawane i usuwane z listy połączonej bez regulacji całej listy połączonej. Wadą połączonej listy jest to, że potrzebuje ona więcej pamięci do przechowywania, ponieważ teraz mamy dodatkowy wskaźnik, który przechowujemy wraz z wartością elementu.

Połączone listy to trzy typy, które opisano poniżej:

• Lista pojedynczo połączona ma tylko jeden wskaźnik wskazujący na węzeł obok niego.
• Podwójnie połączone opiera się na dwóch punktach, w których pierwszy wskazuje za węzłem, który jest za nim, a drugi wskazuje na węzeł obok.
• Okrągła lista połączona, której ogon zawiera wskaźnik do głowy, a zatem tworzy cykl.

Wdrożenie listy powiązanej

Najpierw utwórzmy węzeł, który ma dwie właściwości wartość i wskaźnik, dla której utworzymy klasę o nazwie ListNode to ma te dwie właściwości:

Klasy ListNode
konstruktor (wartość)
Ten.wartość = wartość
Ten.Dalej = NULL

Teraz, gdy wiemy, jak utworzyć węzeł, pozwól nam utwórz powiązaną listę, w której domyślna wartość głowy będzie null:

klasa LinkedList
konstruktor (head = null)
Ten.głowa = głowa

Zainicjujmy teraz linkowaną listę z dwoma węzłami i dodajmy wskaźnik z głowy lub węzła 1 do drugiego węzła:

var node1 = new ListNode (3);
var node2 = new ListNode (4);
Node1.następny = node2;

Następnym krokiem jest zainicjowanie połączonej listy z Node1 w następujący sposób:

var list = new LinkedList (Node1);

Cały kod jest podany poniżej z rejestrowaniem konsoli wartości Node2:

// Tworzenie węzła
Klasy ListNode
konstruktor (wartość)
// konstruktor inicjalizujący wartość i następny wskaźnik
Ten.wartość = wartość
Ten.Dalej = NULL


klasa LinkedList
// Constructor List Lists
konstruktor (head = null)
Ten.głowa = głowa


// Inicjowanie utworzonych węzłów
var node1 = new ListNode (3);
var node2 = new ListNode (4);
Node1.następny = node2;
// Inicjowanie listy powiązanych
var list = new LinkedList (Node1);
// wyświetlanie wyjściowych drugiego węzła
konsola.log (lista.głowa.Następny.wartość) // 4

Połączone metody listy

Teraz, gdy skończymy wdrożeniem listy powiązanej, odtwarzajmy lub manipulujmy powiązaną listą, wdrażając więcej metod korzystania z powiązanych list (metody pomocnicze):

Pierwsza metoda pomocnicza, którą zdefiniujemy rozmiar() Metoda w klasie Połączona lista który zwróci długość linkowanej listy:

size = () =>
Niech liczy = 0;
Niech Node = to.głowa;
// pętla do iteracji listy powiązanych
while (węzeł)
count ++;
węzeł = węzeł.Następny

powrót;

W tym kodzie najpierw deklarujemy zmienną fikcyjną liczyć przechowywanie w nim 0, a następnie przechowywanie wskaźnika głowy w węzeł zmienny. Następnie zadeklarowaliśmy pętlę, która będzie iterowana przez połączoną listę i zwiększy liczyć zmienny.

Następną metodą pomocnika będzie getFirst () Metoda, w której wskaźnik główny zostanie zwrócony:

getFirst = () =>
Zwróć to.głowa.wartość;

Możemy również uzyskać ostatni węzeł linkowanej listy w następujący sposób:

getLast = () =>
Niech LastNode = to.głowa;
if (lastNode)
While (LastNode.Następny)
LastNode = LastNode.Następny


zwróć LastNode.wartość

Cały kod jest teraz podany poniżej z wyświetlaniem wyjścia drugiego węzła, rozmiarem powiązanej listy, pierwszej wartości węzła i ostatniej wartości węzła w tej samej kolejności:

// Tworzenie węzła
Klasy ListNode
konstruktor (wartość)
Ten.wartość = wartość
Ten.Dalej = NULL


// Tworzenie listy powiązanych
klasa LinkedList
konstruktor (head = null)
Ten.głowa = głowa

size = () =>
Niech liczy = 0;
Niech Node = to.głowa;
// pętla do iteracji listy powiązanych
while (węzeł)
count ++;
węzeł = węzeł.Następny

powrót;

getFirst = () =>
Zwróć to.głowa.wartość;

getLast = () =>
Niech LastNode = to.głowa;
if (lastNode)
While (LastNode.Następny)
LastNode = LastNode.Następny


zwróć LastNode.wartość


// Inicjowanie utworzonych węzłów
var node1 = new ListNode (3);
var node2 = new ListNode (4);
Node1.następny = node2;
// Inicjowanie listy powiązanych
var list = new LinkedList (Node1);
// wyświetlanie wyjściowych drugiego węzła
konsola.Log („Wartość drugiego węzła:”, lista.głowa.Następny.wartość) // 4
// Pokazanie rozmiaru linkowanej listy
konsola.Log („Rozmiar linkowanej listy:”, lista.rozmiar());
// Pokazanie pierwszej wartości węzła
konsola.Log („Pierwsza wartość węzła:”, lista.getFirst ());
// pokazanie ostatniej wartości węzła
konsola.log („Wartość ostatniego węzła:”, lista.getLast ());

Wniosek

Po tablicach połączona lista jest drugą najczęściej używaną strukturą danych w dowolnym języku programowania. Połączona lista jest jak tablica, która przechowuje zbiór różnych elementów z różnicą, że każdy element (węzeł) połączonej listy jest obiektem zawierającym wartość elementu i wskaźnik wskazujący następny węzeł, stąd łączenie każdego elementu i Druga różnica polega na tym, że elementy nie są zapisywane w określonej lokalizacji pamięci na połączonej liście.

W tym poście widzieliśmy, jakie są powiązane listy, zalety i wady powiązanych list, typy powiązanych list i jak zaimplementować powiązaną strukturę danych w JavaScript.