Informacje są wszędzie wokół nas.

W świecie oprogramowania sposób, w jaki wybieramy organizację naszych informacji, to połowa sukcesu. Oto jedna rzecz: istnieje wiele sposobów rozwiązania problemu. A jeśli chodzi o porządkowanie naszych danych, istnieje wiele narzędzi, które mogą się sprawdzić w tym zadaniu. Sztuką jest wiedzieć, które narzędzie jest prawo z nich korzystać.

Bez względu na to, w jakim języku zaczynamy kodować, jedną z pierwszych rzeczy, które napotykamy, są struktury danych , czyli różne sposoby, w jakie możemy organizować nasze dane; zmienne , tablice , skróty i obiekty to wszystkie typy struktur danych. Ale to wciąż tylko wierzchołek góry lodowej, jeśli chodzi o struktury danych; jest ich o wiele więcej, a niektóre z nich wydają się bardzo skomplikowane, im więcej o nich się słyszy.

Jedną z tych skomplikowanych rzeczy były dla mnie zawsze listy połączone . O listach z linkami wiem już od kilku lat, ale nigdy nie potrafię utrzymać ich prosto w głowie. Tak naprawdę myślę o nich tylko wtedy, gdy przygotowuję się do (lub czasami w trakcie) wywiadu technicznego i ktoś mnie o nich pyta. Zrobię trochę badań i pomyślę, że rozumiem, o co im chodzi, ale po kilku tygodniach znowu o nich zapominam. Cała sprawa jest dość nieefektywna, a wszystko to wynika z tego, że wiem, że one istnieją, ale zasadniczo ich nie rozumiem ! Czas więc to zmienić i odpowiedzieć na pytanie: czym właściwie jest lista połączona?

Liniowe struktury danych

Jeśli naprawdę chcemy zrozumieć podstawy list połączonych, ważne jest, aby porozmawiać o tym, jakiego typu są to struktury danych.

Jedną z cech powiązanych list jest to, że są to liniowe struktury danych , co oznacza, że ​​istnieje sekwencja i kolejność ich konstruowania i przechodzenia przez nie. Możemy myśleć o liniowej strukturze danych jak o grze w klasy : aby dojść do końca listy, musimy przejść przez wszystkie pozycje na liście po kolei lub po kolei . Struktury liniowe są jednak przeciwieństwem struktur nieliniowych. W nieliniowych strukturach danych elementy nie muszą być uporządkowane, co oznacza, że ​​możemy przechodzić przez strukturę danych niesekwencyjnie .

Może nie zawsze zdajemy sobie z tego sprawę, ale wszyscy codziennie pracujemy z liniowymi i nieliniowymi strukturami danych! Kiedy organizujemy nasze dane w skróty (czasami nazywane słownikami ), wdrażamy nieliniową strukturę danych. Drzewa i wykresy to również nieliniowe struktury danych, po których przemierzamy na różne sposoby, ale omówimy je dokładniej w dalszej części roku.

Podobnie, kiedy używamy tablic w naszym kodzie, wdrażamy liniową strukturę danych! Pomocne może być myślenie o tablicach i połączonych listach jako o podobnych w sposobie, w jaki sekwencjonujemy dane. W obu tych strukturach porządek ma znaczenie . Ale co wyróżnia tablice i połączone listy?

Zarządzanie pamięcią

Największą różnicą między tablicami i połączonymi listami jest sposób, w jaki wykorzystują one pamięć w naszych maszynach. Ci z nas, którzy pracują z dynamicznie typowanymi językami, takimi jak Ruby, JavaScript lub Python, nie muszą myśleć o tym, ile pamięci zajmuje tablica, gdy piszemy nasz kod na co dzień, ponieważ istnieje kilka warstw abstrakcji, które kończą się dzięki nam nie musimy się martwić o alokację pamięci.

Ale to nie znaczy, że alokacja pamięci się nie dzieje! Abstrakcja to nie magia, to po prostu prostota ukrywania rzeczy, których nie musisz widzieć ani zajmować się nimi przez cały czas. Nawet jeśli nie musimy myśleć o alokacji pamięci podczas pisania kodu, jeśli chcemy naprawdę zrozumieć, co dzieje się na liście połączonej i co sprawia, że ​​jest ona potężna, musimy zejść do poziomu podstawowego.

