No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Circular linked list

14/23
Recursos

Aportes 22

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸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:

  • 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

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()
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(鈥測a vamos a mitad de curso =D鈥)
b.append(鈥淢谩s cerca de ser expertos en python =D鈥)
b.append(鈥渓o 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 鈥tc

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