Un puntatore, in ogni nodo, che punta al nodo precedente permette di ottimizzare il metodo pop_right().
Le operazioni di inserimento / rimozione in testa / coda hanno tutte complessità costante
- append_left(x)
- append_right(x)
- x <– pop_left()
- x <– pop_right()
e permettono di utilizzare la lista, in modo efficiente, sia come stack che come coda.
Classe nodo
Ogni nodo contiene due puntatori, prev e next
class Node:
def __init__(self, info):
self._info=info
self._next=None
self._prev=None
def set_info(self, info): self._info=info
def set_prev(self, prev): self._prev=prev
def set_next(self, next): self._next=next
def get_info(self): return self._info
def get_prev(self): return self._prev
def get_next(self): return self._next
Classe lista
La lista possiede due puntatori, alla testa e alla coda
class DL_List: # Double-linked List
def __init__(self):
self._head=None
self._tail=None
def is_empty(self):
return (self._head is None)
def size(self):
n=0
nodo=self._head
while(nodo is not None):
nodo=nodo.get_next()
n += 1
return n
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):
nodo=self._head
num=0
while(nodo is not None):
if(nodo.get_info() == info):
num += 1
nodo=nodo.get_next()
return num
def index(self, info):
nodo=self._head
pos=0
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_prev(None)
nodo.set_next(self._head)
if(self.is_empty()):
self._tail=nodo
else:
self._head.set_prev(nodo)
self._head=nodo
def append_right(self, info):
nnodo=Node(info)
nnodo.set_next(None)
if(self.is_empty()):
nnodo.set_prev(None)
self._head=nnodo
else:
nnodo.set_prev(self._tail)
self._tail.set_next(nnodo)
self._tail=nnodo
def pop_left(self):
if(self.is_empty()):
raise ValueError("Il nodo %s non esiste" %(info))
else:
nodo=self._head
self._head=nodo.get_next()
if(self.is_empty()):
self._tail=None
else:
self._head.set_prev(None)
return nodo.get_info()
def pop_right(self):
if(self.is_empty()):
raise ValueError("Il nodo %s non esiste" % (info))
else:
nodo=self._tail
self._tail=nodo.get_prev()
if (self._tail is None):
self._head = None
else:
self._tail.set_next(None)
return nodo.get_info()
def remove(self, info):
nodo=self._head
while(nodo is not None) and (nodo.get_info() != info):
nodo=nodo.get_next()
if(nodo is None):
raise ValueError("Il nodo %s non esiste" %(info))
else:
prev=nodo.get_prev()
next=nodo.get_next()
if(prev is None) and (next is None):
self._head=None
self._tail=None
elif(prev is None):
self._head=next
self._head.set_prev(None)
elif(next is None):
self._tail=prev
self._tail.set_next(None)
else:
prev.set_next(next)
next.set_prev(prev)
Test
stack=DL_List()
for x in range(10):
stack.append_left(x) # push(x)
while(not stack.is_empty()):
print(stack.pop_left(), end=" ") # pop()
print()
coda=DL_List()
for x in range(10):
coda.append_left(x) # enqueue(x)
while(not coda.is_empty()):
print(coda.pop_right(), end=" ") # dequeue()
Dopo l’input la lista è la seguente
Testa Coda | | <- 9 <-> 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> 0 ->
L’output dei due casi è
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9