Wykład 4 (cz. 2) - listy łączone, hermetyzacja¶

Spis treści¶

Listy łączone
Hermetyzacja (encapsulation)

W tym rozdziale omówimy najprostszą łączoną strukturę danych - listę łączoną, oraz zaprezentujemy na jej przykładzie hermetyzację - pewien koncept programowania obiektowego.

Listy łączone ¶

List łączona to struktura danych, w których obiekty przechowywane są w skończonej ilości węzłów (nodes). Pojedynczy węzeł przechowuje pojedynczy obiekt. Węzły ustawione są w łańcuch. Każdy węzeł zawiera dwie dane: przechowywany obiekt, oraz następnik węzła, czyli następny węzeł w łańcuchu (lub informację, że jest ostatnim węzłem). Pierwszy węzeł w łańcuchu nazywamy głową (head) listy, a ostatni jej ogonem (tail). Lista łączona pamięta, który węzeł jest głową, a który ogonem. Lista może być pusta (nie mieć głowy ani ogona).

Ilustracja listy łączonej, przechowującej liczby jako dane: linked

Rozważmy dwie operacje, polegające na dodaniu węzła node z danymi na początek lub na koniec listy łączonej. Operacje te muszą zachowywać strukturę listy łączonej.

Dodanie węzła na koniec listy. Mamy dwa przypadki:

Lista łączona jest pusta: zapamiętujemy node jako zarówno głowę, jak i ogon.
Lista łączona zawiera węzły: ogon listy zapamiętuje node jako następnik, a node staje się nowym ogonem.

Dodanie węzła na początek listy. Mamy dwa przypadki:

Lista łączona jest pusta: zpamiętujemy node jako zarówno głowę, jak i ogon.
Lista łączona zawiera węzły: node zapamiętuje głowę jako następnik i staje się nową głową.

Teraz rozważmy operacje usunięcia głowy (i tylko głowy) niepustej listy łączonej.

Usunięcie głowy. Mamy dwa przypadki:

Lista łączona zawiera tylko jeden węzeł (jednocześnie głowę i ogon): zapamiętujemy, że lista łączona nie ma głowy ani ogona.
Lista łączona zawiera więcej węzłów: nową głową zostaje następnik głowy.

Pokażemy teraz przykładową implementację listy łączonej. Pojedynczy węzeł będziemy reprezentować przez klasę Node z następującymi metodami:

__init__(data) - tworzy nowy węzeł, pamiętający obiekt data. Węzeł nie ma następnika.
get_data() - zwraca obiekt, pamiętany przez węzeł.
get_next() - zwraca następnik węzła (lub None, jeśli go nie ma).
set_data(data) - ustawia obiekt, pamiętany przez węzeł.
set_next(node) - ustawia następnik węzła na podany węzeł node. Argumentem node może być None.

Wewnętrznie, węzeł, pamięta obiekt i następnik w atrybutach (odpowiednio) data i next.

Całą listę łączoną będziemy reprezentować klasą LinkedList, implementującą metody:

__init__() - tworzy pustą listę łączoną.
push_front(data) - dokłada nowy węzeł pamiętający obiekt data na początek listy łączonej.
push_back(data) - dokłada nowy węzeł pamiętający obiekt data na początek koniec łączonej.
pop_front() - usuwa węzeł z początku listy łączonej i zwraca obiekt pamiętany przez ten węzeł.
size() - zwraca ilość węzłów na liście łączonej.
is_empty() - orzeka, czy lista łączona jest pusta.

Wewnętrznie, lista łączona będzie używać atrybutów head i tail pamiętające odpowienio głowę i ogon.

Przechodzimy do implementacji. Najpierw węzeł:

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

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next

Następnie lista łączona. Metody implementujemy zgodnie z opisem operacji:

