Classe lista concatenata

La lista concatenata ha l’obiettivo di ottimizzare le operazioni di inserimento e di rimozione degli elementi

Le informazioni sono salvate in nodi
Ogni nodo contiene un puntatore al prossimo nodo nella lista
Alla lista si accede conoscendo il puntatore alla testa (al primo a sinistra)

Realizza i metodi tradizionali per le strutture dati

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

class HL_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?

I metodi

append_left(x), aggiunge x a sinistra (in testa)
x <– pop_left(), restituisce l’elemento a sinistra (in testa) e lo elimina
is_empty(), la lista è vuota?

permettono di realizzare, in modo efficiente, uno stack

stack=HL_List()

for x in range(5):
    stack.append_left(x)

while(not stack.is_empty()):
    print(stack.pop_left(), end=" ")

Dopo l’input la lista è la seguente

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

L’output è

4 3 2 1 0

Coda?

I metodi

append_left(x)
x <– pop_right()
is_empty()

oppure

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

permettono di realizzare una coda (le operazioni sul lato destro NON sono efficienti)

coda = HL_List()

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

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

Dopo l’input la lista è la seguente

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

L’output è

0 1 2 3 4