Circular linked list

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.

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)

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

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

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

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

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

reto de todos los metodos pero para una circular linked list

from node import Node

class circular():
    def __init__(self):
        self.head = None
        self.size = 0
    
    def append(self, data, next = None):
               
        if self.head is None:
            self.head = Node(data)
            self.head.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = Node(data)
            current.next.next = self.head
            
        self.size += 1
        
    def iter(self):
        index = self.size
        current = self.head
        while index > -1:
            value = current.data
            current = current.next
            index -= 1
            yield value
        
    def str(self) -> str:
        list_items = list(self.iter())
        return ' -> '.join(list_items)

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

Lo importante a tener en cuenta es como se une la tail con el head

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            tail = self.head
            while tail.next != self.head:
                tail = tail.next
            
            tail.next = new_node
            new_node.next = self.head

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add_element(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def display(self):
        if self.is_empty():
            print("List is empty")
        else:
            current = self.head
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.head:
                    break
            print()


'''
En esta implementación, la clase Node representa un nodo individual en la lista enlazada circular. 
Cada nodo tiene un dato (data) y un enlace al siguiente nodo (next).

La clase CircularLinkedList es la lista enlazada circular propiamente dicha. 
Tiene un puntero a la cabeza (head) y proporciona métodos para verificar si la lista está vacía, 
agregar elementos y mostrar la lista.

Para utilizar la lista enlazada circular, puedes crear una instancia de la clase CircularLinkedList 
y agregar elementos utilizando el método add_element(). Luego, puedes mostrar los elementos de la lista 
utilizando el método display().

Aquí tienes un ejemplo de uso:'''


# Crear una instancia de la lista enlazada circular
my_list = CircularLinkedList()

# Agregar elementos a la lista
my_list.add_element(1)
my_list.add_element(2)
my_list.add_element(3)

# Mostrar los elementos de la lista
my_list.display()  # Resultado: 1 2 3  (se repetirá en un ciclo infinito)

# Agregar más elementos a la lista
my_list.add_element(4)
my_list.add_element(5)

# Mostrar los elementos de la lista nuevamente
my_list.display()  # Resultado: 1 2 3 4 5  (se repetirá en un ciclo infinito)


'''
En este ejemplo, se crea una instancia de la lista enlazada circular llamada my_list 
y se agregan elementos utilizando el método add_element(). Luego, se muestra la lista utilizando 
el método display(), lo cual imprimirá los elementos de la lista en un ciclo infinito.

Recuerda que en una lista enlazada circular, el último nodo apunta de nuevo al primer nodo, formando 
un ciclo continuo.'''

Este serian 5 nodos donde el último apunta al primero:

from node import Node

head = None
for count in range(1, 6):
    head = Node(count, head)

if head is None:
    head.next = head
else:
    probe = head
    while probe.next != None:
        probe = probe.next
    probe.next = head

print(probe.data)
print(probe.next.data)

esta vez busque la forma mas sencilla que me pude imaginar

from node import Node

canciones_choquibtown = [
    "De Donde Vengo Yo",
    "Fiesta Animal",
    "Nuquí (Te Quiero Para Mí)",
    "Somos Pacífico",
    "¡Tú Sabes!"
]

node_one = Node(canciones_choquibtown[0])
tail = node_one

for i in range(1, len(canciones_choquibtown)):
    new_node = None(canciones_choquibtown[i])
    tail.next = new_node
    new_node = tail

tail.next = node_one

class CircleLinkedList:
def init(self) -> None:
self.head= None
self.size=0

def append(self,data):
    node=Node(data)
    probe=self.head

    
    
    if self.head==None :  #Condicion para  lista vacia
        self.head=node
        self.head.next=self.head
        self.size+=1
        
    
    else: 
        while probe.next != self.head: #recorro los valores del nodo hasta que el siguiente sea el primero
            probe=probe.next
        
        probe.next=node  #hago que el siguiente sea el nodo que agrego
        probe.next.next=self.head #hago que el siguiente del nodo que agrego sea el primero 
        self.size+=1 #incremento lista

Lo que pongo en la terminal para ejecutar la funcion

b= CircleLinkedList()

b.append(“ya vamos a mitad de curso =D”)
b.append(“Más cerca de ser expertos en python =D”)
b.append(“lo dire de nuevo por la emocion”)
print(b.head.data)
print(b.head.next.data)
print(b.head.next.next.data)
print(b.head.next.next.next.data)
print(b.head.next.next.next.next.data)
print(b.size)

LO QUE IMPRIME

ya vamos a mitad de curso =D -primer nodo
Más cerca de ser expertos en python =D -segundo nodo
lo dire de nuevo por la emocion -tercer nodo
ya vamos a mitad de curso =D -primer nodo
Más cerca de ser expertos en python =D - segundo nodo …etc

Mi aporte con los métodos de clases anteriores.

Esta fue mi solucion:

from node import Node

class CircularList:
def init(self):
self.index = 0
self.head = Node(None, None)
self.head.next = self.head

def append(self, data):
    probe = self.head

    if self.index == 0:
        self.head = Node(data, None)
        self.head.next = self.head
        self.index +=1
        return

    while probe.next != self.head:
        probe = probe.next

    probe.next = Node(data, probe.next)
    self.index +=1

def iter(self):
    current = self.head
    while current:
        val = current.data
        current = current.next
        yield val

def run():

words = CircularList()
words.append("-1-")
words.append("-2-")
words.append("-3-")
index = words.head
for i in range(1,10):
    print(index.data)
    index = index.next

if name == ‘main’:
run()

Operaciones con Circular Linked List:

from node import Node

class CircularListSingle:

    POSITION = 1
    DATA = 2

    def __init__(self, node = None, size = 0):
        self.__node = node
        self.__size = 0

    def load_node(self, init, end):
        node = None
        first_node_insert = None
        for count in range(init, end):
            node = Node(count, node)
            #El primer nodo es el último
            if first_node_insert is None:
                first_node_insert = node
            self.__size += 1
        
        first_node_insert.next = node
        
        self.__node = node

    def __str__(self):
        node = self.__node
        ret = ""
        if self.__size > 0:
            position = 1
            while position <= self.__size:
                ret += f'Posición {position} dato {node.data}\n\r'
                node = node.next
                position += 1
        return ret

    def print_double(self, register):
        node = self.__node
        ret = ""
        if self.__size > 0:
            position = 1
            while register > position:
                ret += f'Posición {position} dato {node.data}\n\r'
                node = node.next
                position += 1
        print(ret)

    #Agregamos nodos en cualquier posición permitida
    def add(self, position, node):
        if self.__node is None:
            self.__node = node
            node.next = node
            self.__size += 1
        elif position <= 0:
            #Se registra al principio
            first_node = self.__node 
            node.next = first_node
            self.__node = node
            #Adquirimos el último nodo
            last_node = self.get_last_node()
            last_node.next = self.__node
            self.__size += 1
        else:
            try:
                #Obtenemos el nodo en la posición previa a donde insertar
                find_previous_node_position = self.__find_by_position(position - 1)
                assert not find_previous_node_position is None, f'The position {position} is not allowed'
                #Al nuevo nodo le agregamos el siguiente nodo del nodo encontrado, si tiene dato, es decir, no es el último
                node.next = find_previous_node_position.next
                #El nodo encontrado, en la posición siguiente, le agregamos el nodo
                find_previous_node_position.next = node
                self.__size += 1
            except AssertionError as ae:
                print(ae)

    def get_last_node(self):
        return self.__find_last_node()

    def __find_last_node(self):
        node = self.__node

        if self.__size < 2:
            return self.__node

        first_node = self.__node
        position = 1
            
        while node.next != first_node:
            node = node.next
            position += 1
        return node

    def __find_by_position(self, position):
        node_ret = self.__node
        item = 1
        while node_ret != None and item != position:
            node_ret = node_ret.next
            item += 1

        return node_ret

    def __find_by_data(self, data):
        node_ret = self.__node
        while node_ret != None and node_ret.data != data:
            node_ret = node_ret.next
        return node_ret

    def __find_position_by_data(self, data):
        position_ret = 1
        node = self.__node
        while node != None and node.data != data:
            position_ret += 1
            node = node.next
        return position_ret

    def update(self, by, search, data):
        try:
            assert by in (self.POSITION, self.DATA), f'{by} no es un tipo de dato mi_singlylistlinked_simple.mi_singlylistlinked_simple_by'
            if by == self.POSITION:
                node = self.__find_by_position(search)
            if by == self.DATA:
                node = self.__find_by_data(search)
            assert not node is None, f'The node {search} not found'
            node.data = data
        except AssertionError as ae:
            print(ae)


    def remove(self, by, search):
        try:
            assert by in (self.POSITION, self.DATA), f'{by} no es un tipo de dato mi_singlylistlinked_simple.mi_singlylistlinked_simple_by'
            if by == self.POSITION:
                #Si es el primer nodo
                if search == 1:
                    #Movemos una posición
                    self.__node = self.__node.next
                    last_node = self.__find_last_node()
                    last_node.next = self.__node
                    self.__size -= 1
                    return True
                #Buscamos el nodo en la posición
                node = self.__find_by_position(search - 1)
            if by == self.DATA:
                #Obtenemos la posición del dato del nodo y llamamos a la misma función
                return self.remove(self.POSITION, self.__find_position_by_data(search))

            assert not node is None, f'The node {search} not found'
            node.next = node.next.next
            self.__size -= 1
            return True
        except AssertionError as ae:
            print(ae)
            return False
    

    

Pruebas:

from mi_circularlistlinked_simple import CircularListSingle
from node import Node

def run():
    linked_list = CircularListSingle()
    linked_list.load_node(1, 6)
    print(linked_list)
    linked_list.add(3, Node('W'))
    print(linked_list)
    linked_list.add(6, Node('Z'))
    print(linked_list)
    linked_list.add(9, Node('CX'))
    print(linked_list)
    linked_list.update(CircularListSingle.POSITION, 5, 'Actualizar')
    print(linked_list)
    linked_list.update(CircularListSingle.DATA, 'Actualizar', 'Nuevamente actualziado')
    print(linked_list)

if __name__ == '__main__':
    run()

Aquí está mi lista circular.

Mi solución para las circular linked list con 2 metodos: append y pop:

class CircularLinkedList(SinglyLinkedList):

    def __init__(self):
        super().__init__()

    def append(self, data):

        if self.tail == None:
            self.tail = Node(data, self.tail)
            self.tail.next = self.tail
        else:
            current = self.tail
            while current.next != self.tail:
                current = current.next
            
            current.next = Node(data, self.tail)

        self.size += 1

    def pop(self):

        if self.tail.next == self.tail:
            self.tail == None
        else:
            current = self.tail
            while current.next.next != self.tail:
                current = current.next

            current.next = self.tail
        
        self.size -= 1

Hay una herencia de la clase anterior para ahorrar unos cuantos pasos

if you want to learn more about Data Structures, visit next link:
https://www.tutorialspoint.com/python_data_structure/python_linked_lists.htm

Esta es mi solucion para crear una circular linked list

Y tambien agregue este if al metodo de iter para no generar un loop infinito