# from node import Node

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        
    def push_front(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        if self.is_empty():
            self.tail = new_node
        self.head = new_node
        
    def push_back(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            self.tail.set_next(new_node)
        self.tail = new_node
        
    def pop_front(self):
        obj = self.head.get_data()
        if self.head is self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.get_next()
        return obj
        
    def size(self):
        n = 0
        current = self.head
        while current is not None:
            current = current.get_next()
            n += 1
        return n
        
    def is_empty(self):
        return self.head is None

Przykład użycia:

lst = LinkedList()
for n in range(10):
    lst.push_back(n) # -> lst: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for _ in range(5):
    print(lst.pop_front())  # -> 0, 1, 2, 3, 4, lst: [5, 6, 7, 8, 9]
for n in range(-1, -4, -1):
    lst.push_front(n) # lst == [-3, -2, -1, 5, 6, 7, 8, 9]
while not lst.is_empty():
    print(lst.pop_front()) # -3, -2, -1, 5, 6, 7, 8, 9, lst: []

0
1
2
3
4
-3
-2
-1
5
6
7
8
9

Zwracamy uwagę na następujące fakty:

Czasy operacji pop_front i push_front są stałe - nasza lista łączona nadaje się więc jako wydajny złożonościowo stos.
Podobnie, czas operacji push_back jest stały - więc struktura nadaje się jako wydajna kolejka.
Na razie nie widać sposobu, jak wykonać operację pop_back (usuwanie węzła z końca) w czasie stałym - może to wymagać modyfikacji listy łączonej.

Uwaga. Powyższa lista łączona ma wiele wariantów (np. bufor cykliczny, lista wielokrotnie łączona, ...), omówienie których wykracza poza zakres skryptu.

Hermetyzacja (encapsulation)¶

Zwróćmy uwagę, że w opisie klasy LinkedList (a także Node) prezentujemy metody służące do działania na strukturze danych. Ich znaczenie jest niezależne od szczegółów implementacji (np. atrybutów przechowujących głowę i ogon). Te ukryte szczegóły implementacji nie są przeznaczone do bezpośredniego dostępu: manipulacja np. atrybutem tail bez jednoczesnego uaktualnienia nastepników węzłów w łańcuchu niszczy strukturę listy łączonej.

Praktyką w programowaniu obiektowym jest tzw. hermetyzacja (encapsulation), polegająca na uniemożliwianiu dostępu do wewnętrznych danych obiektu (i sposobu reprezentacji tych danych) przez użytkownika (użytkownik to każdy, kto używa danego obiektu - w tym my sami). Służy ona do ochrony spójności przechowywanych danych przy jednoczesnym klarownym zaprezentowaniu operacji, które można wykonać na obiekcie (interfejs publiczny). Jednocześnie pozwala na abstrakcję: obiekt jest opisany przez (publiczne) działania, które można na nim wykonać, bez wnikania w szczegóły, jak te operacje są realizowane.

W naszym przykładzie w naszym przykładzie, szczegółami implementacji Node są jego atrybuty: data i next, a publicznym interfejsem metody get_data(), set_data(), get_next(), set_next(), pozwalające na manipulację nimi. Z kolei interfejsem LinkedList są wszystkie zaimplementowane metody, z kolei szczegółami implementacji LinkedList są na pewno atrybuty head oraz tail. Zauważmy jednak, że wewnętrznie LinkedList używa także klasy Node, która nie jest widoczna w publicznym interfejsie (w np. push_front() podajemy obiekt do zapamiętania, nie węzeł, który ma go pamiętać). Zatem można potraktować całą klasę Node jako niepubliczny szczegół implementacji LinkedList.

Różne języki dostarczają na różne sposoby mechanizmu rozdzielania interfejsu publicznego od szczegółów implementacji. Przykładowo W językach podobnych do C++ (C#, Java, ...), dla metody i atrybuty klas można określić poziom dostępu. Poziom może być publiczny lub niepubliczny (wyróżnia się różne poziomy niepubliczne, np. prywatny lub chroniony). Z publicznych metod i atrybutów klasy można korzystać w dowolnym miejscu kodu. Z niepublicznych jedynie w implementacji tej samej klasy (lub pewnych specjalnych klas stowarzyszonych z nią).

Python nie oferuje "twardego" mechanizmu określania poziomu dostępu, stosuje jednak pewne konwencje. Atrybuty, których nazwy rozpoczęte są znakiem _ traktowane są jako "chronione". Są cały czas dostępne poza implementacją klasy, ale użycie ich poza klasą jest traktowane jako zła praktyka, a edytory będą zgłaszać takie przypadki (np. podkreślając kod). Dodatkowym sposobem na oznaczenie atrybutu jako prywatnego jest nadanie mu nazwy rozpoczętej od __ (tzw. dunder, double underscore).

Uwaga. W rzeczywistości, dunder wprowadza pewien "twardy" mechanizm ukrywania atrybutów ze względu na tzw. name mangling, czego nie omówimy w tym skrypcie.

Klasa LinkedList, w której ukrywamy szczegóły zgodnie z konwencją mogłaby wyglądać tak (zwróćmy uwagę, że _Node - odpowiednik Node - jest klasą zdefiniowaną wewnątrz LinkedList:

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

    def __init__(self):
        self._head = None
        self._tail = None

    def push_front(self, data):
        new_node = self._Node(data)
        new_node.next = self._head
        if self.is_empty():
            self._tail = new_node
        self._head = new_node

    def push_back(self, data):
        new_node = self._Node(data)
        if self.is_empty():
            self._head = new_node
        else:
            self._tail.next = new_node
        self._tail = new_node

    def pop_front(self):
        obj = self._head.data
        if self._head is self._tail:
            self._head = None
            self._tail = None
        else:
            self._head = self._head.next
        return obj

    def size(self):
        n = 0
        current = self._head
        while current is not None:
            current = current.next
            n += 1
        return n

    def is_empty(self):
        return self._head is None

Wykład 4 (cz. 2) - listy łączone, hermetyzacja¶

Spis treści¶

Listy łączone¶

Hermetyzacja (encapsulation)¶

Listy łączone ¶