Jak zaimplementować listę połączoną w Pythonie?

Język programowania Python jest językiem open source z różnymi gotowymi implementacjami, dzięki czemu jest wyjątkowy i łatwiejszy do nauczenia. Mimo że nie obsługuje koncepcji listy połączonej, istnieje sposób obejścia tego za pomocą innej implementacji, aby uzyskać listę połączoną. W tym artykule dowiemy się, jak utworzyć listę połączoną w Pythonie. Oto tematy poruszane na tym blogu:

• Co to jest lista połączona?
• Implementowanie listy połączonej
• Metody listy połączonej

Zaczynajmy!!

Co to jest lista połączona?

Lista łączy to sekwencja węzłów o podobnym typie danych, każdy węzeł zawiera jeden obiekt danych i wskaźnik do następnego węzła.

Lista połączona to liniowa struktura danych z kolekcją wielu węzłów. Gdzie eKażdy element przechowuje własne dane i wskaźnik do lokalizacji następnego elementu. Ostatnie łącze na liście połączonej wskazuje na wartość null, wskazując koniec łańcucha. Element na połączonej liście nosi nazwę węzeł . Pierwszy węzeł nosi nazwę głowa .Nazywa się ostatni węzełthe ogon .
Standardowa biblioteka Pythona nie ma połączonej listy. Możemy zaimplementować koncepcję struktury danych listy linków, wykorzystując koncepcję węzłów.

Teraz, gdy dowiedzieliśmy się, co to jest Linked. Przejdźmy więc do implementacji listy połączonej.

Implementowanie listy połączonej

Aby utworzyć listę połączoną, tworzymy obiekt węzła i tworzymy kolejną klasę, która będzie używać tego obiektu węzła.
Kod do tworzenia klasy Node.
Powyższy program tworzy połączoną listę z trzema elementami danych.

class Węzeł (obiekt): # Konstruktor do inicjalizacji zmiennych klasowych def __init __ (self, data = None, next_node = None): self.data = data self.next_node = next_node #get data def get_data (self): return self.data # get next value def get_next (self): return self.next_node # set next data def set_next (self, new_next): self.next_node = new_next

Implementacja listy linków składa się z następujących funkcji na liście połączonej
jeden. Wstawić : Ta metoda wstawi nowy węzeł na połączonej liście.
2. Rozmiar : Ta metoda zwróci rozmiar połączonej listy.
3. Szukaj : Ta metoda zwróci węzeł zawierający dane, w przeciwnym razie spowoduje błąd
Cztery. Usunąć : Ta metoda usunie węzeł zawierający dane, w przeciwnym razie spowoduje błąd

Zobaczmy listę Methods of Linked

Init na połączonej liście

class LinkedList (obiekt): def __init __ (self, head = None): self.head = head

Metoda Init służy do inicjalizacji pliku klasa zmienna jeśli lista nie zawiera węzłów, jest ustawiona na brak.

Wstawić:

def insert (self, data): new_node = Node (data) new_node.set_next (self.head) self.head = new_node

Ta metoda wstawiania pobiera dane, inicjuje nowy węzeł z podanymi danymi i dodaje go do listy. Technicznie rzecz biorąc, możesz wstawić węzeł w dowolnym miejscu na liście, ale najprostszym sposobem na to jest umieszczenie go na początku listy i skierowanie nowego węzła na starą głowę (rodzaj spychania innych węzłów w dół linii).

Rozmiar

# Zwraca całkowitą liczbę węzłów na liście def size (self): current = self.head count = 0 while current: count + = 1 current = current.get_next () return count

Metoda rozmiaru jest bardzo prosta, w zasadzie liczy węzły, dopóki nie może ich już znaleźć, i zwraca liczbę znalezionych węzłów. Metoda rozpoczyna się w węźle głównym, podróżuje wzdłuż linii węzłów, aż osiągnie koniec (prądem będzie None, gdy dotrze do końca), jednocześnie śledząc, ile węzłów widziała.

Szukaj

# Zwraca węzeł z listy mający nodeData, wystąpił błąd, jeśli węzeł nie jest obecny. Def search (self, nodeData): current = self.head isPresent = False, podczas gdy current i isPresent to False: if current.get_data () == nodeData: isPresent = True else: current = current.get_next () if current is None: raise ValueError ('Data not present in list') return current

Wyszukiwanie jest w rzeczywistości bardzo podobne do rozmiaru, ale zamiast przechodzić przez całą listę węzłów, sprawdza na każdym przystanku, aby sprawdzić, czy bieżący węzeł ma żądane dane. Jeśli tak, zwraca węzeł przechowujący te dane. Jeśli metoda przeszukuje całą listę, ale nadal nie znalazła danych, zgłasza błąd wartości i powiadamia użytkownika, że ​​danych nie ma na liście.

Usunąć

jak używać przycinania w java

# Usuń węzeł z połączonej listy zwraca błąd, jeśli węzeł nie istnieje. Def delete (self, nodeData): current = self.head previous = None isPresent = False while current and isPresent is False: if current.get_data () == nodeData: isPresent = True else: previous = current current = current.get_next () if current is None: raise ValueError ('Dane nieobecne na liście') if previous to None: self.head = current.get_next () else: previous.set_next ( current.get_next ())

Metoda delete przechodzi przez listę w ten sam sposób, co wyszukiwanie, ale oprócz śledzenia bieżącego węzła, metoda delete zapamiętuje również ostatni odwiedzony węzeł. Kiedy delete ostatecznie dotrze do węzła, który chce usunąć. Po prostu usuwa ten węzeł z łańcucha, „przeskakując” go.

Rozumiem przez to, że kiedy metoda delete osiągnie węzeł, który chce usunąć, sprawdza ostatni odwiedzony węzeł („poprzedni” węzeł) i resetuje wskaźnik poprzedniego węzła. Zamiast wskazywać na węzeł, który wkrótce zostanie usunięty.

Wskaże następny węzeł w linii. Ponieważ żaden węzeł nie wskazuje na zły węzeł, który jest usuwany, jest on skutecznie usuwany z listy!

To prowadzi nas do końca tego artykułu, w którym nauczyliśmy się, jak utworzyć listę połączoną w Pythonie z podobną implementacją, mimo że Python tak naprawdę nie obsługuje koncepcji listy połączonej. Mam nadzieję, że wszystko, co zostało Ci udostępnione w tym samouczku, jest dla Ciebie jasne.

Jeśli uważasz, że ten artykuł w „Linked List In Python” jest odpowiedni, zapoznaj się z Zaufana firma zajmująca się edukacją online z siecią ponad 250 000 zadowolonych uczniów rozsianych po całym świecie.

Jesteśmy tutaj, aby pomóc Ci na każdym kroku w Twojej podróży i opracować program nauczania przeznaczony dla studentów i profesjonalistów, którzy chcą być . Kurs ma na celu zapewnienie przewagi w programowaniu w Pythonie i przeszkolenie zarówno podstawowych, jak i zaawansowanych koncepcji Pythona, a także różnych lubić

Jeśli napotkasz jakieś pytania, nie krępuj się zadawać je w sekcji komentarzy w „Powiązanej liście w Pythonie”, a nasz zespół z przyjemnością odpowie.