Listy: listy jednokierunkowe i dwukierunkowe

5.1 Definicja listy i jej rodzaje

Lista — to dynamiczna struktura danych, składająca się z elementów (węzłów), gdzie każdy węzeł zawiera dane i odnośniki do innych węzłów. W przeciwieństwie do tablic, listy mogą zmieniać swój rozmiar podczas wykonywania programu.

Ważne! W tym przypadku nie chodzi o klasę list z Pythona, lecz o strukturę danych z teorii algorytmów.

Rodzaje list:

• Lista jednokierunkowa (Singly Linked List): Każdy węzeł zawiera dane i odnośnik do następnego węzła.
• Lista dwukierunkowa (Doubly Linked List): Każdy węzeł zawiera dane, odnośnik do następnego węzła i odnośnik do poprzedniego węzła.

5.2 Zasada działania listy jednokierunkowej

Struktura listy jednokierunkowej:

• Węzeł (Node): Składa się z dwóch części: danych i odnośnika do następnego węzła.
• Głowa (Head): Wskaźnik na pierwszy węzeł listy.

Zasada działania:

• Dodanie węzła: Odbywa się poprzez stworzenie nowego węzła i aktualizację odnośnika ostatniego węzła na nowy węzeł.
• Usunięcie węzła: Wymaga aktualizacji odnośnika poprzedniego węzła na następny węzeł usuwanego węzła.

Przykład implementacji:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Przykład użycia:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Wyjście: 1 -> 2 -> 3 -> None

5.3 Zasada działania listy dwukierunkowej

Struktura listy dwukierunkowej:

• Węzeł (Node): Składa się z trzech części: danych, odnośnika do następnego węzła i odnośnika do poprzedniego węzła.
• Głowa (Head): Wskaźnik na pierwszy węzeł listy.
• Ogon (Tail): Wskaźnik na ostatni węzeł listy (nieobowiązkowy, ale często używany).

Zasada działania:

• Dodanie węzła: Odbywa się poprzez stworzenie nowego węzła i aktualizację odnośników ostatniego i nowego węzła.
• Usunięcie węzła: Wymaga aktualizacji odnośników następnego i poprzedniego węzła usuwanego węzła.

Przykład implementacji:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Przykład użycia:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Wyjście: 1 <-> 2 <-> 3 <-> None

5.4 Podstawowe operacje

Podstawowe operacje: wstawianie, usuwanie, wyszukiwanie

Wstawianie:

• Lista jednokierunkowa: Wstawienie nowego węzła na końcu listy wymaga przejścia przez wszystkie węzły do ostatniego i aktualizacji odnośnika ostatniego węzła.
• Lista dwukierunkowa: Wstawienie nowego węzła na końcu listy jest analogiczne do listy jednokierunkowej, ale wymaga również aktualizacji odnośnika prev nowego węzła na poprzedni węzeł.

Usunięcie:

• Lista jednokierunkowa: Usunięcie węzła wymaga przejścia przez listę do węzła, który należy usunąć, oraz aktualizacji odnośnika poprzedniego węzła na następny węzeł usuwanego węzła.
• Lista dwukierunkowa: Usunięcie węzła wymaga aktualizacji odnośników next i prev sąsiednich węzłów usuwanego węzła.

Wyszukiwanie: Przejście przez listę od głowy do ogona i porównywanie danych każdego węzła z poszukiwaną wartością. Złożoność czasowa — O(n).

5.5 Przykład użycia list

Dla przykładu zrealizujemy stos na bazie listy jednokierunkowej.

Stos można łatwo zrealizować przy użyciu listy jednokierunkowej, używając metod dodawania push i usuwania pop elementów. Powinien mieć 2 metody:

• push — dodanie nowego elementu na koniec listy
• pop — pobranie ostatniego elementu z końca listy

Przykład implementacji:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Przykład użycia:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Wyjście: 3 -> 2 -> 1 -> None
print(stack.pop())  # Wyjście: 3
stack.display()  # Wyjście: 2 -> 1 -> None