linkedlists.py

'''
Tailz
'''

class Empty:
    def __init__(self):
        self.isEmpty = True

class Node:
    def __init__(self, value, tail):
        self.isEmpty = False
        self.value = value
        self.tail = tail

    def printAll(self):

        while True:

            if self.isEmpty == True:
                break

            print self.value

            #self, dus Node(a), overschrijven met zijn eigen tail,
            #dan wordt self > Node(b) in de volgende loop
            self = self.tail

    def size(self):

        count = 0
        while True:

            if self.isEmpty == True:
                break

            count += 1

            #ga naar de volgende node
            self = self.tail

        return count

    def get(self, index):

        count = 0
        while True:

            if self.isEmpty == True:
                break

            if count == index:
                return self.value

            count += 1

            #ga naar de volgende node
            self = self.tail

    def printAllReverse(self):

        #verkrijg de lengte door de eerder gemaakte method 'size'
        size = self.size()
        count = 1
        #zet een startwaarde (node) om naar terug te kunnen keren
        start = self

        while True:

            #indien leeg (einde), ga terug naar eerste node
            if self.isEmpty == True:
                self = start

            #als de counter bij het eind van de lijst is
            if size == count:

                print self.value

                #maak lijstje 1 korter
                size -= 1
                #reset naar beginwaarden voor nieuwe ronde loops
                count = 1
                self = start

            else:

                count += 1
                #ga naar de volgende node
                self = self.tail

            #als het lijstje op is
            if size == 0:
                break

    def delete(self, index):

        count = 0
        while True:

            if self.isEmpty == True:
                break

            if count == index:

                removed = self.value
                #overschrijft zichzelf met zijn staart, zodat hij zelf 'verdwijnt' en de node opschuift
                self = self.tail
                return removed

            count += 1
            self = self.tail


mijnList = Node('a', Node('b', Node('c', Node('d', Empty()))))

#mijnList.printAll()
opgeruimd = mijnList.delete(1)
print opgeruimd
#mijnList.printAll()

=== Comment van onze leraar ===

Het mag zowel met als zonder recursie, tenzij expliciet aangegeven in de opdracht. Wel wordt een recursie (als je er nieuw mee bent) als moeilijker beschouwd, maar ook als netter, en in een vervolg opdracht moet het persee met een recursie.

Je code lijkt te werken op delete() na: self = self.tail past de structuur namelijk niet aan, maar laat alleen de variabele self naar self.tail verwijzen.
Deze werkt beter:
"""
Deze oplossing werkt niet in geval van index==0, omdat self vanuit client code niet te wijzigen is.
"""
def delete2(self, index):
count = 0
currentNode = self

while count < index - 1:
    currentNode = currentNode.tail
    count += 1
print "count" + str(count)

removed = currentNode.tail.value
currentNode.tail = currentNode.tail.tail
return removed

Maar blijkt lastig in het geval dat index==0 is, en mag wat mij betreft worden overgeslagen voor die situatie.

printReverse mag ook korter, al hoewel deze oplossing minder snel is:
def printRev(self):
for i in range(self.size() - 1, -1, -1):
print self.get(i),
print

Verder gebruik je veel while true loops, wat ik opzich goedkeur (tenzij anders aangegeven, bijv. dmv recursies), maar het is netter om while true loops om te schrijven naar while conditie loops, indien dat opzich gemakkelijk gaat. Zo wordt printAll() dan:
def printAll2(self):
currentNode = self
while not currentNode.isEmpty:
print currentNode.value,

    currentNode = currentNode.tail
print  Verder ziet het er gevaarlijk uit (gevoelig voor problemen) indien je self. assigned (met een = erachter) aan een nieuwe waarde. Beter is om een nieuwe variabele te maken die naar hetzelfde verwijst als self:

currentNode = self
en om die continue te wijzigen:
currentNode = currentNode.tail