Klasa DoubleList

IMPLEMENTACJA 2

W klasie DoubleList przechowujemy łącza do początku i do końca listy oraz dla wygody zapamiętujemy liczbę elementów przechowywanych w liście.

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

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

    def __str__(self):
        return str(self.data)

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

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

class DoubleList:
    """Klasa reprezentująca całą listę dwukierunkową."""

    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

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

    def count(self):
        return self.length

    def insert_head(self, node):
        if self.head:
            node.next = self.head
            self.head.prev = node   # stary head
            self.head = node        # nowy head
        else:         # pusta lista
            self.head = node
            self.tail = node
        self.length += 1

    def insert_tail(self, node):
        if self.tail:
            node.prev = self.tail
            self.tail.next = node   # stary tail
            self.tail = node        # nowy tail
        else:         # pusta lista
            self.head = node
            self.tail = node
        self.length += 1

    def remove_head(self):   # zwraca node
        if self.is_empty():
            raise ValueError("pusta lista")
        elif self.head is self.tail:   # length == 1
            node = self.head
            self.head = None
            self.tail = None
            self.length = 0
            return node
        else:
            node = self.head
            self.head = self.head.next
            self.head.prev = None   # czyszczenie
            node.next = None   # czyszczenie
            self.length -= 1
            return node

    def remove_tail(self):   # zwraca node
        if self.is_empty():
            raise ValueError("pusta lista")
        elif self.head is self.tail:   # length == 1
            node = self.tail
            self.head = None
            self.tail = None
            self.length = 0
            return node
        else:
            node = self.tail
            self.tail = self.tail.prev
            self.tail.next = None   # czyszczenie
            node.prev = None
            self.length -= 1
            return node

LISTA POWIĄZANA PODWÓJNIE Z ITERATORAMI

Listę powiązaną podwójnie można wydajnie przechodzić w obu kierunkach. Warto stworzyć odpowiednie iteratory. Nie należy zmieniać zawartości listy podczas iterowania po niej.

class DoubleList:
    # ... inne metody ...

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

    def __reversed__(self):   # wykorzystanie funkcji generatora
        node = self.tail
        while node:
            yield node.data
            node = node.prev

# Zastosowanie.
alist = DoubleList()
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)
for item in reversed(alist):   # kolejność 33, 11, 22
    print(item)