Podwójnie połączone listy i jak je zaimplementować w Pythonie 3

Listy połączone to liniowy sposób przechowywania danych. Składa się z węzłów, które zawierają dane, a także wskazówek, jak dostać się do następnego fragmentu danych. Pomyśl o węzłach jako o członku łańcucha. Każdy łańcuch zależy od siebie nawzajem, aby zachować silną więź. Jeśli na przykład w środkowym łączu brakuje wszystkiego, potem się nie powiedzie. To już nie jest kompletny łańcuch! Jak to się przekłada na połączone listy? Jeśli brakuje jednego ze wskaźników lub jest on niepoprawny, nie można już odczytać pozostałych danych.

Nieprawidłowy łańcuch! Spowodowałoby to uszkodzenie połączonej listy!

Jednak tematem tego artykułu jest bardziej uniwersalna wersja list połączonych - lista podwójnie połączona. W porównaniu do zwykłej (lub pojedynczo) połączonej listy, podwójnie połączona lista zawiera inny wskaźnik o nazwie previous. Jak można się domyślić, pozwala to węzłowi wiedzieć, gdzie jest poprzedni węzeł. Dla porównania, pojedynczo połączona lista musiałaby ponownie przejść całą listę do poprzedniego punktu, aby dostać się do tego samego punktu.

Aby uzyskać informacje na temat pojedynczo połączonych list, odwiedź artykuł mojego kolegi z klasy:

Jak wspomniano wcześniej, węzły wskazują inne miejsca w pamięci. Co to znaczy? Cóż, w przeciwieństwie do tablic przechowywanych w sąsiadujących lokalizacjach, listy połączone mają po prostu wskaźniki. Na poniższym schemacie każdy blok pamięci (czerwony) ma dwa wskaźniki, które do niego wskazują. Dostęp do tych informacji uzyskuje się, patrząc na wskaźnik Następny (czarny). Jeśli chce znaleźć blok przed nim, spojrzy na Poprzedni wskaźnik (biały).

Jak więc wdrożyć podwójnie połączoną listę? Oto jak w Python 3

Po prostu dodaj .prev do swojej klasy Node. Teraz możesz rozpocząć wdrażanie!

Zalety - Z kodem Python 3!

Jakie są zalety podwójnie połączonej listy w porównaniu z pojedynczo połączoną listą? Cóż, z podwójnie połączoną listą, możesz przesuwać się do tyłu i do przodu między swoimi węzłami. To sprawia, że ​​wstawianie jest naprawdę łatwe. W przypadku podwójnie połączonych list wystarczy przejść do połączonej listy do żądanego węzła, a następnie wywołać poprzedni węzeł.

Wady

Chociaż istnieją świetne rzeczy w połączonych listach, nie jest to rozwiązanie typu „wszystko dla wszystkich”. Podobnie jak w przypadku wielu struktur danych i algorytmów, powinno to być narzędzie w twoim arsenale. Jedną z wad w stosunku do pojedynczo połączonej listy jest większe zużycie pamięci, ponieważ każde łącze na podwójnie połączonej liście musi śledzić poprzedni wskaźnik. Ponadto trudno jest śledzić wskazany wskaźnik.

Właściwie wciąż jestem w trakcie ich wdrażania. To będzie moja druga udana implementacja od napisania tego artykułu (kwiecień 2019 r.). Za każdym razem staje się nieco łatwiej, ale wciąż muszę rysować diagramy interakcji poprzedniego wskaźnika ze wszystkimi innymi funkcjami.

Ale do czego by to wykorzystano?

Słyszę, że pytasz. Pomyśl o każdej chwili, w której widziałeś poprzednią i następną. Istnieje kilka oczywistych i subtelnych sposobów ich wdrożenia.

Źródło: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

Co powiesz na odtwarzacz muzyczny? Ma bardzo wyraźny następny i poprzedni przycisk. Podwójnie połączoną listę można wykorzystać do przełączania między tymi dwoma utworami.

A co z przeglądarką? Mają także wyraźne sposoby przechodzenia między odwiedzanymi stronami.

Teraz pomyśl o wybranym edytorze tekstu lub edytorze zdjęć. Za każdym razem, gdy się pomylisz, możesz nacisnąć CTRL (CMD na Maca) + Z, aby cofnąć ostatnią czynność. Podobnie, możesz powtórzyć to, co cofnąłeś, używając CTRL (CMD dla komputerów Mac) + Y. Dlaczego to brzmi znajomo? Można go również wdrożyć za pomocą podwójnie powiązanej listy! Poprzedni wskaźnik wskazuje na działania, które zostały wykonane, a jednocześnie jest w stanie wykonać je ponownie, jeśli cofniesz za dużo.

Źródło: https://gfycat.com/brilliantbeautifuldassieŹródło: https://www.solitairecardgames.com/how-to-play-solitaire

Mniej oczywistą implementacją, o której myślałem, była gra Solitaire. Z boku znajduje się obraz terminologii pasjansa, aby zilustrować mój punkt widzenia.

Gra jest świetnym przykładem, w którym stale musisz mieć możliwość przeglądania poprzednich i następnych kart, niezależnie od tego, czy znajdują się one na stole, czy na stosie odpadów. Kiedy zagrywasz kartę ze stosu odpadów na planszę, stos odpadów jest aktualizowany o kartę przed nią.

Aby ożywić dyskusję o zastosowaniach na podwójnie połączonych listach, polecam rzucić okiem na tę dyskusję na temat przepływu stosu:

Więc następnym razem, gdy wdrażasz listę połączoną, dlaczego nie wypróbować podwójnie połączonej listy? Nie jest to o wiele więcej kodu na górze połączonej listy i są ogromne korzyści!

Dodatkowe zasoby

Pełny link do mojej implementacji podwójnie połączonej listy w Python 3 można znaleźć na moim repozytorium Github.

Jeśli chcesz łańcuch 3d podwójnie połączonych list do wydrukowania, przesłałem go do Thingiverse.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