Contenido del curso
Gilberto Pérez Garrido
Rosse SPA
Hanns Maza
Christian Molina Vázquez
Sebastian Penagos
Alexis Dorado Muñoz
Santiago Ortiz Ceballos
Lorenzo Alejandro Guerrero Gómez
Alexis Dorado Muñoz
Nicolas Alpargatero
iecgerman .
Nicolas Alpargatero
Jose Noriega
Alexis Dorado Muñoz
Juan Pablo Leyva
Usuario anónimo
Héctor Daniel Vega Quiñones
Nieng Yordan Lee Gaitan
iecgerman .
Manuel Rodrigo Zamorano Jimenez
Juan Camilo Suarez
Eduardo Kiriakos Piazza
Kevin Tovar
Miguel Angel Reyes Moreno
Luis Eduardo Lerena Pereira
Ulises Alejandro Mánica Caricio
Dumar Estiven Angulo Sanchez
José Joaquín Tripp Gudiño
Rigoberto Maldonado
Rigoberto Maldonado
Rigoberto Maldonado
Rigoberto Maldonado
No me esta gustando el curso, todo lo está dejando como reto, más bien digan que les faltó contenido y fin
En realidad el hecho de que sean retos es bastante positivo, lo que sí se siente es que no se profundiza tanto en la explicación y este curso maneja varios conceptos que no son tan faciles de asimilar. No es un mal curso, pero considero que no es para personas que tengan 0 o bajo conocimiento de programación.
yo pienso que deberia de usarse jupyter notebooks ya que no todos comprender la logica interna..., usando la terminal como ejecutor no se comprende nada(aclaro solo para los que no interpretan que ocurre en el codigo)
por otro lado aprender a usar los metodos def _ _ str _ _ y _ _ repr _ _ son utiles para reprensentar la clase de una manera mas visual
si quieres usar jupyter notebooks en visual studio te dejo este link
si quieren utilicen mi codigo
para los nodos
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 ```y para los arrays ```python import random """ ARRAY """ class Array: def __init__(self, capacity, fill_value=None): self.capacity = capacity if callable(fill_value): self.items = [fill_value(i) for i in range(capacity)] else: self.items = [fill_value for _ in range(capacity)] def __len__(self): return len(self.items) def __repr__(self): return f"<Array({self.capacity}) {hex(id(self))}>" def __str__(self): color = lambda t: f"\u001b[96m{t}\u001b[39m" result = f"{color('[')}" def parse_str(val): if isinstance(val, str): return f"'{val}'" return val result = f"{result}{parse_str(self.items[0])}" for d in self.items[1:]: result = f"{result}, {parse_str(d)}" return f"{result}{color(']')}" def __iter__(self): return iter(self.items) def __getitem__(self, index): return self.items[index] def __setitem__(self, index, new_item): self.items[index] = new_item def fill_random(self, min, max, function_random=random.randint): for i in range(self.capacity): self.items[i] = function_random(min, max) def fill(self, value=None): for i in range(self.capacity): self.items[i] = value def join(self, separator=' '): result = self.items[0] for item in self.items[1:]: result = f"{result}{separator}{item}" return result def sum(self): result = 0 for item in self.items: result = result + item return result def reduce(self, func, init_val=0): for index in range(0, self.capacity): init_val = func(init_val, self.items[index], index) return init_val # menu = Array(4, lambda i: i) # print(menu) # print(repr(menu)) """ GRID """ class Grid(): def __init__(self, rows, columns, fill_value=None): self.height = rows self.width = columns if callable(fill_value): self.data = Array(rows, lambda r: Array(columns, lambda c: fill_value(r, c))) else: self.data = Array(rows, lambda _: Array(columns, fill_value)) def __getitem__(self, row, col=None): if col: return self.data[row][col] return self.data[row] def __setitem__(self, row, col, value): self.data[row][col] = value def __repr__(self): return f"<Grid({self.width}x{self.height}) {hex(id(self))}>" def __str__(self): color = lambda t: f"\u001b[95m{t}\u001b[39m" result = f"{color('[')}" result += f"\n {self.data[0].__str__()}" for row in self.data[1:]: result += f",\n {row.__str__()}" return f"{result}\n{color(']')}" def fill_random(self, min, max, function_random=None): if function_random: for row in self.data: row.fill_random(min, max, function_random) else: for row in self.data: row.fill_random(min, max) def fill(self, value=None): for row in self.data: row.fill(value) # matrix = Grid(4, 4, lambda r, c: f"{r}:{c}") # print(repr(matrix)) # print(matrix) """ CUBE """ class Cube(): def __init__(self, x, y, z, fill_value=None): self.x = x self.y = y self.z = z if callable(fill_value): self.space = Array(x, lambda r:Grid(y, z, lambda h, s: fill_value(r, h, s))) else: self.space = Array(x, lambda _:Grid(y, z, fill_value)) def __repr__(self): return f"<Cube({self.x}x{self.y}x{self.z}) {hex(id(self))}>" def __str__(self): color1 = lambda t: f"\u001b[93m{t}\u001b[39m" color2 = lambda t: f"\u001b[95m{t}\u001b[39m" result = f"{color1('[')}" def parse_str(grid:Grid): res = f"{color2('[')}" res += f"{grid[0].__str__()}" for arr in grid[1:]: res += f", {arr.__str__()}" return f"{res}{color2(']')}" result += f"\n {parse_str(self.space[0])}" for xs in self.space[1:]: result += f",\n {parse_str(xs)}" result = f"{result}\n{color1(']')}" return result def fill_random(self, min, max, function_random=None): if function_random: for grid in self.space: grid.fill_random(min, max, function_random) else: for grid in self.space: grid.fill_random(min, max) def fill(self, value=None): for grid in self.space: grid.fill(value) # rubik = Cube(3, 3, 3, lambda x, y, z: f"{x}:{y}:{z}") # print(repr(rubik)) # print(rubik)
Les comparto mi solución al reto. Me lleve unas horas pero cree la clase con los métodos vistos en clases pasadas y agregue unos cuantos más.
Este es el código de la clase que cree:
# ! Circle Double Linked List class circleDoubleLinkedList(): def __init__(self): self.head = TwoWayNode(None,None,None) self.tail = self.head self.size = 0 self.head.next = self.tail self.head.previous = self.tail def range(self, start, stop): # * Creación de los nodos enlazados (linked list) self.head = TwoWayNode(start, next=None, previous=None) self.tail = self.head self.size = 1 for data in range(start+1, stop): self.tail.next = TwoWayNode(data, previous=self.tail) self.tail = self.tail.next self.size += 1 self.tail.next = self.head self.head.previous = self.tail def __str__(self): # * Recorrer e imprimir valores de la lista probe = self.head result = '' while probe.next != self.head: result += f'{probe.data} ' probe = probe.next result += f'{probe.data}' result = result.strip() return result def reverse(self): probe = self.tail result = '' while probe.previous != self.tail: result += f'{probe.data} ' probe = probe.previous result += f'{probe.data}' result = result.strip() return result def str_by_steps(self, steps, direction='forward'): result = '' if direction == 'forward': probe = self.head while steps > 0: result += f'{probe.data} ' probe = probe.next steps -= 1 if direction == 'backward': probe = self.tail while steps > 0: result += f'{probe.data} ' probe = probe.previous steps -= 1 result = result.strip() return result def search(self, target_item): # * Busqueda de un elemento probe = self.head while probe.next != self.head and target_item != probe.data: probe = probe.next if probe.data == target_item: print(f'Target item {target_item} has been found') return probe else: print(f'Target item {target_item} is not in the linked list') return -1 def replace(self, target_item, new_item): # * Remplazo de un elemento probe = self.head while probe.next != self.head and target_item != probe.data: probe = probe.next if probe.data == target_item: probe.data = new_item print( f"{new_item} replace the old value {target_item}") else: print(f"The target item {target_item} is not in the linked list") def unshift(self, new_item): # * Insertar un nuevo elemento/nodo al inicio(head) if self.size == 0: self.head.data = new_item else: self.head = TwoWayNode(new_item, previous=self.tail, next=self.head) self.head.next.previous = self.head self.tail.next = self.head self.size += 1 def append(self, new_item): # * Insertar un nuevo elemento/nodo al final(tail) if self.size == 0: self.tail.data = new_item else: self.tail = TwoWayNode(new_item, previous=self.tail, next=self.head) self.tail.previous.next = self.tail self.head.previous = self.tail self.size += 1 def shift(self): # * Eliminar un elmento/nodo al inicio(head) if self.size == 0: return None removed_item = self.head.data self.head = self.head.next self.head.previous = self.tail self.tail.next = self.head self.size -= 1 print(f'Removed_item: {removed_item}') return removed_item def pop(self): # * Eliminar un elmento/nodo al final(tail) if self.size == 0: return None removed_item = self.tail.data self.tail = self.tail.previous self.head.previous = self.tail self.tail.next = self.head self.size -= 1 print(f'Removed_item: {removed_item}') return removed_item def insert(self, new_item, index): # * Agregar un nuevo elemento/nodo por "indice" (Cuenta de Head - Tail) if self.size == 0: self.head.data = new_item self.size += 1 elif index <= 0: self.unshift(new_item) elif index >= self.size - 1: self.append(new_item) else: probe = self.head while index > 1 and probe.next != self.head: probe = probe.next index -= 1 probe.next = TwoWayNode(new_item, previous=probe, next=probe.next) probe.next.next.previous = probe.next self.size += 1 def delete_by_index(self, index): # * Eliminar un nuevo elemento/nodo por "indice" (Cuenta de Head - Tail) if self.size == 0: return None if index <= 0: self.shift() elif index >= self.size - 1: self.pop() else: probe = self.head while index > 1 and probe.next.next != self.head: probe = probe.next index -= 1 removed_item = probe.next.data probe.next = probe.next.next probe.next.previous = probe self.size -= 1 print(f'Removed_item: {removed_item}') return removed_item def clear(self): self.__init__()
y estas son las pruebas de su funcionamiento, en esta parte me lleve más tiempo solucionando los bugs.
from double_linked_list import circleDoubleLinkedList circlue_doble_list = circleDoubleLinkedList() print('Prueba para ver si se inicializo correctamente:') print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba para agregar un elemento con la lista vacia:') circlue_doble_list.unshift(4) print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de generación de elementos por range:') circlue_doble_list.range(1, 6) print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de recorrido por pasos:') print(circlue_doble_list.str_by_steps(12, 'forward')) print(circlue_doble_list.str_by_steps(12, 'backward')) print() print('Prueba de busqueda:') circlue_doble_list.search(2) print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de remplazar un elmento:') circlue_doble_list.replace(3, 'replace_item') print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de insertar un nuevo elmento en head:') circlue_doble_list.unshift('unshift') print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de insertar un nuevo elmento en tail:') circlue_doble_list.append('append') print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de elminar el elemento en head: ') circlue_doble_list.shift() print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de elminar el elemento en tail: ') circlue_doble_list.pop() print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de insertar un elemento por indice: ') circlue_doble_list.insert("index", 1) print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de elminar un elemento por indice: ') circlue_doble_list.delete_by_index(3) print(circlue_doble_list) print(circlue_doble_list.reverse()) print() print('Prueba de limpieza de la lista: ') circlue_doble_list.clear() print(circlue_doble_list) print(circlue_doble_list.reverse()) print()
Y por ulimo los resultados
Prueba para ver si se inicializo correctamente: None None Prueba para agregar un elemento con la lista vacia: 4 4 Prueba de generación de elementos por range: 1 2 3 4 5 5 4 3 2 1 Prueba de recorrido por pasos: 1 2 3 4 5 1 2 3 4 5 1 2 5 4 3 2 1 5 4 3 2 1 5 4 Prueba de busqueda: Target item 2 has been found 1 2 3 4 5 5 4 3 2 1 Prueba de remplazar un elmento: replace_item replace the old value 3 1 2 replace_item 4 5 5 4 replace_item 2 1 Prueba de insertar un nuevo elmento en head: unshift 1 2 replace_item 4 5 5 4 replace_item 2 1 unshift Prueba de insertar un nuevo elmento en tail: unshift 1 2 replace_item 4 5 append append 5 4 replace_item 2 1 unshift Prueba de elminar el elemento en head: Removed_item: unshift 1 2 replace_item 4 5 append append 5 4 replace_item 2 1 Prueba de elminar el elemento en tail: Removed_item: append 1 2 replace_item 4 5 5 4 replace_item 2 1 Prueba de insertar un elemento por indice: 1 index 2 replace_item 4 5 5 4 replace_item 2 index 1 Prueba de elminar un elemento por indice: Removed_item: replace_item 1 index 2 4 5 5 4 2 index 1 Prueba de limpieza de la lista: None None
Cómo utilizar listas doblemente enlazadas
Las listas doblemente enlazadas se diferencian de las listas enlazadas individualmente en que tienen dos referencias:
El resultado final se ve así:
class Node: def __init__(self, data): self.data = data self.next = None self.previous = None
Este tipo de implementación le permitiría atravesar una lista en ambas direcciones en lugar de solo atravesar usando next. Puede utilizar next para avanzar y previous retroceder.
En términos de estructura, así es como se vería una lista doblemente enlazada:
Muchas gracias por tu aporte.
Tal vez ayude a comprender:
Excelente aporte.
Muchas gracias por tu aporte.
Me imagino que los que tiene bastante experiencia se les facilita aun como el transcribe solo el código, pero los que no, sinceramente que modulo tan mediocre. Los retos fueron vaya aprenda mejor en otros lados.
yo ya es la tercera vez que veo los videos y casi estoy igual jajaja
Te aconsejo que si quieres estructuras de datos y algoritmos ver los cursos de Camila, estoy haciéndolos y mucho mejor.
Double Linked List con operaciones y UnitTest
Linked List
from typing import Iterable from typing import Optional from typing import Union from node import TwoWayNode class DoubleLinkedList: _head: Optional[TwoWayNode] _size: int def __init__(self, *items): """Initializes a double linked list.""" self._head = None self._size = 0 if len(items) > 0 and isinstance(items[0], Iterable): items = items[0] for item in items: self.append(item) @property def size(self) -> int: """Returns the size of the list.""" return self._size def append(self, data: object): """Appends a node to the end of the list. Time complexity: O(n) """ new_node = TwoWayNode(data) if self._head is None: self._head = new_node else: current = self._head while current.next is not None: current = current.next current.next = new_node new_node.previous = current self._size += 1 def itervalues(self): """Iterates over the list.""" current = self._head while current is not None: yield current.value current = current.next def iteritems(self): """Iterates over the list.""" current = self._head while current is not None: yield current current = current.next def insert(self, index: int, value: object): """Inserts item before index. Time complexity: O(n) Args: index: The index to insert the item before. value: The value to insert. Returns: None """ if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('Index out of range') if index == 0: self._head = TwoWayNode(value, self._head) else: for idx, item in enumerate(self): if idx == index: new_node = TwoWayNode(value) new_node.next = item item.previous.next = new_node item.previous = new_node break self._size += 1 return None def index(self, target: object) -> int: """Returns the index of the value. Raises ValueError if the value is not in the list. Time complexity: O(n) Args: target: The value to find the index of. Returns: int: The index of the value. """ item: TwoWayNode for index, item in enumerate(self): if item.value == target: return index raise ValueError('Value not found') def clear(self): """Clears the list.""" self._head = None self._size = 0 def replace(self, old_value: object, new_value: object): """Replaces the old value with the new value. Raises ValueError if the value is not in the list. Time complexity: O(n) Args: old_value: The value to replace. new_value: The new value. Returns: None """ item: TwoWayNode for item in self: if item.value == old_value: item.value = new_value return None raise ValueError('Value not found') def pop(self, raw: bool = False) -> Union[object, TwoWayNode]: """Removes the last item and returns it. Time complexity: O(n) Args: raw: If True, returns the node instead of the value. Returns: object: The last item. """ if self._head is None: raise IndexError('List is empty') item: TwoWayNode for item in self: pass if item.previous is not None: item.previous.next = None self._size -= 1 if raw: return item return item.value def remove(self, target: object): """Removes the target from the list. Raises ValueError if the value is not in the list. Time complexity: O(n) Args: target: The value to remove. Returns: None """ item: TwoWayNode for item in self: if item.value == target: if item.previous is not None: item.previous.next = item.next if item.next is not None: item.next.previous = item.previous self._size -= 1 return None raise ValueError('Value not found') def reverse(self): """Reverses the double linked list. Time complexity: O(n) """ temp = None current = self._head # Swap next and previous for all nodes of the list while current is not None: temp = current.previous current.previous = current.next current.next = temp current = current.previous # Before changing the head, check for the cases like empty list if temp is not None: self._head = temp.previous def __getitem__(self, index: int) -> object: """Returns the item at the index. Raises IndexError if the index is out of range. Time complexity: O(n) Args: index: The index to get the item at. Returns: object: The item at the index. """ if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('Index out of range') item: TwoWayNode for idx, item in enumerate(self): if idx == index: return item.value return None def __setitem__(self, index: int, value: object): """Sets the item at the index. Raises IndexError if the index is out of range. Time complexity: O(n) Args: index: The index to set the item at. value: The value to set. Returns: None """ if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('Index out of range') if index == 0: self._head.value = value else: item: TwoWayNode for idx, item in enumerate(self): if idx == index: item.value = value break return None def __iter__(self): return self.iteritems() def __len__(self) -> int: """Returns the size of the list.""" return self._size def __delitem__(self, index: int): """Deletes the item at the index. Raises IndexError if the index is out of range. Time complexity: O(n) Args: index: The index to delete the item at. Returns: None """ if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('Index out of range') if index == 0: self._head = self._head.next else: item: TwoWayNode for idx, item in enumerate(self): if idx == index: if item.previous is not None: item.previous.next = item.next if item.next is not None: item.next.previous = item.previous self._size -= 1 break return None
UnitTest
# Unittest import unittest # Utils from double_linked_list import DoubleLinkedList class DoubleLinkedListTestCase(unittest.TestCase): """Test case for DoubleLinkedList""" def test_initialize_empty_list(self): """Test initialize empty list""" dll = DoubleLinkedList() self.assertEqual(dll.size, 0) def test_initialize_list_with_values(self): """Test initialize list with values""" dll = DoubleLinkedList(['a', 'b', 'c']) self.assertEqual(dll.size, 3) for a, b in zip(['a', 'b', 'c'], dll): self.assertEqual(a, b) def test_append_item(self): """Test append item""" dll = DoubleLinkedList() dll.append('a') self.assertEqual(dll.size, 1) def test_insert_item_at_first_position(self): """Test insert item at first position""" dll = DoubleLinkedList(1) dll.insert(0, 'a') self.assertEqual(dll.size, 2) for a, b in zip(['a', 1], dll): self.assertEqual(a, b) def test_insert_item(self): """Test insert item""" dll = DoubleLinkedList(['a', 'b', 'c']) dll.insert(1, 'd') self.assertEqual(dll.size, 4) for a, b in zip(['a', 'd', 'b', 'c'], dll): self.assertEqual(a, b) def test_index_item(self): """Test index item""" dll = DoubleLinkedList(['a', 'b', 'c']) self.assertEqual(dll.index('b'), 1) def test_index_item_not_found(self): """Test index item not found""" dll = DoubleLinkedList(['a', 'b', 'c']) self.assertRaises(ValueError, dll.index, 'd') def test_clear_list(self): """Test clear list""" dll = DoubleLinkedList(['a', 'b', 'c']) dll.clear() self.assertEqual(dll.size, 0) def test_replace_item(self): """Test replace item""" dll = DoubleLinkedList(['a', 'b', 'c']) dll.replace('b', 'd') self.assertEqual(dll.size, 3) for a, b in zip(['a', 'd', 'c'], dll): self.assertEqual(a, b) def test_replace_item_not_found(self): """Test replace item not found""" dll = DoubleLinkedList(['a', 'b', 'c']) self.assertRaises(ValueError, dll.replace, 'd', 'e') def test_replace_by_index(self): """Test replace by index""" dll = DoubleLinkedList(['a', 'b', 'c']) dll[1] = 'd' self.assertEqual(dll.size, 3) for a, b in zip(['a', 'd', 'c'], dll): self.assertEqual(a, b) def test_pop_item(self): """Test pop item""" dll = DoubleLinkedList(['a', 'b', 'c']) self.assertEqual(dll.pop(), 'c') self.assertEqual(dll.size, 2) for a, b in zip(['a', 'b'], dll): self.assertEqual(a, b) def test_remove_item_by_index(self): """Test remove item by index""" dll = DoubleLinkedList(['a', 'b', 'c']) del dll[1] self.assertEqual(dll.size, 2) for a, b in zip(['a', 'c'], dll): self.assertEqual(a, b) def test_reverse_list(self): """Test reverse list""" dll = DoubleLinkedList(['a', 'b', 'c']) dll.reverse() self.assertEqual(dll.size, 3) for a, b in zip(['c', 'b', 'a'], dll): self.assertEqual(a, b)
Muchas gracias por tu aporte.
Hola.
Me queda la duda de cual seria la razon para utilizar una linked list en lugar de una lista de python, ya que se puede obtener la misma funcionalidad con las segundas,
Pense que quiza la forma de recorrer la lista completa seria mas rapido en una linked list, pero hice unas pruebas y me parece que no. De hecho, las listas de python son el doble de rapidas recorriendo una lista del mismo tamaño elemento por elemento (Que seria la unica forma de recorrer una linked list).
Muchas gracias si alguien puede resolverme esta pequeña duda.
Size 10000 ********** Python list time: 0.0003509521484375 ********** Linked list time: 0.0005764961242675781
Code:
from time import time size = 10000 linked_list, l = SinglyLinkedList(), [i for i in range(1, size)] for i in range(1, size): linked_list.append(i) probe = linked_list.tail print(f"Size {size}") print("*" * 10) print("Python list time:") before = time() for e in l: _ = e print(time() - before) print("*" * 10) print("Linked list time:") before = time() while probe != None: probe = probe.next print(time() - before)
Hola Compañero digamos que en cuanto el tema de almacenar datos ya en memoria como ya sabes cada variable tendra un valor con direccion en memoria que normalemente un array o lista lo hara de manera contigua (alamcenar esos valores en memoria) y va a ver casos en los que ya no haya memoria CONTIGUA DISPONIBLE, aqui es cuando entra las hermosas LISTAS LINKEADAS ellas resuelven el problema de que cada nodo tendra un valor y la direccion en memoria del siguiente nodo o valor y funcionan como punteros es decir cada nodo va a apuntar a otro nodo aqui el almacenamiento en memoria ya no es contiguo ya funciona con punteros
Tal como explica Nildiert, se trata de un tema de optimización de espacio sobre tiempo. Optimizamos espacio o tiempo, pero no podemos tener ambas.
Además en las listas hay operaciones que como resultado generan una nueva lista y esto consume memoria.
Me siento como en la universidad, veo a un profesor hablar mucho y no entendí nada, ni su uso, ni utilidad y sin pedagogía.
porque al profe si le imprime el resultado usando probe.previous y a mi no, le tengo que quitar la o
DOUBLE_LNKED_LIST
class Node(object): def init(self, data, previous=None, next=None): self.data = data self.previous = previous self.next = next
from node import Node class TwoWayNode(Node): def init(self, data, previous=None, next=None): self.head = None self.tail = None self.size = 0
def append(self, data): node = Node(data) # PRIMER Nodo if self.head is None and self.tail is None: self.head = node self.tail = node # MAS DE UN Nodo else: node.previous = self.tail self.tail.next = node self.tail = node self.size += 1 def delete(self, data): # NO HAY Nodo(s) en la DobleLinkedList if self.head is None and self.tail is None: return False # SI HAY Nodo(s) en la DobleLinkedList else: probe = self.head # UNICO Nodo if probe.previous is None and probe.next is None: self.head = None self.tail = None self.size -= 1 return True # VARIOS Nodos else: while probe: # Encontrado if probe.data == data: # PRIMER Nodo de la DobleLinkedList if probe.previous is None and probe.next != None: self.head = probe.next probe = probe.next probe.previous = None # ENTRE Nodos de la DobleLinkedList elif probe.previous != None and probe.next != None: probe.previous.next = probe.next probe.next.previous = probe.previous # ULTIMO Nodo de la DobleLinkedList else: self.tail = probe.previous probe.previous.next = None self.size -= 1 return True probe = probe.next def __str__(self): probe = self.head result = "* " while probe: result += str(probe.data) + " <--> " probe = probe.next result += "*" return result
def main(): head = TwoWayNode(1) head.append(1) head.append(2) head.append(3) head.append(4) head.append(5) print(head.str()) head.delete(1) print(head.str()) head.delete(3) print(head.str()) head.delete(5) print(head.str())
if name == 'main': main()
muchas gracias :')
Aquí mi solución al reto!
class DoubleCircularLinkedList(): def __init__(self): self.head = None self.tail = None self.size = 0 def append(self, data): node = TwoWayNode(data) if self.head == None: self.head = node self.head.next = self.head self.tail = self.head self.size += 1 else: probe = self.head while probe.next != self.head: probe = probe.next probe.next = node node.next = self.head node.previous = probe self.tail = node self.size += 1 def inverse_iter(self): probe = self.tail while probe != None: val = probe.data probe = probe.previous yield val def iter(self): probe = self.head size = self.size while size > 0: val = probe.data probe = probe.next size -= 1 yield val def clear(self): self.head = None self.tail = None self.size = 0 def delete(self, data): probe = self.tail while probe.previous != None and probe.data != data: probe = probe.previous if probe.data == data and self.head == self.tail: self.clear() elif probe.data == data: if probe == self.tail: self.tail = probe.previous probe.previous.next = probe.next if probe.next != self.head: probe.next.previous = probe.previous self.size -= 1
Les comparto mi reto de la clase .
Salida:
5 4 3 2 1 target item 3 has been found target item 10 is not in the linked list the final item "F" aim: I 8 replaced the old value in the node number 4 we remove: F Now the final item "5" aim: I we remove: 3 5 8 2 9 1 I
from node import Node class TwoWayNode(Node): def __init__(self, data, previous = None, next=None): Node.__init__(self, data, next) self.previous = previous class CircleDoublelinkedlist: def __init__(self): self.head = TwoWayNode(1) self.tail = self.head def ranger(self): for data in range(2, 6): self.tail.next = TwoWayNode(data, self.tail) self.tail = self.tail.next def travel(self): probe = self.tail while probe != None: print(probe.data) probe = probe.previous def add_elements(self, new_final, new_start): self.tail = TwoWayNode(new_final, self.tail) self.tail.previous.next = self.tail new_node = TwoWayNode(new_start) if self.tail is None: self.tail = new_node else: probe = self.tail while probe.previous != None: probe = probe.previous probe.previous = new_node new_node.next = probe def circular(self): probe = self.tail while probe.previous != None: probe = probe.previous self.tail.next = probe print(f'the final item "{self.tail.data}" aim: {self.tail.next.data}') def search(self, data): probe = self.tail target_item = data while probe != None and target_item != probe.data: probe = probe.previous 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 replace(self, data, new_item): probe = self.tail target_item = data while probe != None and target_item != probe.data: probe = probe.previous 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 romove_element_of_tail(self): removed_item = self.tail.data try: if self.tail.next.previous is None: removed_item = self.tail.data self.tail = self.tail.previous self.tail.next = self.tail.next.next print(f'we remove: {removed_item}') print(f'Now the final item "{self.tail.data}" aim: {self.tail.next.data}') except AttributeError: probe = self.tail while probe.next != None: probe = probe.next removed_item = probe.data self.tail = self.tail.previous self.tail.next = None print(f'we remove: {removed_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.tail is None or index < 0: self.tail = TwoWayNode('py', self.tail) else: probe = self.tail.next while index > 1 and probe.next != None: probe = probe.next index -= 1 if probe.next.previous is None: probe.next = TwoWayNode(new_item, probe, probe.next) self.tail = probe.next print(f'the final item "{self.tail.data}" aim: {self.tail.next.data}') else: probe.next = TwoWayNode(new_item, probe, probe.next) probe.next.next.previous = probe.next def remove_element_in_index(self, index): if index <= 0 or self.tail.next is None: remove_item = self.tail.data self.tail = self.tail.next print(remove_item) else: probe = self.tail while index > 1 and probe.next.next != None: probe = probe.next index -= 1 if probe.next.next.previous is None: remove_item = self.tail.data self.tail = self.tail.previous self.tail.next = self.tail.next.next print(f'we remove: {remove_item}') print(f'Now the final item "{self.tail.data}" aim: {self.tail.next.data}') else: remove_item = probe.next.data probe.next = probe.next.next probe.next.previous = probe print(f'we remove: {remove_item}') if __name__ == '__main__': words = CircleDoublelinkedlist() words.ranger() words.travel() words.add_elements('F', 'I') words.search(3) words.search(10) words.circular() words.replace(4, 8) words.romove_element_of_tail() words.add_item(9, 2) words.remove_element_in_index(5) words.travel()
Prometo hacer mejoras. Por ahora hice esto:
class Node(object): def __init__(self, data, next = None): self.data = data self.next = next class TwoWayNode(Node): def __init__(self, data, previous = None, next = None): Node.__init__(self, data, next) self.previous = previous def add_after(self, node): node = TwoWayNode(node) if self.next == None: self.next = node node.previous = self else: probe = self while probe.next != None: probe = probe.next probe.next = node node.previous = probe def find_node(self, data): if self.data == data: return (f'Se ha encontrado {self.data}') elif self.next == None: return (f'No existe ese dato') else: return self.next.find_node(data)
Solución al reto:
from node import Node, TwoWayNode class TwoWayListSingle: POSITION = 1 DATA = 2 def __init__(self, node = None, size = 0): self.__tail = node self.__size = 0 def load_node(self, init, end): node = None for count in range(init, end): if node is None: node = TwoWayNode(count) node.previous = node node.next = node first_node = node else: previous_node = node node = TwoWayNode(count, previous_node, node.next) previous_node.next = node self.__size += 1 node.next = first_node first_node.previous = node self.__tail = first_node def __str__(self): node = self.__tail 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.__tail 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.__tail is None: self.__tail = node node.next = node node.previous = node self.__size += 1 elif position <= 0: #Se registra al principio first_node = self.__tail node.next = first_node first_node.previous = node self.__tail = node #Adquirimos el último nodo last_node = self.get_last_node() last_node.next = self.__tail self.__tail.previous = last_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) print(f'find_previous_node_position: {find_previous_node_position.data}') 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 find_previous_node_position.previous.next = node node.previous = find_previous_node_position.previous node.next = find_previous_node_position find_previous_node_position.previous = 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.__tail if self.__size < 2: return self.__tail first_node = self.__tail position = 1 while node.next != first_node: node = node.next position += 1 return node def __find_by_position(self, position): node_ret = self.__tail item = 1 while node_ret != None and item != position: node_ret = node_ret.previous item += 1 return node_ret def __find_by_data(self, data): node_ret = self.__tail 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.__tail 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.__tail = self.__tail.next last_node = self.__find_last_node() last_node.next = self.__tail 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 node.previous = node.previous self.__size -= 1 return True except AssertionError as ae: print(ae) return False
Como implementarlo:
from mi_twowaynodelistlinked_simple import TwoWayListSingle from node import Node def run(): linked_list = TwoWayListSingle() 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(TwoWayListSingle.POSITION, 5, 'Actualizar') print(linked_list) linked_list.update(TwoWayListSingle.DATA, 'Actualizar', 'Nuevamente actualziado') print(linked_list) if __name__ == '__main__': run()
Por qué al llamar a la clase base en el ejemplo e inicializarla no usa super()??
según entendí es como para que quede mas claro que node es la clase padre, pero en términos de no hacer hard coding hay que usar el super(). por si algún día cambian las jerarquías o cosas asi en las clases
En lo personal, me gustaría un poco de más explicación e ir viendo que es lo que sucede internamente, porque la verdad con las narracciones del código en terminal, no queda nada claro.
Les recomiendo usar el debugger de vscode, para poder ir viendo las variables con los apuntadores. Es mucho mejor para estos casos que un jupyter notebook.
:D
Excelente.
..
..
Good day.
Increible reto.
..
..
Increible.
class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class DoubleLinkedList: def __init__(self): self.head = None def size(self): if self.head is None: return 0 current = self.head count = 0 while current: current = current.next count += 1 return count def index_of(self, data): index = 0 current = self.head while current: if current.data == data: return index current = current.next index += 1 return "Does not exist in the list" def insert_start(self, data): new_node = Node(data) if self.head is None: self.head = new_node # print(self.head.data) return else: current = self.head current.prev = new_node new_node.next = current self.head = new_node print(f"add VALUE {data} at the beginning DLL")
def insert_ending(self, data): new_node = Node(data) if self.head is None: self.head = new_node return current = self.head while current.next is not None: current = current.next current.next = new_node new_node.prev = current print(f"The value {data} is added in the last DLL") def insert_position(self, pos, data): new_node = Node(data) if pos == 1: self.insert_start(data) else: current = self.head for i in range(1, pos - 1): current = current.next if current is None: raise IndexError("Position out of range") new_node.prev = current new_node.next = current.next if current.next is not None: current.next.prev = new_node current.next = new_node print(f"add node {data} on the position {pos}") def delete(self, data): current = self.head while current: if current.data == data: if current.prev: current.prev.next = current.next if current.next: current.next.prev = current.prev if current == self.head: self.head = current.next print(f"Node with value {data} was deleted") return current = current.next print(f"Node with value {data} not found") def delete_first(self): if self.head is None: print("The list is empty, no node to delete") return if self.head.next is None: self.head = None else: current = self.head self.head = self.head.next self.head.prev = None print(f"First None deleted value: {current.data}") def delete_last(self): if self.head is None: print("The list is empty, no node to delete") return if self.head.next is None: self.head = None else: current = self.head while current.next is not None: current = current.next current.prev.next = None print(f"Last node delete value: {current.data}") def insert_at_index(self, index, data): if index < 0 or index > self.size(): print("Index out of range") return False if index == 0: self.insert_start(data) return True new_node = Node(data) current = self.head for _ in range(index - 1): current = current.next new_node.prev = current new_node.next = current.next current.next = new_node print(f"Insert node {data} at the index{[index]}") def replace(self, data, new_data): current = self.head while current: if current.data == data: current.data = new_data print(f"Node with value {data} replaced with {new_data}") return current = current.next print(f"Node with value {data} not found") def iter(self): current = self.head while current: yield current.data current = current.next def search(self, data): for item in self.iter(): if item == data: print(f"The data {data} is in the list") return print(f"The data {data} is not in the list")
def __str__(self): if self.head is None: return f"Empty Double linked list" elements = [] current = self.head while current is not None: if isinstance(current.data, (int, float)): elements.append(str(current.data)) else: elements.append(f"'{str(current.data)}'") current = current.next if current == self.head: self.head return " --> ".join(elements) # return "[" + ", ".join(elements) + "]" def main(): D = DoubleLinkedList() # print(D) node1 = Node(10) D.head = node1 node2 = Node(20) node2.prev = node1 node1.next = node2 node3 = Node(30) node3.prev = node2 node2.next = node3 node4 = Node(40) node4.prev = node3 node3.next = node4 D.insert_start(3) D.insert_ending(1) D.insert_position(2, 999) D.insert_at_index(2, 1111) print("*"*50) print(f"{D}") print(f"size: {D.size()}") print("*"*50) D.replace(1111, 5) D.insert_at_index(5, 25) D.insert_ending('abc') print("*"*50) print(f"{D}") print(f"size: {D.size()}") print(f"INDEX OF 40: {D.index_of(40)}") print("*"*50) D.search(10) D.delete(20) D.delete_first() D.delete_first() D.delete_last() D.delete_last() D.insert_at_index(6, 5555) D.delete_first() print("*"*50) print(f"{D}") print(f"size: {D.size()}") print(f"INDEX OF 999: {D.index_of(999)}") print("*"*50) for idx, lst in enumerate(D.iter()): print(f"{idx + 0}. {lst}") # print(f"- {lst}")
if __name__ == '__main__': main()
hola.
