# länkad lista
#
# En länkad lista består av nod-objekt:
#
# +----+----+
# |data|next|
# +----+----+
#
# False avslutar listan:
#
# +---+---+   +---+---+   +---+-----+
# | | | ----->| | | ----->| | |False|
# +-|-+---+   +-|-+---+   +-|-+-----+
#   V           V           V      
#   1           2           3      
#


# Listnod
#
class Node (object):
    def __init__ (self, data, nextNode):
        self.data = data
        self.nextNode = nextNode

# Konstruera en listnod
# (kan också göras genom att helt enkelt anropaNode (data, nextNode))
#
# Denna operation kan också tolkas som att vi returnerar en ny lista
# med data som första element, följt av alla element i listan
# nextNode.
#
def cons (data, nextNode):
    return Node (data, nextNode)

# Returnera en listas första element
#
def first (ls):
    return ls.data

# Returnera alla element i listan utom det första
#
def rest (ls):
    return ls.nextNode

# Konstruera lista med ett element
#
def list1 (data1):
    return cons (data1, False)
    
# Konstruera lista med två element
#
def list2 (data1, data2):
    return cons (data1, cons (data2, False))

# Konstruera lista med tre element
#
def list3 (data1, data2, data3):
    return cons (data1, cons (data2, cons (data3, False)))

# Skriv ut lista
# (något mer komplicerad version än den vi gick igenom på
# föreläsningen för att få utskriften snygg)
#
def printList (ls):
    print ("[", end="")
    # Finns åtminstone ett element i listan?
    if ls:
        # Skriv ut första elementet utan inledande komma och mellanslag
        print (first (ls), end="")
        # Skriv ut resten
        ls = rest (ls)
        while ls:
            print (",", first (ls), end="") # komma och mellanslag först
            ls = rest (ls)
    print ("]")

# Sätt samman listorna ls1 och ls2, dvs returnera en lista med alla
# element i ls1 följt av alla element i ls2
#
def append (ls1, ls2):
    if not ls1:
        # Om ls1 är en tom lista är sammanslagningen bara ls2.
        return ls2
    else:
        # Förenkla problemet genom att sätta samman lösningen med
        # hjälp av sammanslagningen av *resten* av elementen i ls1
        # och ls2.
        return cons (first (ls1), # vi börjar med första elementet i ls1
                     append (rest (ls1), # sedan resten av ls1
                             ls2))       # och till sist ls2

# Returnera listan ls omvänd, dvs returnera en lista med alla element
# i ls fast i omvänd ordning
#
def reverse (ls):
    # Om ls är en tom lista är omvändningen helt enkelt en tom lista.
    if not ls:
        return False
    else:
        # Förenkla problemet genom att sätta samman lösningen som
        # omvändningen av resten av ls plus första elementet i ls.
        return append (reverse (rest (ls)), list1 (first (ls)))

# Demonstration

ls1 = list2 (1, 2)
ls2 = list3 (1, 2, 3)

print ("ls1: ", end="")
printList (ls1)

print ("ls2: ", end="")
printList (ls2)

print ("append (ls1, ls2) -> ", end="")
printList (append (ls1, ls2))

print ("reverse (ls2) -> ", end="")
printList (reverse (ls2))