Klasa DoubleList z wartownikiem

IMPLEMENTACJA 3

W klasie DoubleList przechowujemy łącze do wartownika oraz dla wygody zapamiętujemy liczbę elementów przechowywanych w liście (Cormen str. 236). Wartownik pozwala w jednolity sposób usuwać węzeł z dowolnego miejsca listy (właściwie powstaje lista cykliczna). Wartownik nie przechowuje żadnych istotnych danych w atrybucie data.

|       nil       |     nil  +----------------------------+ |
|        |        |      |   |                            | |
|        o        |      o   o                            | |
|    +-+---+-+    |    +-+---+-+               +-+---+-+  | |
| +--+ | ? | +--+ | +--+ | ? | +--o+-+---+-+o--+ | B | +--+ |
| |  +-+---+-+  | | |  +-+---+-+o--+ | A | +--o+-+---+-+    |
| |     o o     | | |              +-+---+-+       o        |
| |     | |     | | |                              |        |
| +-----+ +-----+ | +------------------------------+        |

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   # może to trzymać w polu data wartownika?
        self.nil = Node()   # wartownik
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def is_empty(self):
        # return self.length == 0
        return self.nil.next == self.nil

    def count(self):
        return self.length

    def insert_head(self, node):
        node.next = self.nil.next
        node.prev = self.nil
        self.nil.next.prev = node
        self.nil.next = node
        self.length += 1

    def insert_tail(self, node):
        node.next = self.nil
        node.prev = self.nil.prev
        self.nil.prev.next = node
        self.nil.prev = node
        self.length += 1

    def remove_head(self):   # zwraca node
        if self.is_empty():
            raise ValueError("pusta lista")
        node = self.nil.next
        # Teraz ogólny schemat usuwania węzła.
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = node.prev = None   # czyszczenie
        self.length -= 1
        return node

    def remove_tail(self):   # zwraca node
        if self.is_empty():
            raise ValueError("pusta lista")
        node = self.nil.prev
        # Teraz ogólny schemat usuwania węzła.
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = node.prev = None   # czyszczenie
        self.length -= 1
        return node

Jako ćwiczenie można dodać możliwość iteracji po liście do przodu [for item in dlist] i do tyłu [for item in reversed(dlist)].