Contenido del curso
Sebastian Penagos
Mauricio Gonzalez Falcon
Alexis Dorado Muñoz
Jose Noriega
Juan Antonio Aramburo Pasapera
Jose Noriega
Christian Andrés Espinosa Villagómez
Julián Cárdenas
Orlando castellanos
iecgerman .
Christian Molina Vázquez
Leonardo David Alonso Sosa
Neicer Vásquez
Sebastián Andrés Sanhueza Tapia
Alexis Dorado Muñoz
Andres Montes
Kevin Tovar
Andres Cueto Estrada
Daniel Chinome
Juan Antonio Aramburo Pasapera
Luis Eduardo Lerena Pereira
Miguel Torres
Luis Eduardo Lerena Pereira
DAVID IBARRA BETANZOS
Héctor Daniel Vega Quiñones
Nicolas Alpargatero
Alfonso Neil Jiménez Casallas
Oscar Rogelio Heredia Ruiz
Hanns Maza
Carlos Paredes
Carlos Paredes
Andres Montes
Diego Moreno Gallón
listas enlazadas circulares
Las listas enlazadas circulares son un tipo de lista enlazada en la que el último nodo apunta hacia el headde la lista en lugar de apuntar None. Esto es lo que los hace circulares.
Las listas enlazadas circulares tienen bastantes casos de uso interesantes:
Así es como se ve una lista enlazada circular:
Una de las ventajas de las listas enlazadas circulares es que puede recorrer toda la lista comenzando en cualquier nodo. Dado que el último nodo apunta al headde la lista, debe asegurarse de dejar de atravesar cuando llegue al punto de partida. De lo contrario, terminarás en un bucle infinito.
En términos de implementación, las listas enlazadas circulares son muy similares a la lista enlazada individualmente. La única diferencia es que puede definir el punto de partida cuando recorre la lista:
class CircularLinkedList: def __init__(self): self.head = None def traverse(self, starting_point=None): if starting_point is None: starting_point = self.head node = starting_point while node is not None and (node.next != starting_point): yield node node = node.next yield node def print_list(self, starting_point=None): nodes = [] for node in self.traverse(starting_point): nodes.append(str(node)) print(" -> ".join(nodes))
Atravesar la lista ahora recibe un argumento adicional starting_point, que se usa para definir el inicio y (debido a que la lista es circular) el final del proceso de iteración. Aparte de eso, gran parte del código es el mismo que teníamos en nuestra LinkedListclase.
Que hace el código si el usuario le asigna un valor a starting point? me parece que eso rompe la iteración.
Muchas gracias por tu aporte.
Simple circular linked list.
from typing import Optional from typing import Any from node import Node class CicularLinkedList: _head: Optional[Node] = None _size: int = 0 def __init__(self, *items): """Initializes the circular linked list.""" self._head = None self._size = 0 for item in items: self.append(item) @property def size(self) -> int: """Returns the size of the circular linked list.""" return self._size def append(self, item: Any) -> None: """Appends an item to the end of the list. Time complexity: O(n) """ if self._head is None: self._head = Node(item) self._head.next = self._head else: current = self._head while current.next != self._head: current = current.next current.next = Node(item) current.next.next = self._head self._size += 1 def iter(self): """Iterates through the circular linked list.""" current = self._head while current.next != self._head: value = current.value current = current.next yield value yield current def iternodes(self): """Iterates through the circular linked list.""" current = self._head while current.next != self._head: yield current current = current.next yield current def __iter__(self) -> None: return self.iter() def __len__(self) -> int: return self._size def __str__(self) -> str: list_items = list(self.iter()) return ' -> '.join(str(item) for item in list_items) if __name__ == '__main__': import unittest class CircularLinkedListTestCase(unittest.TestCase): def test_initialize_empty(self): self.assertEqual(len(CicularLinkedList()), 0) def test_initialize_with_items(self): self.assertEqual(len(CicularLinkedList(1, 2, 3)), 3) def test_append(self): cll = CicularLinkedList() cll.append(1) cll.append(2) cll.append(3) self.assertEqual(len(cll), 3) def test_iter(self): cll = CicularLinkedList(1, 2, 3) self.assertEqual(list(cll), [1, 2, 3]) def test_first_node_linked_with_last_node(self): cll = CicularLinkedList(1, 2, 3) head = cll._head for item in cll.iternodes(): pass self.assertIs(head, item.next) unittest.main(verbosity=2)
Si se pudiera te pondría más corazoness por usar type hints.
@jaarpa se agradece la intención jaja
Definitavamente toda la sección de nodos , fue un fracaso del profesor , no explica bien.
Sad :/
ya dejen de utilizar la terminal por favor me confunde T.T
🤣😂🤣 cuando empece este curso crei que yo iba a ser el unico con ese problema jajaja
Mi solución para crear una lista circular enlazada de verios nodos.
from node import Node # Generación de lista de nodos enlazados head = None for count in range(1,10): head = Node(count, head) # Referenciar el ultimo nodo (tail) con el primer nodo(head) probe = head while probe.next != None: probe = probe.next probe.next = head # Agregar un nuevo elemento por "indice" (head a tail) index = 3 new_item = 'ham' probe = head if index <= 0: head = Node(new_item, head) else: probe = head while index > 1 and probe.next != head: probe = probe.next index -= 1 probe.next = Node(new_item, probe.next) # # Recorrer lista de manera circular steps = 15 probe = head while steps > 0: print(probe.data, end=' ') probe = probe.next steps -= 1 print() # Recorrer lista una vez probe = head while probe.next != head: print(probe.data, end=' ') probe = probe.next print(probe.data)
Salida
9 8 7 ham 6 5 4 3 2 1 9 8 7 ham 6 9 8 7 ham 6 5 4 3 2 1
Me parece que para cumplir que sea circular aun falta linkear el ultimo valor que toma probe con head, de lo contrario aun tienes una lista normal
Es un poco malo tener que decir que la clase no tiene un verdadero valor de conocimiento, pero enserio el profe solo se pone a escribir el código y decir lo que literal se entiende sin que lo explique. Además, este tema no es complicado pero el profe lo hace ver aburrido y eso es malo, porque hace que mejor uno vaya a Youtube o a un artículo donde se explica de mejor manera este tema. Platzi te pido que renueves el curso y por mi parte voy a dejar hasta aquí este curso porque en Youtube hay videos que lo explican mejor.
Despues de harto debugging Lo resolví de la siguiente manera
Muchas gracias por tu aporte.
metodo para agregar un nuevo nodo a una circular linked list
Les comparto mi codigo. La funcion circular la puse de ulltimo. si hay algun error o hice algo que no, me dicen porfa xd.
from node import Node class SinglyLinkedList: def __init__(self): self.head = None def remove_element_in_index(self, index): if index <= 0 or self.head.next is None: remove_item = self.head.data self.head = self.head.next print(remove_item) else: probe = self.head while index > 1 and probe.next.next != None: probe = probe.next index -= 1 remove_item = probe.next.data probe.next = probe.next.next print(f'we remove: {remove_item}') def add_item(self, new_item, index): try: index = int(index) except ValueError: print(f'El indice "{index}" no es un numero') return False if self.head is None or index < 0: self.head = Node('py', self.head) else: probe = self.head while index > 1 and probe.next != None: probe = probe.next index -= 1 probe.next = Node(new_item, probe.next) def romove_element_of_tail(self): removed_item = self.head.data if self.head.next is None: self.head = None else: probe = self.head while probe.next.next != None: probe = probe.next removed_item = probe.next.data probe.next = None print(f'we remove: {removed_item}') #add elements to start and final def add_elements(self, new_start, new_final): self.head = Node(new_start, self.head) new_node = Node(new_final) if self.head is None: self.head = new_node else: probe = self.head while probe.next != None: probe = probe.next probe.next = new_node def remplace(self, data, new_item): probe = self.head target_item = data while probe != None and target_item != probe.data: probe = probe.next if probe != None: probe.data = new_item print(f'{new_item} replaced the old value in the node number {target_item}') else: print(f"the target item {target_item} is not in the linked list") def ranger(self): for count in range(1, 6): self.head = Node(count, self.head) def travel(self): probe = self.head while probe != None: print(probe.data) probe = probe.next def search(self, data): probe = self.head target_item = data while probe != None and target_item != probe.data: probe = probe.next if probe != None: print(f'target item {target_item} has been found') else: print(f'target item {target_item} is not in the linked list') def circular(self): probe = self.head while probe.next != None: probe = probe.next probe.next = self.head print(f'the final item "{probe.data}" aim: {probe.next.data}') if __name__ == '__main__': words = SinglyLinkedList() words.ranger() words.search(10) words.add_elements('e','t') # words.travel() # words.romove_element_of_tail() # words.travel() words.add_item(9,4) # words.remove_element_in_index(3) words.remplace(1, 7) words.travel() words.circular()
Salida:
target item 10 is not in the linked list 7 replaced the old value in the node number 1 e 5 4 3 9 2 7 t the final item "t" aim: e
Banda, la clase está muy revuelta, pero no nos compliquemos, para generar el Cirle Linked List solo hay que poner esto:
1.- Su circular linked list
class CircularLinkedList(LinkedList): def __init__(self) -> None: super().__init__() def append(self, data): super().append(data, self.head)
2.- Modificar las primeras líneas del append así:
def append(self, data, next = None): node = Node(data, next)
3.- Modificar los whiles en la Linked List original de la siguiente forma:
i = self.size while current.next and i>=0: current = current.next i -= 1 current.next = node
Hi Guys, i comparte my solution for circle linked list, in this solution you can insert the nodes number with your respective value
from node import Node class CircleLinkedList: def __init__(self) -> None: self.head = None self.size = 0 def append(self, data): """Insert a new Node data: is of value for Node """ node = Node(data) if self.head == None: self.head = node self.head.next = self.head else: node.next = self.head current = self.head while current.next != self.head: current = current.next current.next = node self.size += 1 def print(self): """Print all value of nodes """ current = self.head node_numbers = self.size while node_numbers > 0: print(f'The Node {current} have value {current.data}') current = current.next node_numbers -= 1 if __name__ == '__main__': node_numbers = int(input('Insert numbers of Nodes: ')) node = CircleLinkedList() total_nodes = node_numbers while node_numbers > 0: data_node = str(input(f'¿What is the value of node number {total_nodes - (node_numbers - 1)}?: ')) node.append(data_node) node_numbers -= 1 node.print()
share = comparte
Nice job!
Hector, buen día
Te quería consultar, estoy realizando el código que realizastes y lo que estoy viendo que al imprimir:
print(probe.data) print(probe.next.data)
la consulta no me devuelve las dos veces ham, sino que me devuelve: None ham
¿El comportamiento es el correcto? ¿Si se apuntara a sí mismo, no debería aparecer las dos veces "ham"?
Muchas gracias
¡Hola, Luis! 🤓
Al ejecutar data sobre probe sí se llama a None porque de esa manera apuntas al head y no al nodo. Por ello sale None.
Cuando ejecutas probe.next estás llamando al nodo que se instanció.
Muchas gracias
Para que sirve un circular linked list?
Las linked lists tienen un gran número de aplicaciones, pues a diferencia de una singly o doubly linked list permite iterar de forma circula (valga la redudancia) por todos sus elementos ayudando a reducir la complejidad algorítmica.
Un ejemplo puede ser nuestro sistema operativo, donde las aplicaciones son iteradas en forma concurrente para ejecutar sus procesos.
Un caso más sencillo puede ser un videojuego multiplayer tipo Mario Party donde cada jugador es un nodo. O incluso puedes crear una circular queue (queue basado en nodos) donde se atienda de forma concurrente front y rear.
Realmente hay infinidad de posibilidades.
El repetir en una lista de reproducción
El problema de Josefo es una de las aplicaciones más conocidas con listas circulares, los invito a revisar su implementación en Python
# Definimos una clase para los nodos de la lista class Node: def __init__(self, data, next_node): self.data = data # Dato que almacena el nodo self.next = next_node # Referencia al siguiente nodo # Creamos un nodo centinela (no contiene datos útiles, solo sirve como referencia inicial/final) head = Node(None, None) head.next = head # El centinela apunta a sí mismo, indicando que la lista está vacía (lista circular) # Función para insertar un nodo al final de la lista def insert_at_end(head, data): new_node = Node(data, head) # Creamos el nuevo nodo apuntando al centinela (como siguiente nodo) probe = head # Comenzamos desde el nodo centinela # Recorremos la lista hasta encontrar el último nodo (el que apunta al centinela) while probe.next != head: probe = probe.next probe.next = new_node # Enlazamos el último nodo con el nuevo nodo # Insertamos algunos elementos al final de la lista insert_at_end(head, "ham") insert_at_end(head, "cheese") insert_at_end(head, "lettuce") # Función para imprimir los elementos de la lista def print_list(head): probe = head.next # Empezamos con el primer nodo real (después del centinela) while probe != head: # Recorremos hasta volver al centinela print(probe.data) # Imprimimos el dato del nodo actual probe = probe.next # Avanzamos al siguiente nodo # Mostramos el contenido de la lista print_list(head)
modifique las clases
Node
SinglyLinkedList
DoubleLinkedList
CircularLinked
class Node: def __init__(self, data, child=None, parent=None): self.data = data self.child:Node = child self.parent:Node = parent def set_child(self, node): self.child = node node.parent = self def set_parent(self, node): self.parent = node node.child = self def __repr__(self): if isinstance(self.child, Node): return f"<Node({self.data}) {hex(id(self))}> -> Node({self.child.data})" else: return f"<Node({self.data}) {hex(id(self))}> -> {self.child}" def __str__(self): if isinstance(self.child, Node): return f"Node({self.data}) -> {self.child.__str__()}" else: return f"Node({self.data}) -> {self.child}" """ SinglyLinkedList el primer agregado es el tail el ultimo agregado es el head """ class SinglyLinkedList: def __init__(self): self.head:Node = None self.tail:Node = None self.size = 0 def __repr__(self): return f"<SinglyLinkedList({self.size})>" def __str__(self): if self.head: return self.head.__str__() else: return "None" def empty(self): self.tail = None self.head = None self.size = 0 def iter(self): probe = self.head while probe: yield probe probe = probe.child def has(self, data): for current_node in self.iter(): if current_node.data == data: return True return False def append_head(self, data): new_node = Node(data) if self.head: new_node.set_child(self.head) else: self.tail = new_node self.head = new_node self.size += 1 def append_tail(self, data): new_node = Node(data) if self.tail: new_node.set_parent(self.tail) else: self.head = new_node self.tail = new_node self.size += 1 def append_index(self, index, data): if index == 0: return self.append_head(data) if index == self.size: return self.append_tail(data) if index > self.size: return new_node = Node(data) i = 0 for node in self.iter(): if i == index: node.parent.set_child(new_node) new_node.set_child(node) i+=1 self.size += 1 def replace(self, find_data, new_data): for current_node in self.iter(): if current_node.data == find_data: current_node.data = new_data return True return False def delete(self, data): state = False for node in self.iter(): if node.data == data: state = True if self.size == 1: self.empty() break if node.parent == None: self.head = self.tail = node.child break if node.child == None: self.head = self.tail = node.parent break node.parent.set_child(node.child) return state def remove_index(self, index): if index == 0: return self.remove_head() if index == self.size: return self.remove_tail() if index > self.size: return i = 0 for node in self.iter(): if i == index: node.parent.set_child(node.child) i+=1 self.size -= 1 def remove_head(self): if self.head == None: return True, None remove_item = self.head self.head = remove_item.child self.size -= 1 return True, remove_item def remove_tail(self): remove_item = self.tail self.tail = remove_item.parent self.size -= 1 return remove_item """ DoubleLinkedList """ class DoubleLinkedList(SinglyLinkedList): def __init__(self): super().__init__() def __repr__(self): return f"<DoubleLinkedList({self.size})>" def iter_tail(self): probe = self.tail while probe: yield probe probe = probe.parent """ CircularLinked """ class CircularLinked: def __init__(self): self.head = None self.size = 0 def __repr__(self): return f"<CircularLinked({self.size})>" def __str__(self): if self.head: iter_child = self.iter_child() result = f"┌┬▸({next(iter_child).data})\n" for node in iter_child: result += f"│├▸({node.data})\n" result += "└┘" return result else: return 'None' def iter_child(self): head = self.head yield head probe = head.child while probe != head: yield probe probe = probe.child def iter_parent(self): tail = self.head.parent yield tail probe = tail.parent while probe != tail: yield probe probe = probe.parent def apend(self, data): new_node = Node(data) if self.head: new_node.set_parent(self.head.parent) new_node.set_child(self.head) else: new_node.set_child(new_node) self.head = new_node self.size += 1
Antes de la inserción: head/probe | v +-----+ +-----+ | None |--->| None | +-----+ +-----+ Después de la inserción: head probe | | v v +-----+ +-----+ +-----+ | None |--->| 'ham' |--->| None | +-----+ +-----+ +-----+
Antes de la inserción: head/probe | v +-----+ +-----+ | None |--->| None | +-----+ +-----+ Después de la inserción: head probe | | v v +-----+ +-----+ +-----+ | None |--->| 'ham' |--->| None | +-----+ +-----+ +-----+ ```Antes de la inserción: head/probe   |   v +-----+ +-----+ | None |--->| None | +-----+ +-----+ Después de la inserción: head probe   | |   v v +-----+ +-----+ +-----+ | None |--->| 'ham' |--->| None | +-----+ +-----+ +-----+
reto de todos los metodos pero para una circular linked list
Me encanta como volví un for loop que normalmente se usa para iterar un numero definido de veces en un ciclo infinito.
from data_structures.linked_list import SinglyLinkedList words = SinglyLinkedList() words.append("Hola") words.append("Esto") words.append("Es") words.append("Una") words.append("lista") words.append("Enlazada") words.append("Circular") head = words.head movement = head while movement.next != None: movement = movement.next movement.next = head contador = 0 print("Lista circular") for word in words.iter(): print(word.data) contador += 1 if contador == 30: print(f"Lista infinita en un for loop vamos en {contador} iteraciones") break
