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.

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.

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.

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ść.

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.

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.

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.

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ść.

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.

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ę.