Python: lista vinculada avanzada
Ya hemos visto Linked List en el capítulo anterior en el que solo es posible viajar hacia adelante. En este capítulo vemos otro tipo de lista enlazada en la que es posible viajar tanto hacia adelante como hacia atrás. Esta lista enlazada se denomina Lista doblemente enlazada. A continuación se muestran las características de la lista doblemente enlazada.
- La lista doblemente enlazada contiene un elemento de enlace llamado primero y último.
- Cada enlace lleva un campo de datos y dos campos de enlace llamados siguiente y anterior.
- Cada enlace está vinculado con su siguiente enlace utilizando su siguiente enlace.
- Cada enlace está vinculado con su enlace anterior utilizando su enlace anterior.
- El último enlace lleva un enlace como nulo para marcar el final de la lista.
Creando una lista doblemente enlazada
Creamos una lista Doblemente Vinculada usando la clase Node. Ahora usamos el mismo enfoque que se usó en la Lista de enlaces sencillos, pero el encabezado y los punteros siguientes se utilizarán para la asignación adecuada para crear dos enlaces en cada uno de los nodos además de los datos presentes en el 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)
Cuando se ejecuta el código anterior, produce el siguiente resultado:
62 8 12
Insertar en una lista doblemente vinculada
aquí vamos a ver cómo insertar un nodo en la lista de enlaces dobles usando el siguiente programa. El programa usa un menthod llamado insert que inserta el nuevo nodo en la tercera posición del encabezado de la lista doblemente enlazada.
# 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)
Cuando se ejecuta el código anterior, produce el siguiente resultado:
62 8 13 12
Agregar a una lista doblemente enlazada
Agregar a una lista doblemente enlazada agregará el elemento al final.
# 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)
Cuando se ejecuta el código anterior, produce el siguiente resultado:
62 8 12 9 45
Tenga en cuenta la posición de los elementos 9 y 45 para la operación de adición.