Struktury danych stanowią fundament programowania, umożliwiając efektywną organizację i manipulację informacjami.
W tym przewodniku przyjrzymy się bliżej listom jednokierunkowym i dwukierunkowym.
Lista wiązana to liniowa struktura, w której dane nie są przechowywane w ciągłych fragmentach pamięci, jak ma to miejsce w tablicach. Każdy element, zwany węzłem, jest powiązany z kolejnym za pomocą wskaźników. Pierwszy węzeł w liście to jej głowa.
Rozmiar listy wiązanej jest dynamiczny, co oznacza, że możemy dodawać węzły do momentu, aż dostępna pamięć zostanie wyczerpana.
Istnieją dwa główne rodzaje list wiązanych. Przeanalizujmy je szczegółowo.
# 1. Lista Jednokierunkowa
Lista jednokierunkowa charakteryzuje się tym, że każdy węzeł zawiera wskaźnik do następnego elementu. Przechowujemy zatem dane oraz odnośnik do kolejnego węzła.
Ostatni węzeł ma wskaźnik ustawiony na wartość null, co sygnalizuje koniec listy.
Poniżej znajduje się ilustracja przedstawiająca strukturę listy jednokierunkowej.
Po takim wprowadzeniu, przejdźmy do implementacji listy jednokierunkowej w Pythonie.
Implementacja Listy Jednokierunkowej
1. Pierwszym etapem jest stworzenie reprezentacji węzła.
Jak to zrobić?
W Pythonie możemy wygodnie zdefiniować węzeł za pomocą klasy. Klasa ta będzie przechowywać dane oraz wskaźnik do kolejnego węzła.
Oto kod implementujący węzeł:
class Node: def __init__(self, data): ## dane przechowywane w węźle self.data = data ## wskaźnik do kolejnego węzła self.next = None
Wykorzystując tę klasę, możemy tworzyć węzły przechowujące dane dowolnego typu. Zobaczymy to w dalszej części.
Mając zdefiniowany węzeł, możemy przejść do stworzenia samej listy. W tym celu utworzymy kolejną klasę.
2. Stwórzmy klasę `LinkedList`, w której głowa (pierwszy węzeł) zostanie zainicjowana jako `None`. Oto kod:
class LinkedList: def __init__(self): ## inicjalizacja głowy jako None self.head = None
3. Posiadając klasy `Node` i `LinkedList`, jak wstawić nowy węzeł do listy? Najprościej będzie dodać do klasy `LinkedList` metodę wstawiającą. Zaimplementujmy ją.
Wstawianie nowego węzła wymaga wykonania kilku kroków:
Spójrzmy na nie:
- Sprawdź, czy lista jest pusta (czy głowa ma wartość None).
- Jeśli lista jest pusta, przypisz nowy węzeł do głowy.
- Jeśli lista nie jest pusta, znajdź ostatni węzeł.
- Ustaw wskaźnik ostatniego węzła na nowy węzeł.
Oto kod, który implementuje te kroki:
class LinkedList: #### def insert(self, new_node): ## sprawdzenie, czy głowa ma wartość None if self.head: ## znalezienie ostatniego węzła last_node = self.head while last_node.next != None: last_node = last_node.next ## przypisanie nowego węzła do wskaźnika następnego węzła last_node.next = new_node else: ## lista jest pusta ## przypisanie nowego węzła do głowy self.head = new_node
Świetnie! Metoda wstawiania nowego węzła została ukończona. Jak możemy uzyskać dostęp do danych przechowywanych w węzłach?
Aby tego dokonać, musimy przejść przez listę, iterując po wskaźnikach `next`. Zastosujemy podobne podejście jak przy szukaniu ostatniego węzła. Napiszmy metodę, która wyświetli dane wszystkich węzłów.
4. Oto kroki niezbędne do wyświetlenia danych listy:
- Zainicjuj zmienną z głową.
- Wykorzystaj pętlę, która będzie iterować dopóki nie dotrze do końca listy.
- Wyświetl dane bieżącego węzła.
- Przejdź do następnego węzła.
Spójrzmy na kod:
class LinkedList:
####
def display(self):
## zmienna do iteracji
temp_node = self.head
## iterowanie dopóki nie dotrzemy do końca listy
while temp_node != None:
## wyświetlanie danych węzła
print(temp_node.data, end='->')
## przejście do kolejnego węzła
temp_node = temp_node.next
print('Null')
Udało się! Mamy podstawową implementację listy jednokierunkowej z niezbędnymi metodami. Przetestujmy ją, tworząc instancję z danymi.
Węzeł możemy utworzyć za pomocą kodu `Node(1)`. Spójrzmy na pełny kod implementacji, wraz z przykładem użycia:
class Node:
def __init__(self, data):
## dane przechowywane w węźle
self.data = data
## wskaźnik do kolejnego węzła
self.next = None
class LinkedList:
def __init__(self):
## inicjalizacja głowy jako None
self.head = None
def insert(self, new_node):
## sprawdzenie, czy głowa ma wartość None
if self.head:
## znalezienie ostatniego węzła
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## przypisanie nowego węzła do wskaźnika następnego węzła
last_node.next = new_node
else:
## lista jest pusta
## przypisanie nowego węzła do głowy
self.head = new_node
def display(self):
## zmienna do iteracji
temp_node = self.head
## iterowanie dopóki nie dotrzemy do końca listy
while temp_node != None:
## wyświetlanie danych węzła
print(temp_node.data, end='->')
## przejście do kolejnego węzła
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## utworzenie instancji listy
linked_list = LinkedList()
## dodanie danych do listy
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))
## wyświetlenie listy
linked_list.display()
Uruchomienie powyższego programu da następujący wynik:
1->2->3->4->5->6->7->Null
To wszystko w kontekście list jednokierunkowych. Teraz już wiesz jak je zaimplementować. Mając tę wiedzę, możesz łatwo poradzić sobie z implementacją listy dwukierunkowej. Przejdźmy do kolejnej części poradnika.
#2. Lista Dwukierunkowa
Lista dwukierunkowa, w przeciwieństwie do jednokierunkowej, ma w każdym węźle dwa wskaźniki: jeden do poprzedniego węzła, a drugi do następnego. Oznacza to, że każdy węzeł zawiera dane, wskaźnik do poprzednika oraz wskaźnik do następnika.
Poprzedni wskaźnik pierwszego węzła i następny wskaźnik ostatniego węzła mają wartość null, co oznacza odpowiednio początek i koniec listy.
Poniżej znajduje się ilustracja struktury listy dwukierunkowej.
Implementacja listy dwukierunkowej jest podobna do jednokierunkowej. Powtarzanie tych samych kroków byłoby nużące, więc przejdźmy od razu do kodu, który z pewnością zrozumiesz bardzo szybko. Zaczynajmy.
Implementacja Listy Dwukierunkowej
1. Definiujemy węzeł listy dwukierunkowej, zawierający wskaźnik do poprzedniego węzła, dane oraz wskaźnik do następnego węzła.
class Node: def __init__(self, data): ## wskaźnik do poprzedniego węzła self.prev = None ## dane przechowywane w węźle self.data = data ## wskaźnik do kolejnego węzła self.next = None
2. Klasa reprezentująca listę dwukierunkową.
class LinkedList: def __init__(self): ## inicjalizacja głowy jako None self.head = None
3. Metoda wstawiania nowego węzła do listy dwukierunkowej.
class LinkedList: #### def insert(self, new_node): ## sprawdzenie, czy głowa ma wartość None if self.head: ## znalezienie ostatniego węzła last_node = self.head while last_node.next != None: last_node = last_node.next ## przypisanie ostatniego węzła do wskaźnika poprzedniego węzła nowego węzła new_node.prev = last_node ## przypisanie nowego węzła do wskaźnika next ostatniego węzła last_node.next = new_node
4. Metoda wyświetlania danych listy dwukierunkowej.
class LinkedList:
####
def display(self):
## wyświetlanie w normalnej kolejności
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## wyświetlanie w odwrotnej kolejności z użyciem wskaźnika do poprzedniego węzła
print("Reverse Order: ", end='')
## znalezienie ostatniego węzła
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 implementujący listę dwukierunkową. Nie zamieszczono jednak kodu, który pozwoliłby na praktyczne przetestowanie tej klasy. Zostawiam to jako zadanie dla Ciebie. Użyj klasy `LinkedList` w podobny sposób jak wcześniej, przy liście jednokierunkowej. Powodzenia!
Podsumowanie
Istnieje wiele problemów, które można rozwiązać za pomocą list wiązanych. Grunt to zrozumieć podstawową implementację, którą przedstawiliśmy w tym samouczku. Mam nadzieję, że nauka nowej koncepcji sprawiła Ci przyjemność.
Miłego kodowania! 🙂
newsblog.pl