Articles

lista z pojedynczym linkiem w JavaScript

aby mieć jasne zrozumienie listy z pojedynczym linkiem, zaimplementuję klasę LinkedList w JavaScript.

każdy węzeł listy połączonej będzie miał dwa atrybuty: value & next, a lista połączona będzie miała atrybut head, tail i length.

https://gist.github.com/GAierken/eb9583bc1ffa78b8e1bb7438a7a49014

Push

Jak możemy wcisnąć nowy węzeł na koniec naszej listy? Zróbmy funkcję push. Najpierw musimy utworzyć nowy węzeł używając podanej wartości, sprawdzić czy lista ma head (czy jest pusta?) i nie zapomnij zwiększyć rozmiar listy.

https://gist.github.com/GAierken/4e44162c8fefe746680e67ea65bf9397

Pop

naciskając, musimy pomyśleć o poppingu, usunięciu ostatniego elementu. Jeśli nie ma węzła, zwróć undefined, else, Pętla przez Listę, aż dojdziemy do tail, Ustaw następną właściwość drugiego ostatniego węzła na null, Ustaw drugi ostatni na tail, nie zapomnij zmniejszyć rozmiaru listy.

https://gist.github.com/GAierken/2c24fecb26f7453879ab471190fcba1e

Shift

aby usunąć pierwszy element, przesuwając, jak zwykle, sprawdź, czy lista jest pusta. Najpierw zapisz bieżącą głowicę w zmiennej, Ustaw głowicę na następną bieżącą głowicę, zmniejsz długość.

https://gist.github.com/GAierken/e6a11cdaf63d9620db33cef58d0a9507

Unshift

aby wstawić węzeł na początku listy, sprawdź, czy lista jest pusta, jeśli nie, ustawiamy bieżącą głowicę na następny atrybut przychodzącego węzła, zwiększ rozmiar.

https://gist.github.com/GAierken/95cbf790f1b6e03711f2460eb7951aa4

Pobierz

mimo, że lista połączona nie ma indeksów, nadal jesteśmy w stanie znaleźć węzeł według podanego indeksu. Najpierw upewnij się, że podany indeks jest większy od zera i mniejszy lub równy długości listy. Następnie przechodzimy przez Listę, aż dojdziemy do indeksu.

https://gist.github.com/GAierken/6475bb388fe8b0f2b7f6507bb3cab446

Ustaw

Co zrobić, jeśli chcemy zmienić węzeł na naszej liście? Znajdujemy węzeł za pomocą get () i ustawiamy węzeł z podanymi danymi.

https://gist.github.com/GAierken/e9b0bb11849219914e2b3ee7b215d5d2

Wstaw

gdy chcemy wstawić nowy węzeł do listy, najpierw sprawdź, czy indeks jest większy niż 0 i mniejszy niż długość. Jeśli indeks jest długością, używamy po prostu push(), jeśli indeks jest równy 0, używamy unshift(). W przypadku innych indeksów, musimy uzyskać węzeł w indeksie-1 i ustawić następną właściwość tego węzła na nowy węzeł, a następną właściwość nowego węzła na poprzednią właściwość następny, a następnie zwiększamy długość.

https://gist.github.com/GAierken/08c88867ddb514de6ef4ddb3923a4117

Usuń

W przeciwieństwie do pop i unshift, funkcja remove usunie węzeł o podanym indeksie. Jak zwykle sprawdź, czy indeks jest poprawny, jeśli indeks jest równy długości – 1 lub 0, użyj pop lub shift. W przeciwnym razie dostajemy węzeł w indeksie-1, ustawiamy właściwość next na tym węźle jako następną z następnej właściwości, po czym zmniejszamy rozmiar.

https://gist.github.com/GAierken/e888104f65a836925b11e102584edd76

Reverse

ostateczne pytanie do tyłu! Jak odwrócić listę? Najpierw zamieniamy head i tail, deklarujemy next i previous, ustawiamy poprzedni jako null. Przeglądamy listę.

https://gist.github.com/GAierken/556c13f4ccbc5bcd49584bd662b553de