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

Curso de Estructuras de Datos Lineales con Python

Contenido del curso

Introducción a las estructuras de datos

Arrays

Linked lists

Stacks

Queues

Próximos pasos

23
Estructuras de Datos Lineales: Nodos y Arrays
01:51 min

Tomar examen

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

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!

Hanns Maza

Estudiante

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

Sebastian Penagos

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

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)

Juan Antonio Aramburo Pasapera

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

Sad :/

Orlando castellanos

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

iecgerman .

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

Christian Molina Vázquez

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

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

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

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

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!

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 |
+-----+  +-----+  +-----+

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

&#x20; |

&#x20; v

+-----+    +-----+

| None |--->| None |

+-----+    +-----+



Después de la inserción:



head    probe

&#x20; |       |

&#x20; 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

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

Introducción a las estructuras de datos

Estructuras de Datos Lineales con Python: Arrays, Listas y Pilas

Estructuras de Datos y Colecciones en Python

Tipos y Estructuras de Colecciones de Datos en Programación

Operaciones esenciales en colecciones de Python

Colecciones en Python: Listas, Tuplas, Conjuntos y Diccionarios

Arrays

Arrays: Estructuras de Datos Lineales y sus Aplicaciones

Creación de un Array Personalizado en Python

Arrays Bidimensionales en Python: Creación y Métodos Básicos

Linked lists

Estructuras de Datos: Nodos y Listas Enlazadas Simples

Creación y Manipulación de Nodos en Python

Estructuras de Datos: Implementación de Listas Enlazadas Simples en Python

Operaciones en Single Link List: Búsqueda, Inserción y Eliminación

Operaciones en Listas Enlazadas: Búsqueda, Inserción y Eliminación