Classe lista concatenata, con testa e coda

Se la lista concatenata ha un puntatore aggiuntivo alla sua coda (all’ultimo nodo a destra) è possibile ottimizzare l’operazione di inserimento in coda, append_right()

• append_right(x), aggiunge x a destra (in coda)
• append_left(x), aggiunge x a sinistra (in testa)
• x <– pop_right(), restituisce l’elemento in coda e lo elimina
• x <– pop_left(), restituisce l’elemento in testa e lo elimina
• x <– remove(x), elimina l’elemento x
• is_empty(), la lista è vuota?
• size(), quanti elementi contiene?
• count(x), quante volte è presente x
• index(x), a quale posizione è presente x?
• …

Classe nodo

class Node:
    def __init__(self, info):
        self._info=info
        self._next=None

    def set_info(self, info): 
        self._info=info
    def get_info(self): 
        return self._info
    def set_next(self, next): 
        self._next=next
    def get_next(self): 
        return self._next

Classe lista concatenata

class HTL_List:
    def __init__(self):
        self._head=None

    def is_empty(self):
        return (self._head is None)

    def size(self):
        num=0
        nodo=self._head
        while(nodo is not None):
            nodo=nodo.get_next()
            num += 1
        return num

    def exists(self, info):
        nodo=self._head
        while(nodo is not None) and (nodo.get_info() != info):
            nodo=nodo.get_next()
        return (nodo is not None)

    def count(self, info):
        num=0
        nodo=self._head
        while(nodo is not None):
            if(nodo.get_info() == info):
               num += 1
            nodo=nodo.get_next()
        return num

    def index(self, info):
        pos=0
        nodo=self._head
        while(nodo is not None) and (nodo.get_info() != info):
            pos += 1
            nodo=nodo.get_next()
        if (nodo is None):
            raise ValueError("Il nodo %s non esiste" % (info))
        else:
            return pos

    def append_left(self, info):
        nodo=Node(info)
        nodo.set_next(self._head)
        self._head=nodo

    def append_right(self, info):
        nnodo=Node(info)
        nnodo.set_next(None)

        if(self.is_empty()):
            self._head=nnodo
        else:
            nodo=self._head
            next=nodo.get_next()
            while(next is not None):
                nodo=next
                next=nodo.get_next()
            nodo.set_next(nnodo)

    def pop_left(self):
        if(self._head is None):
            raise ValueError("Il nodo %s non esiste" %(info))
        elif(nodo == self._head):
            self._head=nodo.get_next()
            return nodo.get_info()

    def pop_right(self):
        if(self.is_empty()):
            raise ValueError("Il nodo %s non esiste" % (info))
        else:
            prec=None
            nodo=self._head
            while(nodo.get_next() is not None):
                prec=nodo
                nodo=nodo.get_next()
            info=nodo.get_info()
            if(nodo == self._head):
                self._head=None
            else:
                prec.set_next(None)
            return info

     def remove(self, info): 
         prec=None 
         nodo=nodo=self._head 
         while(nodo is not None) and (nodo.get_info() != info): 
             prec=nodo 
             nodo=nodo.get_next() 
         if(nodo is None): 
             raise ValueError("Il nodo %s non esiste" %(info)) 
         elif(nodo == self._head): 
             self._head=nodo.get_next() 
         else: 
             prec.set_next(nodo.get_next())

Stack?

Come prima…

La lista diventa

Testa                Coda
  |                   |
  4 -> 3 -> 2 -> 1 -> 0 ->

L’output è

4 3 2 1 0

Coda?

I metodi

• append_right(x)
• x <– pop_left()
• is_empty()

permettono di realizzare efficientemente una coda

coda=HL_List()

for x in range(5):
    coda.append_right(x)

while(not coda.is_empty()):
    print(coda.pop_left())

La lista diventa

Testa                Coda
  |                   |
  0 -> 1 -> 2 -> 3 -> 4 ->

L’output è

0 1 2 3 4