Verkette Listen

[narpfel]

@__blackjack__:

Code: Alles auswählen

In [1]: from attr import attrib, attrs

In [2]: @attrs
   ...: class LinkedList:
   ...:     value = attrib()
   ...:     next = attrib(default=None, cmp=False)
   ...:

In [3]: LinkedList(5, LinkedList("ab", LinkedList(0.36))) == LinkedList(5, LinkedList("foo"))
Out[3]: True

Ich sehe da noch ein wenig Verbesserungspotential.

Meine Lösung in Haskell:

Code: Alles auswählen

data List a = Cons a (List a) | Nil

instance Eq a => Eq (List a) where
   Cons a as == Cons b bs = a == b && as == bs
   Nil == Nil = True
   _ == _ = False
   
main :: IO ()
main = print $ Cons 42 (Cons 27 Nil) == Cons 42 (Cons 5 Nil) -- ⇒ False

[__blackjack__]

@narpfel: Ich weiss jetzt nicht was Du damit sagen willst? ``==`` vegleicht ja nicht die ganze Liste sondern nur einen Knoten. Das halt nur anhand des Wertes und das soll und muss auch so. Das `next` (`nachfolger`) von dem Vergleich ausgenommen ist, braucht man dann in der `equals()`-Methode (`gleich()`) die laut Aufgabenstellung implementiert werden soll. Die habe ich noch nicht gezeigt, weil das ja noch eine offene Aufgabe für d_rose ist. Also man braucht es nicht zwingend, aber es macht den Code einfacher wenn man in der `equals()` einfach ``==`` auf den Knoten verwenden kann ohne prüfen zu müssen ob der Knoten eventuell `None` ist, weil man *da* ja nicht auf das `value`/`eintrag`-Attribut zugreifen kann.

Edit: Obwohl die Lösung ja sowieso nicht so einfach 1:1 übernommen werden kann, also hier ist die `equals()` für die ich die Änderung an den Vergleichen gemacht hatte:

Code: Alles auswählen

from itertools import takewhile, zip_longest
from operator import attrgetter

from attr import attrib, attrs
from more_itertools import iterate


@attrs
class LinkedList:
    value = attrib()
    next = attrib(default=None, cmp=False)

    def __iter__(self):
        return takewhile(bool, iterate(attrgetter('next'), self))

    def equals(self, other):
        return all(a == b for a, b in zip_longest(self, other))

Ohne könnte man die einzelnen Knoten nicht einfach mit ``a == b`` vergleichen, sondern müsste dort explizit `a` und `b` gegen `None` prüfen bevor man deren `value`-Attribute vergleicht.

Edit2: Alternativ, wenn man tatsächlich den ``==``-Operator überschreiben wollte, müsste es so aussehen:

Code: Alles auswählen

@attrs
class LinkedList:
    value = attrib()
    next = attrib(default=None)

    def __iter__(self):
        return takewhile(bool, iterate(attrgetter('next'), self))

    def __eq__(self, other):
        return all(
            a and b and a.value == b.value for a, b in zip_longest(self, other)
        )

    def __ne__(self, other):
        return not self == other
    
    def __hash__(self):
        raise TypeError(f'unhashable type: {self.__class__.__name__!r}')

[__blackjack__]

Mal der gesamte Code den ich hier habe, allerdings wie bisher halt auch schon mit zusätzlichen Bibliotheken, damit ich nicht alles selbst implementieren muss:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import takewhile, zip_longest
from operator import attrgetter

from attr import attrib, attrs
from more_itertools import iterate, last


@attrs(cmp=False)
class LinkedList:
    value = attrib()
    next = attrib(default=None)

    def __iter__(self):
        return takewhile(bool, iterate(attrgetter('next'), self))

    def __eq__(self, other):
        return all(
            a and b and a.value == b.value for a, b in zip_longest(self, other)
        )
    
    def __ne__(self, other):
        return not self == other
    
    def __hash__(self):
        raise TypeError(f'unhashable type: {self.__class__.__name__!r}')

    def append(self, value):
        last(self).next = LinkedList(value)


def main():
    list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
    print('list_a', list_a)
    print('list_a third value', list_a.next.next.value)
    
    list_b = LinkedList(1, LinkedList(2))
    print('list_b', list_b)
    list_c = LinkedList(1, LinkedList(2, LinkedList(3)))
    print('list_c', list_c)
    print('list_b equals list_c', list_b == list_c)
    print('append 3 to list_b')
    list_b.append(3)
    print('list_b', list_b)
    print('list_b equals list_c', list_b == list_c)
    
    # list_d = LinkedList()
    # print('list_d', list_d)
    # list_d.append(42)
    # list_d.append(23)
    # print('list_d', list_d)


if __name__ == '__main__':
    main()

An dem auskommentierten Codeschnippsel am Ende der `main()`-Funktion sieht man was an dieser Darstellung der verketteten Liste unschön ist, und warum man die Knoten-Objekte in der Regel noch einmal in einer weiteren Klasse kapselt: Man kann nicht so einfach mit einer *leeren* Liste starten, die ja eigentlich als `None` definiert ist durch die Aufgabe, und dann von da ausgehend Elemente anhängen. Man kann das natürlich auch mit dieser einen, der Knoten-Klasse, lösen. Dazu müsste man als Wert einen speziellen Wert einführen, der einen ”leeren” Knoten repräsentiert und auf den entsprechend in den Methoden getestet wird.

[__blackjack__]

Eigentlich möchte man ja über die Werte iterieren und nicht über die Knoten, damit sich das ein bisschen mehr wie normale Listen verhält. Aus dem gleichen Grund gibt's jetzt noch eine `__getitem__()`-Methode, damit man an das dritte Element auch über ``list_a[2]`` heran kommt.

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import takewhile, zip_longest
from operator import attrgetter

from attr import attrib, attrs
from more_itertools import iterate, last, nth


@attrs(cmp=False)
class LinkedList:
    value = attrib()
    next = attrib(default=None)

    def __iter__(self):
        return map(attrgetter('value'), self._iter_nodes())
    
    def __getitem__(self, index):
        node = nth(self._iter_nodes(), index)
        if not node:
            raise IndexError(f'index {index!r} out of range')
        return node.value
    
    def __eq__(self, other):
        return all(
            a and b and a.value == b.value
            for a, b in zip_longest(self._iter_nodes(), other._iter_nodes())
        )
    
    def __ne__(self, other):
        return not self == other
    
    def __hash__(self):
        raise TypeError(f'unhashable type: {self.__class__.__name__!r}')

    def _iter_nodes(self):
        return takewhile(bool, iterate(attrgetter('next'), self))

    def append(self, value):
        last(self._iter_nodes()).next = LinkedList(value)


def main():
    list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
    print('list_a', list_a)
    print('list_a third value', list_a.next.next.value)
    print('list_a[2]', list_a[2])
    
    list_b = LinkedList(1, LinkedList(2))
    print('list_b', list_b)
    list_c = LinkedList(1, LinkedList(2, LinkedList(3)))
    print('list_c', list_c)
    print('list_b equals list_c', list_b == list_c)
    print('append 3 to list_b')
    list_b.append(3)
    print('list_b', list_b)
    print('list_b equals list_c', list_b == list_c)
    
    # list_d = LinkedList()
    # print('list_d', list_d)
    # list_d.append(42)
    # list_d.append(23)
    # print('list_d', list_d)


if __name__ == '__main__':
    main()