Więc powiedz mi o połączonych listach
Niedawno ukończyłem programowanie na bootcampie i zagłębiłem się w studiowanie struktur danych i algorytmów, aby poszerzyć moją podstawową wiedzę. Listy połączone są stosunkowo prostą strukturą danych, ale stanowią podstawę dla bardziej złożonych struktur danych. W tym artykule omówimy listy połączone - ich mocne i słabe strony oraz sposób ich wdrażania.
Struktury danych to, w uproszczeniu, sposoby organizacji i efektywnego przechowywania danych
Co to są struktury danych?
Struktury danych to w uproszczeniu sposoby porządkowania i efektywnego przechowywania danych. Umożliwiają one nam przechowywanie informacji, abyśmy mogli uzyskać do nich dostęp w późniejszym czasie - wyszukując określony element lub sortując je w celu uzyskania określonej kolejności, a nawet zarządzając dużymi zbiorami danych. JavaScript ma struktury danych, które prawdopodobnie dobrze znasz - tablice i obiekty. Są to prymitywne struktury danych, które są rodzime dla języka. Nieprymitywne struktury danych to struktury danych zdefiniowane przez programistę. Przykłady obejmują stosy, kolejki, drzewa, wykresy i tabele skrótów.
Co to są listy połączone?
Lista połączona to liniowa struktura danych, która zawiera elementy w kolejności sekwencyjnej. Brzmi znajomo? Są podobne do tablic, ale nie są takie same. Tablice są indeksowane przez zero , co oznacza, że każdy indeks jest odwzorowywany na wartość, a pierwszy element tablicy zaczyna się od indeksu 0. Możesz łatwo wyciągnąć elementy z tablicy, o ile znasz indeks.
Z drugiej strony połączona lista składa się z węzłów wskazujących na inne węzły. Każdy węzeł zna tylko siebie i następny węzeł. W ramach liniowej struktury danych elementy są uporządkowane. Można o tym myśleć jak o pociągu - każdy wagon jest połączony z następnym i tak dalej. Połączone listy nie są indeksowane , więc nie można uzyskać bezpośredniego dostępu do piątego elementu. Musiałbyś zacząć od początku, przejść do następnego i przejść do następnego, aż znajdziesz piąty element. Pierwszy węzeł to głowa, a ostatni - ogon. Istnieją różne typy list połączonych - lista połączona pojedynczo, lista połączona podwójnie i lista połączona cyklicznie. Ze względu na ten artykuł skoncentruję się na liście pojedynczo połączonej.
Dostęp do elementów w całej tablicy jest łatwiejszy, ale wiąże się to z pewnymi kosztami.
Po co używać list połączonych zamiast tablic?
Możesz się zastanawiać - ale po co tego używać, jeśli mogę uzyskać dostęp do elementów bezpośrednio za pomocą tablic? To prawda! Dostęp do elementów w całej tablicy jest łatwiejszy, ale wiąże się to z pewnymi kosztami.
Tablice są indeksowane - więc za każdym razem, gdy trzeba usunąć element z początku lub środka, wszystkie poniższe indeksy muszą zostać przesunięte. Dotyczy to również sytuacji, gdy trzeba wstawić element - wszystkie kolejne elementy muszą zostać ponownie zindeksowane. Podczas wstawiania lub usuwania elementów z połączonej listy nie musisz ponownie indeksować - wszystko, o co go obchodzi, to węzeł, na który wskazuje .
Implementacja listy połączonej pojedynczo
Istnieją różne typy list połączonych - pojedynczo, podwójnie i cyklicznie. Listy pojedynczo połączone to typ listy połączonej, w której każdy węzeł ma wartość i wskaźnik do następnego węzła (null, jeśli jest węzłem końcowym). Z drugiej strony, listy podwójnie połączone mają dodatkowy wskaźnik do poprzedniego węzła. Na listach połączonych kołowo węzeł końcowy wskazuje z powrotem na węzeł główny.
Uwaga: Jeśli jesteś wizualnym uczniem, VisuAlgo to świetne miejsce do zabawy i obserwowania, jak struktura danych przechodzi zmiany.
Jeśli chcesz pominąć cały kod: zapoznaj się z tym streszczeniem GitHub .
Tworzenie węzła
Zacznijmy od zbudowania węzła do użycia. Będzie miał wartość i następny wskaźnik, który wskaże kolejnego sąsiada.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Zaczniemy od zbudowania klasy o nazwie SinglyLinkedList i podamy jej podstawę dla początku, końca i długości listy.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Aby dodać węzeł na końcu, sprawdzimy, czy na liście jest już zadeklarowana głowa. Jeśli nie, ustaw głowę i ogon jako nowo utworzony węzeł. Jeśli już istnieje właściwość head, ustaw następną właściwość na końcu na nowy węzeł, a właściwość tail na nowy węzeł. Zwiększymy długość o 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Aby usunąć węzeł na końcu, musimy najpierw sprawdzić, czy na liście znajdują się węzły. Jeśli istnieją węzły, musimy przeglądać listę, aż dojdziemy do końca. Ustawimy następną właściwość przedostatniego węzła na wartość null, ustawimy właściwość tail na ten węzeł, zmniejszymy długość o 1 i zwrócimy wartość usuniętego węzła.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Aby usunąć węzeł od początku, sprawdzamy, czy na liście są węzły. Bieżącą właściwość head będziemy przechowywać w zmiennej i ustawimy head jako następny węzeł aktualnej głowy. Zmniejsz długość o 1 i zwróć wartość usuniętego węzła.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Aby dodać węzeł na początku, najpierw tworzymy węzeł i sprawdzamy, czy na liście znajduje się właściwość head. Jeśli tak, ustaw następną właściwość nowo utworzonego węzła na bieżącą głowę, ustaw głowę na nowy węzeł i zwiększ długość.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Aby uzyskać dostęp do węzła na podstawie jego pozycji na liście, najpierw sprawdzimy, czy indeks jest prawidłowym indeksem. Następnie przejdziemy przez listę, zachowując zmienną licznika. Gdy zmienna licznika pasuje do indeksu, zwrócimy znaleziony węzeł
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Aby zmienić węzeł na podstawie jego pozycji, najpierw znajdujemy węzeł za pomocą metody get i ustawiamy wartość na nową wartość.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Aby wstawić węzeł, najpierw sprawdzamy indeks. Jeśli jest równe 0, używamy naszej metody unshift. Jeśli jest równy długości, wypychamy go na listę. W przeciwnym razie otrzymamy węzeł przed, używając metody get o jeden mniej niż indeks. Zasadniczo musimy śledzić węzeł przed i po wybranym indeksie, aby upewnić się, że nasze wskaźniki są skierowane do właściwego węzła.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Aby usunąć węzeł na podstawie pozycji, ponownie użyjemy naszej metody get i zastosujemy tę samą zasadę, której używaliśmy do wstawiania węzła. Śledząc węzeł przed wybranym indeksem, możemy manewrować naszymi wskaźnikami.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Mocne strony list połączonych
Zaletą korzystania z listy połączonej jest możliwość szybkiego wstawiania i usuwania elementów. Ponieważ listy połączone nie są indeksowane, wstawianie elementów jest stosunkowo szybkie i łatwe.
Dodanie na końcu połączonej listy wymaga po prostu, aby stary koniec wskazywał na nowy węzeł, a właściwość końca była ustawiona na nowy węzeł. Dodawanie na początek połączonej listy jest tym samym założeniem, ale nowy węzeł wskazuje na stary węzeł, a właściwość head jest ustawiona na nowy węzeł. Zasadniczo te same działania, więc wstawienie to O (1).
Uwaga: Wstawienie w środku połączonej listy wymaga przeszukania w celu znalezienia węzła (O (N)), a następnie wstawienia węzła (O (1)).
Usunięcie węzła z połączonej listy może być łatwe… ale też nie. To zależy od tego, gdzie. Usunięcie węzła z początku listy jest proste - drugi węzeł staje się nową głową, a następny wskaźnik starej głowy ustawiamy na zero. Usunięcie z końca jest trudniejsze, ponieważ wymaga przejrzenia całej listy i zatrzymania się na przedostatnim węźle. Najgorszy przypadek O (N), a najlepszy przypadek O (1).
Wady list połączonych
Słabe strony połączonej listy są spowodowane brakiem ponownego indeksowania. Ponieważ nie można uzyskać bezpośredniego dostępu do elementów, utrudnia to wyszukiwanie i dostęp do elementów.
Wyszukiwanie i uzyskiwanie dostępu do węzła na połączonej liście wymaga rozpoczęcia od początku listy i podążania ścieżką nawigacyjną w dół listy. Jeśli szukamy węzła na końcu listy, będziemy musieli przejść przez całą połączoną listę, skutecznie tworząc złożoność czasową O (N). Wraz ze wzrostem listy rośnie liczba operacji. W porównaniu z tablicą, która ma dostęp losowy - dostęp do elementu zajmuje stały czas.
Otóż to!
Połączone listy są świetną alternatywą dla tablic, gdy wstawianie i usuwanie na początku jest kluczową czynnością. Tablice są indeksowane, a listy połączone nie. Połączone listy są również podstawową strukturą danych, z której zbudowane są stosy i kolejki, o czym będę mówić w późniejszym artykule. Jeśli dotarłeś aż tutaj, chwała ci i mam nadzieję, że nauczyłeś się małego samorodka podczas swojej podróży programistycznej!