Dowiedzieliśmy się już o plikach binarnych io tym, jak dane można podzielić na bity i bajty. Podobnie jak znaki, liczby, słowa, zdania wymagają bajtów pamięci, aby je przedstawić, tak samo jest ze strukturami danych.

Kiedy tworzona jest tablica , potrzebuje pewnej ilości pamięci. Gdybyśmy mieli 7 liter, które musielibyśmy przechowywać w tablicy, potrzebowalibyśmy 7 bajtów pamięci do reprezentowania tej tablicy. Ale potrzebowalibyśmy całej tej pamięci w jednym ciągłym bloku . Oznacza to, że nasz komputer musiałby zlokalizować 7 bajtów wolnej pamięci, jeden bajt obok drugiego, wszystkie razem, w jednym miejscu.

Z drugiej strony, gdy rodzi się połączona lista , nie potrzebuje ona 7 bajtów pamięci w jednym miejscu. Jeden bajt mógłby gdzieś żyć, podczas gdy następny bajt mógłby być przechowywany w zupełnie innym miejscu w pamięci! Połączone listy nie muszą zajmować ani jednego bloku pamięci; zamiast tego pamięć, której używają, może być rozproszona .

Podstawowa różnica między tablicami a połączonymi listami polega na tym, że tablice są statycznymi strukturami danych , a połączone listy to dynamiczne struktury danych . Statyczna struktura danych wymaga przydzielenia wszystkich zasobów podczas tworzenia struktury; Oznacza to, że nawet jeśli struktura miałaby się rozrosnąć lub skurczyć, a elementy miałyby zostać dodane lub usunięte, to zawsze potrzebuje ona określonego rozmiaru i ilości pamięci. Jeśli trzeba było dodać więcej elementów do statycznej struktury danych i nie było wystarczającej ilości pamięci, musiałbyś na przykład skopiować dane tej tablicy i odtworzyć ją z większą ilością pamięci, aby można było dodać elementy to.

Z drugiej strony dynamiczna struktura danych może się kurczyć i powiększać w pamięci. Nie potrzebuje określonej ilości pamięci do przydzielenia, aby istnieć, a jego rozmiar i kształt mogą się zmieniać, a ilość pamięci, której potrzebuje, również może się zmieniać.

Do tej pory możemy już zacząć dostrzegać pewne główne różnice między tablicami i połączonymi listami. Ale to nasuwa pytanie: co pozwala, aby lista połączona miała rozproszoną pamięć? Aby odpowiedzieć na to pytanie, musimy przyjrzeć się strukturze połączonej listy.

Części połączonej listy

Lista połączona może być mała lub ogromna, ale niezależnie od rozmiaru części, które ją tworzą, są w rzeczywistości dość proste. Lista połączona składa się z szeregu węzłów , które są elementami listy.

Punktem wyjścia listy jest odniesienie do pierwszego węzła, który jest nazywany głową . Prawie wszystkie powiązane listy muszą mieć nagłówek, ponieważ jest to właściwie jedyny punkt wejścia do listy i wszystkich jej elementów, a bez niej nie wiedziałbyś, od czego zacząć! Koniec listy nie jest węzłem, ale raczej węzłem wskazującym na wartość null lub pustą wartość.

Pojedynczy węzeł jest również dość prosty. Składa się tylko z dwóch części: danych lub informacji, które zawiera węzeł, oraz odniesienia do następnego węzła .

Jeśli uda nam się to obejść, to jesteśmy w połowie drogi. Sposób, w jaki działają węzły, jest bardzo ważny i potężny, i można go podsumować następująco:

Węzeł wie tylko, jakie dane zawiera i kto jest jego sąsiadem.

Pojedynczy węzeł nie wie, jak długa jest połączona lista i niekoniecznie musi nawet wiedzieć, gdzie się zaczyna lub gdzie kończy. Wszystko, czego dotyczy węzeł, to zawarte w nim dane i do którego węzła odnosi się jego wskaźnik - następny węzeł na liście.

I to jest właśnie powód, dla którego lista połączona nie potrzebuje ciągłego bloku pamięci. Ponieważ pojedynczy węzeł ma „adres” lub odniesienie do następnego węzła, nie muszą one mieszkać obok siebie, tak jak elementy tablicy. Zamiast tego możemy po prostu polegać na fakcie, że możemy przechodzić przez naszą listę, opierając się na wskaźnikach referencyjnych do następnego węzła, co oznacza, że ​​nasze maszyny nie muszą blokować ani jednego kawałka pamięci, aby reprezentować naszą listę.

