Cursos Empresas Blog Live Conf Eventos Precios

0:003:38

Recursos

Resumen

¿Qué es una lista circularmente enlazada?

Las listas circularmente enlazadas son una variante intrigante de las listas enlazadas, donde el último nodo de la lista apunta de nuevo al primer nodo, creando así una estructura circular. Esta característica añade una versatilidad extra que no está presente en las listas lineales tradicionales, donde el último nodo apunta a null o a ninguno. Esta simple modificación permite realizar un recorrido circular a través de los nodos, lo cual puede ser útil en escenarios como el procesamiento continuo de datos o la implementación de estructuras de datos destinados a ciclos repetitivos.

¿Cómo implementar listas circularmente enlazadas en Python?

Al trabajar en Python, podemos crear una lista circularmente enlazada utilizando nuestra clase de nodo existente. Académicamente y en la práctica, este concepto es bastante directo si ya estás familiarizado con listas enlazadas. Aquí te mostramos cómo se puede lograr:

class Nodo:
    def __init__(self, valor=None):
        self.valor = valor
        self.next = None

# Inicializar el primer nodo
head = Nodo('jamón')
head.next = head

# Pro es un auxiliar para recorrer la lista
pro = head

# Asumimos una estructura lista más extensa
while True:
    nuevo_nodo = Nodo('nuevo_valor')
    if pro.next == head:
        break
    pro = pro.next

pro.next = nuevo_nodo
nuevo_nodo.next = head

Como puedes observar, el último nodo nuevo_nodo apunta de nuevo al head, creando una estructura circular cohesionada.

¿Qué beneficios trae la estructura circular?

Trabajar con listas circularmente enlazadas ofrece varios beneficios:

Recorrido continuo: La estructura circular permite un recorrido ininterrumpido, útil en la programación de algoritmos que deben retornar al inicio tras alcanzar el final.
Memoria dinámica: Al no tener que encontrar el final de la lista, el manejo de la memoria es más flexible, permitiendo insertions y deletions más eficientes.
Estructura simple: Comparado con las listas doblemente enlazadas, las listas circularmente enlazadas son más simples en términos de definición de nodos y enlaces.

Sin duda, las listas circularmente enlazadas son una herramienta poderosa al tratar con estructuras de datos dinámicas.

Experimenta y comprueba

El reto que se presenta con las listas circularmente enlazadas es implementar y expandir tus propias listas con múltiples nodos, asegurándote de que el último nodo apunte al primero. Tal práctica es invaluable para fortalecer tus habilidades de programación y tu comprensión de las estructuras de datos. ¡Adelante, experimenta, comprueba tus resultados y profundiza en los detalles de las estructuras de datos circulares!

Próximamente, exploraremos otro tipo de estructura afín, las Double Linked Lists, que ofrecen otras funcionalidades interesantes y útiles. ¿Interesante, verdad? ¡Sigue explorando y ampliando tus capacidades!

Listas Circulares en Python: Creación y Uso Práctico

Curso de Estructuras de Datos Lineales con Python

Clase 14 de 23

Clase 14 / 23

Hanns Maza

Hace 2 años

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

Comentarios (33)33 comentarios

Sebastian Penagos

Hace 5 años

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:

Dar la vuelta al turno de cada jugador en un juego multijugador
Gestionar el ciclo de vida de la aplicación de un sistema operativo determinado
Implementando un montón de Fibonacci

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.

Mauricio Gonzalez Falcon

Que hace el código si el usuario le asigna un valor a starting point? me parece que eso rompe la iteración.

Alexis Dorado Muñoz

Muchas gracias por tu aporte.

Jose Noriega

Juan Antonio Aramburo Pasapera

Hace 4 años

Si se pudiera te pondría más corazoness por usar type hints.

@jaarpa se agradece la intención jaja

Christian Andrés Espinosa Villagómez

Definitavamente toda la sección de nodos , fue un fracaso del profesor , no explica bien.

Julián Cárdenas

Hace 3 años

Sad :/

Orlando castellanos

ya dejen de utilizar la terminal por favor me confunde T.T

Germán García

🤣😂🤣 cuando empece este curso crei que yo iba a ser el unico con ese problema jajaja

Christian Molina Vázquez

Leonardo David Alonso Sosa

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

Neicer Vásquez

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.

Sebastián Andrés Sanhueza Tapia

Despues de harto debugging Lo resolví de la siguiente manera

Para hacerlo tuve que corregir varias cosas en el linked_list, le agregé una self.head, y modifiqué el método append para que head sea siempre fuera el primero nodo y para que tail siempre fuera el último, error que hace dos clases causo estragos en los cometarios de este curso

También añadí un nuevo método llamado Show para visualizar los nodos

y se ve así

Cuándo se vuelve circular la iteración nunca termina, por ende limité a que pasara dos veces por el head, por eso en la 2da imagen tuve que crear el head

Andres Montes

metodo para agregar un nuevo nodo a una circular linked list

Kevin Tovar

Andres Cueto Estrada

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

Daniel Chinome

share = comparte

Nice job!

Luis Eduardo Lerena Pereira

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

Miguel Torres

¡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ó.

DAVID IBARRA BETANZOS

Para que sirve un circular linked list?

Héctor Daniel Vega Quiñones

Profesor

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.

Nicolas Alpargatero

El repetir en una lista de reproducción

Alfonso Neil Jiménez Casallas

El problema de Josefo es una de las aplicaciones más conocidas con listas circulares, los invito a revisar su implementación en Python

Oscar Rogelio Heredia Ruiz

# 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)

Carlos Paredes

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

Diego Moreno Gallón

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

Recursos

Resumen

Listas Circulares en Python: Creación y Uso Práctico

Progreso del curso

Introducción a las estructuras de datos

Arrays

Linked lists

Stacks

Queues

Próximos pasos