Struktury danych odgrywają kluczową rolę w świecie programowania. Pomagają nam organizować nasze dane w sposób, który można efektywnie wykorzystać.
W tym samouczku dowiemy się o liście pojedynczo połączonej i liście połączonej podwójnie.
Lista połączona to liniowa struktura danych. Nie przechowuje danych w ciągłych lokalizacjach pamięci, takich jak tablice. A każdy element w linku nazywany jest węzłem i są one połączone za pomocą wskaźników. Pierwszy węzeł na połączonej liście nazywa się głową.
Rozmiar połączonej listy jest dynamiczny. Możemy więc mieć dowolną liczbę węzłów, o ile pamięć nie jest dostępna w urządzeniu.
Istnieją dwa rodzaje połączonych list. Zobaczmy szczegółowy samouczek o nich jeden po drugim.
Spis treści:
# 1. Lista pojedynczo połączona
Pojedynczo połączona lista zawiera pojedynczy wskaźnik połączony z następnym węzłem na połączonej liście. Musimy przechowywać dane i wskaźnik dla każdego węzła na połączonej liście.
Ostatni węzeł na połączonej liście zawiera wartość null jako następny wskaźnik reprezentujący koniec połączonej listy.
Możesz zobaczyć ilustrację linku poniżej.
Teraz mamy pełne zrozumienie listy pojedynczo połączonej. Zobaczmy, jak zaimplementować go w Pythonie.
Implementacja listy pojedynczo połączonej
1. Pierwszym krokiem jest utworzenie węzła dla połączonej listy.
Jak go stworzyć?
W Pythonie możemy łatwo utworzyć węzeł za pomocą klasy. Klasa zawiera dane i wskaźnik do następnego węzła.
Spójrz na kod węzła.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Możemy stworzyć węzeł z dowolnym typem danych wykorzystując powyższą klasę. Zobaczymy to za chwilę.
Teraz mamy ze sobą węzeł. Następnie musimy utworzyć połączoną listę z wieloma węzłami. Stwórzmy kolejną klasę dla połączonej listy.
2. Utwórz klasę o nazwie LinkedList z głową zainicjowaną na None. Zobacz kod poniżej.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Mamy ze sobą klasy Node i LinkedList. Jak wstawić nowy węzeł do połączonej listy? Prostą odpowiedzią może być użycie metody w klasie LinkedList. Tak, to byłoby miłe. Napiszmy metodę wstawiania nowego węzła do połączonej listy.
Aby wstawić nowy węzeł do połączonej listy, musimy wykonać określone kroki.
Zobaczmy je.
- Sprawdź, czy głowica jest pusta, czy nie.
- Jeśli głowa jest pusta, przypisz nowy węzeł do głowy.
- Jeśli głowa nie jest pusta, pobierz ostatni węzeł połączonej listy.
- Przypisz nowy węzeł do ostatniego węzła następnego wskaźnika.
Zobaczmy kod, aby wstawić nowy węzeł na połączonej liście.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
Hurra! zakończyliśmy metodę wstawiania nowego węzła na połączonej liście. Jak możemy uzyskać dostęp do danych węzłów z połączonej listy?
Aby uzyskać dostęp do danych z połączonej listy, musimy iterować przez połączone, używając następnego wskaźnika, tak jak robimy to, aby uzyskać ostatni węzeł w metodzie wstawiania. Napiszmy metodę wewnątrz klasy LinkedList, aby wydrukować dane wszystkich węzłów na połączonej liście.
4. Wykonaj poniższe czynności, aby wydrukować dane wszystkich węzłów z połączonej listy.
- Zainicjuj zmienną z głową.
- Napisz pętlę, która iteruje, aż dojdziemy do końca połączonej listy.
- Wydrukuj dane węzła.
- Przesuń następny wskaźnik
Zobaczmy kod.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
Uff! zakończyliśmy tworzenie powiązania z niezbędnymi metodami. Przetestujmy połączoną listę, tworząc instancję z niektórymi danymi.
Możemy utworzyć węzeł za pomocą kodu Node(1). Zobaczmy pełny kod implementacji połączonej listy wraz z przykładowym użyciem.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## printing the linked list
linked_list.display()
Uruchom powyższy program, aby uzyskać następujący wynik.
1->2->3->4->5->6->7->Null
To tyle w przypadku połączonej listy. Teraz wiesz, jak zaimplementować listę pojedynczo połączoną. Możesz łatwo zaimplementować listę podwójnie połączoną ze znajomością listy pojedynczo połączonej. Przejdźmy do następnej części samouczka.
#2. Lista podwójnie połączona
Lista podwójnie połączona zawiera dwa wskaźniki połączone z poprzednim węzłem i następnym węzłem na połączonej liście. Musimy przechowywać dane i dwa wskaźniki dla każdego węzła na połączonej liście.
Poprzedni wskaźnik pierwszego węzła jest pusty, a następny wskaźnik ostatniego węzła jest pusty, aby reprezentować koniec połączonej listy po obu stronach.
Możesz zobaczyć ilustrację linku poniżej.
Lista podwójnie połączona ma również podobne kroki w implementacji, jak lista pojedynczo połączona. Powtarzanie tych samych rzeczy będzie dla ciebie nudne. Przejrzyj kod w każdym kroku, a zrozumiesz go bardzo szybko. Chodźmy.
Implementacja listy podwójnie połączonej
1. Tworzenie węzła dla listy podwójnie połączonej ze wskaźnikiem poprzedniego węzła, danymi i wskaźnikiem następnego węzła.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Podwójnie połączona klasa listy.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Sposób wstawiania nowego węzła do listy podwójnie połączonej.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Metoda wyświetlania danych listy podwójnie połączonych.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Widzieliśmy kod listy podwójnie połączonej. I nie ma kodu do użycia podwójnie połączonej klasy listy. To dla Ciebie. Użyj klasy listy podwójnie połączonej, podobnej do listy połączonej pojedynczo. Miłej zabawy 🙂
Wniosek
Możesz znaleźć wiele problemów na podstawie połączonych list. Ale musisz znać podstawową implementację linku, której nauczyłeś się w tym samouczku. Mam nadzieję, że dobrze się bawiłeś, poznając nową koncepcję.
Miłego kodowania 🙂