Jest to również wyjaśnienie, dlaczego listy połączone mogą rosnąć i kurczyć się dynamicznie podczas wykonywania programu. Dodawanie lub usuwanie węzła z połączoną listą staje się tak proste, jak przestawianie niektórych wskaźników, zamiast kopiowania elementów tablicy! Istnieją jednak pewne wady list połączonych, o których jeszcze nie wspominam - ale więcej o tych w przyszłym tygodniu.

Na razie będziemy po prostu cieszyć się chwałą tego, jak fajne są połączone listy!

Listy dla wszystkich kształtów i rozmiarów

Mimo że części listy połączonej nie zmieniają się, sposób, w jaki tworzymy strukturę list połączonych, może być zupełnie inny. Podobnie jak większość rzeczy w oprogramowaniu, w zależności od problemu, który próbujemy rozwiązać, jeden typ połączonych list może być lepszym narzędziem do pracy niż inny.

Listy pojedynczo połączone to najprostszy typ list połączonych, oparty wyłącznie na fakcie, że prowadzą one tylko w jednym kierunku. Istnieje jedna ścieżka , w której możemy przemierzać listę; zaczynamy odwęzła głównego i przechodzimy od korzenia do ostatniego węzła, który kończy się pustąwartością null .

Ale tak jak węzeł może odwoływać się do swojego kolejnego węzła sąsiedniego, może również mieć wskaźnik odniesienia do poprzedniego węzła! Nazywamy to podwójnie połączoną listą , ponieważ w każdym węźle znajdują się dwa odniesienia : odniesienie do następnego węzła, a także do poprzedniego węzła. Może to być pomocne, jeśli chcemy mieć możliwość przechodzenia przez naszą strukturę danych nie tylko w jednym torze lub w jednym kierunku, ale także do tyłu.

Na przykład, gdybyśmy chcieli mieć możliwość przeskakiwania między jednym węzłem a poprzednim węzłem bez konieczności cofania się do samego początku listy , podwójnie połączona lista byłaby lepszą strukturą danych niż lista pojedynczo połączona. Jednak wszystko wymaga miejsca i pamięci, więc jeśli nasz węzeł musiałby przechowywać dwa wskaźniki referencyjne zamiast tylko jednego, byłoby to kolejną rzeczą do rozważenia.

Okrągły lista związana jest trochę dziwne, że to nie koniec z węzła skierowaną do wartości zerowej. Zamiast tego węzła, który działa jak ogon listy (zamiast tradycyjnego węzła głowie), a węzeł po węźle ogona jest początek listy. Ta struktura organizacyjna sprawia, że ​​naprawdę łatwo jest dodać coś na koniec listy, ponieważ możesz rozpocząć przemierzanie go w węźle końcowym , ponieważ pierwszy element i ostatni element wskazują na siebie. Listy połączone cyklicznie mogą zacząć robić się naprawdę szalone, ponieważ możemy zmienić zarówno listę połączoną pojedynczo, jak i listę podwójnie połączoną w okrągłą listę połączoną!

Ale bez względu na to, jak skomplikowana jest lista połączona, jeśli pamiętamy podstawy węzła i jego działanie oraz strukturę różnych odniesień do wskaźników na naszej liście, nie ma listy połączonej, której nie możemy rozwiązać!

W przyszłym tygodniu, w drugiej części tej serii, zagłębimy się w złożoność czasoprzestrzenną połączonych list i ich porównanie z ich kuzynem, tablicą. Obiecuję, że w rzeczywistości jest to o wiele bardziej zabawne, niż się wydaje!

Zasoby

Jeśli uważasz, że listy z linkami są super fajne, zapoznaj się z tymi pomocnymi zasobami.

1. Różnice między tablicami a listami połączonymi , Damien Wintour
2. Struktury danych: tablice a listy połączone , mykodeschool
3. Powiązane listy: podstawy , dr Edward Gehringer
4. Wprowadzenie do list połączonych , dr Victor Adamchik
5. Struktury danych i implementacje , dr Jennifer Welch
6. Statyczne struktury danych a dynamiczne struktury danych , Ayoma Gayan Wijethunga