Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Circular linked list

14/23
Recursos

Aportes 11

Preguntas 2

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta 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.

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

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)

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

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

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

Mi aporte con los métodos de clases anteriores.

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