#!/usr/bin/env python

# Implementierung der doppelt verketteten Liste
# mit drei Arrays (vgl. Cormen S. 242 ff.)
# ohne 

class ListeArrays:
    def __init__(self, groesse):
        self.length = groesse
        self.werte = groesse*[None]
        self.nexts = groesse*[None]
        self.prevs = groesse*[None]
        self.werte[0] = "Nil"    # Sentinel
        self.nexts[0] = 0
        self.prevs[0] = 0

    def free(self):
        for i in range(self.length):
            if self.werte[i] == None: return i
        return -1 # Fehler

    def dump(self):
        print(self.werte)

    def delete(self,position):
        self.nexts[self.prevs[position]] = self.nexts[position]
        self.prevs[self.nexts[position]] = self.prevs[position]
        self.werte[position] = None

    def insert(self, wert):
        index = self.free()
        self.werte[index] = wert
        self.nexts[index] = self.nexts[0]
        self.prevs[self.nexts[index]] = index
        self.nexts[0] = index
        self.prevs[index] = 0

    def show(self):
        index = self.nexts[0]
        while index != 0:
            print (self.werte[index], end=',')
            index = self.nexts[index]
        print ()  # Zeilenumbruch

    def search(self, wert):
        index = self.nexts[0]
        while (index != 0) and (self.werte[index] != wert):
            index = self.nexts[index]
        return index

# Tests
b = ListeArrays(20); x = "TEST"
for i in range(5): b.insert(i)
b.insert(x)
for i in range(5,10): b.insert(i)
b.dump(); b.show()
b.delete(6); 
b.dump(); b.show()
b.insert("NEU")
b.dump(); b.show()
print ("(Suche gibt Positionen zurück)")
print ("Suche nach 3:   ", b.search(3))
print ("Suche nach 100: ", b.search(100))