Python: elenco collegato avanzato
Abbiamo già visto la lista collegata nel capitolo precedente in cui è possibile solo andare avanti. In questo capitolo vediamo un altro tipo di lista concatenata in cui è possibile viaggiare sia avanti che indietro. Tale elenco collegato è chiamato Elenco doppio collegamento. Di seguito sono riportate le caratteristiche della lista doppiamente collegata.
- La lista doppiamente collegata contiene un elemento di collegamento chiamato primo e ultimo.
- Ogni collegamento contiene uno o più campi dati e due campi di collegamento denominati successivo e precedente.
- Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.
- Ogni collegamento è collegato al collegamento precedente utilizzando il collegamento precedente.
- L'ultimo collegamento porta un collegamento come nullo per contrassegnare la fine dell'elenco.
Creazione di una lista doppiamente collegata
Creiamo un elenco Doubly Linked utilizzando la classe Node. Ora utilizziamo lo stesso approccio utilizzato nell'Elenco collegato singolarmente, ma per l'assegnazione corretta verranno utilizzati i puntatori head e next per creare due collegamenti in ciascuno dei nodi oltre ai dati presenti nel nodo.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class doubly_linked_list:
def __init__(self):
self.head = None
# Adding data elements
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Print the Doubly Linked list
def listprint(self, node):
while (node is not None):
print(node.data),
last = node
node = node.next
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)
Quando il codice sopra viene eseguito, produce il seguente risultato:
62 8 12
Inserimento in una lista doppiamente collegata
qui andremo a vedere come inserire un nodo nella Doubly Link List utilizzando il seguente programma. Il programma utilizza un metodo denominato insert che inserisce il nuovo nodo alla terza posizione dall'inizio della lista doppiamente concatenata.
# Create the Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Create the doubly linked list
class doubly_linked_list:
def __init__(self):
self.head = None
# Define the push method to add elements
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Define the insert method to insert the element
def insert(self, prev_node, NewVal):
if prev_node is None:
return
NewNode = Node(NewVal)
NewNode.next = prev_node.next
prev_node.next = NewNode
NewNode.prev = prev_node
if NewNode.next is not None:
NewNode.next.prev = NewNode
# Define the method to print the linked list
def listprint(self, node):
while (node is not None):
print(node.data),
last = node
node = node.next
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)
Quando il codice sopra viene eseguito, produce il seguente risultato:
62 8 13 12
Aggiunta a una lista doppiamente collegata
L'aggiunta a una lista doppiamente collegata aggiungerà l'elemento alla fine.
# Create the node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Create the doubly linked list class
class doubly_linked_list:
def __init__(self):
self.head = None
# Define the push method to add elements at the begining
def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode
# Define the append method to add elements at the end
def append(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = None
if self.head is None:
NewNode.prev = None
self.head = NewNode
return
last = self.head
while (last.next is not None):
last = last.next
last.next = NewNode
NewNode.prev = last
return
# Define the method to print
def listprint(self, node):
while (node is not None):
print(node.data),
last = node
node = node.next
dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)
Quando il codice sopra viene eseguito, produce il seguente risultato:
62 8 12 9 45
Notare la posizione degli elementi 9 e 45 per l'operazione di aggiunta.