Klasa SingleList

WPROWADZENIE

Istnieją pewne subtelne problemy przy implementacji list z wykorzystaniem tylko klasy Node. Przy przejściu z funkcji do metod jest problem z pustą listą. Nie można wywoływać metod, gdy węzeł jest równy None. Rozwiązaniem jest inna implementacja.

Innym problemem są operacje, które są klasy O(n), co powoduje, że dla długich list będą powolne. Są to np. znajdowanie liczby elementów na liście i wstawianie elementu na koniec listy. W podejściu obiektowym możemy rozwiązać te problemy wprowadzając dodatkowe atrybuty, tzn. możemy na bieżąco uaktualniać licznik elementów, oraz możemy przechowywać łącze do końca listy.

IMPLEMENTACJA 2

Obok klasy Node wprowadzamy klasę SingleList, w której przechowujemy elementy informacyjne poprawiające wydajność operacji na listach.

class Node:
    """Klasa reprezentująca węzeł listy jednokierunkowej."""

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

    def __str__(self):
        return str(self.data)   # bardzo ogólnie

    def __eq__(self, other):
        return self.data == other.data

    def __ne__(self, other):
            return not self == other

class SingleList:
    """Klasa reprezentująca całą listę jednokierunkową."""

    def __init__(self):
        self.length = 0   # nie trzeba obliczać za każdym razem
        self.head = None
        self.tail = None

    def is_empty(self):
        #return self.length == 0
        return self.head is None

    def count(self):   # tworzymy interfejs do odczytu
        return self.length

    def insert_head(self, node):
        if self.head:   # dajemy na koniec listy
            node.next = self.head
            self.head = node
        else:   # pusta lista
            self.head = self.tail = node
        self.length += 1

    def insert_tail(self, node):   # klasy O(1)
        if self.head:   # dajemy na koniec listy
            self.tail.next = node
            self.tail = node
        else:   # pusta lista
            self.head = self.tail = node
        self.length += 1

    def remove_head(self):   # klasy O(1)
        if self.is_empty():
            raise ValueError("pusta lista")
        node = self.head
        if self.head == self.tail:   # self.length == 1
            self.head = self.tail = None
        else:
            self.head = self.head.next
        node.next = None   # czyszczenie łącza
        self.length -= 1
        return node   # zwracamy usuwany node

# Zastosowanie.
alist = SingleList()
alist.insert_head(Node(11))   # [11]
alist.insert_head(Node(22))   # [22, 11]
alist.insert_tail(Node(33))   # [22, 11, 33]
print("length {}".format(alist.length))   # odczyt atrybutu
print("length {}".format(alist.count()))   # wykorzystujemy interfejs
while not alist.is_empty():   # kolejność 22, 11, 33
    print("remove head {}".format(alist.remove_head()))

LISTA POWIĄZANA POJEDYNCZO Z ITERATOREM

Istnieją co najmniej dwa sposoby wyposażenia klasy SingleList w możliwość iteracji po elementach listy.

class SingleList:   # lista zwróci iterator po sobie
    # ... inne metody ...

    def __iter__(self):   # wykorzystanie funkcji generatora
        node = self.head
        while node:
            yield node.data
            node = node.next

class SingleList:    # lista jest jednocześnie iteratorem
    # ... inne metody ...

    def __iter__(self):
        # Przy tworzeniu iteratora trzeba mieć zmienną, która będzie pamiętać stan.
        # Przy kolejnym tworzeniu iteratora będzie ustawianie na początek.
        # Iterator będzie odświeżony do nowej iteracji po liście.
        self.current = self.head
        return self

    def __next__(self):
        if self.current:
            node = self.current
            self.current = self.current.next
            return node.data
        else:   # self.current is None
            raise StopIteration

    next = __next__   # kompatybilność Py2 i Py3

# Zastosowanie.
alist = SingleList()
alist.insert_head(Node(11))   # [11]
alist.insert_head(Node(22))   # [22, 11]
alist.insert_tail(Node(33))   # [22, 11, 33]
for item in alist:   # kolejność 22, 11, 33
    print(item)