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