Contenido del curso
Operaciones en Listas Enlazadas: Búsqueda, Inserción y Eliminación
¿Cómo se manejan las estructuras de datos con nodos?
Entender las operaciones en estructuras de datos como las listas enlazadas puede parecer complicado al principio. Para abordar este desafío, necesitamos un profundo conocimiento de cómo operar, qué herramientas usar y cómo implementarlas adecuadamente. Este artículo explorará el funcionamiento conceptual de las operaciones comunes en listas enlazadas simples, resaltando la importancia de comprender cómo se manipulan los nodos.
¿Qué papel juegan las variables auxiliares?
Las variables auxiliares, como la utilizada en este caso, denominada prop, son fundamentales. Estas variables nos permiten conocer qué hay dentro de cada nodo mientras recorremos la lista. Durante este proceso, los nodos se recorren mediante un bucle while hasta que se cumplen ciertas condiciones que permiten detenerse para realizar modificaciones necesarias en los datos.
¿Cómo se realizan las operaciones básicas en listas enlazadas?
Hay varias operaciones básicas que se pueden realizar en una lista enlazada:
Búsqueda: Nuestra variable prop visita cada nodo en búsqueda de un valor específico. Si buscamos el elemento con valor dos, por ejemplo, el procedimiento se detiene cuando se encuentra el valor, anunciándonos su localización.
Reemplazo: Este método permite dar un argumento, buscarlo y reemplazarlo. Al buscar el nodo con valor tres y reemplazarlo por una letra, como ‘f’, la lista se altera introduciendo un nuevo elemento.
Inserción al inicio: Para insertar un nuevo nodo al principio, ese nodo se convierte en el nuevo head, mientras que el anterior head se pasa al segundo lugar.
Inserción al final: Para añadir un nodo al final, identificamos el tail, que apunta a null, y actualizamos la lista para incluir nuestro nueva entrada al final.
¿Cómo se eliminan nodos en listas enlazadas?
Eliminar nodos requiere cuidado, especialmente cuando hay valores duplicados. Es crucial localizar y señalar el nodo que queremos eliminar considerando los atributos next, head y tail para evitar confusiones. Es importante documentar bien el código para tener claridad sobre la cantidad de nodos y los datos que almacena cada uno, evitando así el caos en la gestión de nodos.
¿Qué complejidades adicionales presentan las listas enlazadas?
Aumentar la complejidad de las operaciones es posible trabajando no solo con head o tail, sino también con nodos intermedios. Al insertar un nodo en una posición específica, por ejemplo, es importante entender cómo reposicionar los punteros de nodo.
Las manipulaciones intermedias, como eliminar un nodo en una posición intermedia, requieren recorridos cuidadosos y ajustes de las referencias de nodo anteriores y siguientes.
Ejemplo de inserción intermedia
Si insertamos un nodo en una posición intermedia, se debe calcular exactamente dónde se va a ubicar. A continuación, el nuevo nodo también debe apuntar a su nodo siguiente correcto, asegurando que la estructura de la lista se mantenga coherente.
# Supongamos que estamos manejando una lista enlazada en Python # Insertar un nodo en una posición intermedia podría parecerse a esto: class Nodo: def __init__(self, data): self.data = data self.next = None def insertar_en_medio(head, dato_nuevo, valor_anterior): nuevo_nodo = Nodo(dato_nuevo) actual = head while actual is not None and actual.data != valor_anterior: actual = actual.next if actual is not None: nuevo_nodo.next = actual.next actual.next = nuevo_nodo
Este ejemplo demuestra cómo un nuevo nodo se integra en una posición intermedia fijando conexiones entre nodos vecinos.
¿Qué sucede con estructuras más complejas como las listas circulares?
A lo largo de este análisis hemos descrito listas enlazadas de vía única, pero existen variaciones como las listas circulares que se comportan de manera diferente, ya que el último nodo apunta de nuevo al primer nodo. Este es apenas el comienzo de entender la complejidad que ofrecen las diferentes estructuras de datos en programación. Invitamos a continuar explorando y aprendiendo sobre estas fascinantes arquitecturas para dominar el mundo de la informática.
Julian Camilo Hermida Delgado
Estudiante
Mauricio Gonzalez Falcon
Estudiante
Alexis Dorado Muñoz
Estudiante
Junior Peves
Estudiante
Jose Carlos Borrayo
EstudianteMauricio Gonzalez Falcon
Estudiante
Jose Noriega
EstudianteJose Noriega
EstudianteAlexis Dorado Muñoz
Estudiante
Jhon Freddy Tavera Blandon
Estudiante
Nicolas Alpargatero
Estudiante
Eduardo Kiriakos Piazza
EstudianteAlexis Dorado Muñoz
Estudiante
Sebastian Alejandro Gómez Ardila
Estudiante
Leslie Paz Ore
EstudianteLeslie Paz Ore
EstudianteMauricio Gonzalez Falcon
Estudiante
Andres Montes
Estudiante
Mauricio Combariza
EstudianteNicolas Alpargatero
Estudiante
Miguel Angel Lopez Monroy
Estudiante
Joel Angel David Barrantes Palacios
Estudiante
Anabel Chavez Berumen
Estudiante
Jonathan Osorio
Estudiante
marco antonio
Estudiante
Pedro Alvarado Garcia
Estudiante
Christian Molina Vázquez
EstudianteMi aporte con todos los métodos:
from nodos import Node class SinglyLinkedList: def __init__(self): self.head = None self.size = 0 def add_to_start(self, data): """Inserta un nodo al inicio.""" self.head = Node(data, self.head) print(f"Nodo {self.head.data} añadido a la cabezera.") self.size += 1 def append(self, data): """Añade un nodo nuevo al final.""" node = Node(data) if self.head == None: self.head = node else: probe = self.head while probe.next: probe = probe.next probe.next = node print(f"Nodo {node.data} añadido a la cola.") self.size += 1 def insert(self, data, index): """Inserta un nodo segun indice.""" if index > self.count_nodes(): print("El indice supera la cantidad de nodos") else: if self.head is None or index <= 0: self.head = Node(data, self.head) else: probe = self.head index -= 1 while index > 1 and probe.next != None: probe = probe.next index -= 1 probe.next = Node(data, probe.next) print(f"Nodo {data} añadido.") self.size += 1 def replace(self, data, new_data): """Reemplaza un nodo por uno nuevo.""" probe = self.head while probe != None and data != probe.data: probe = probe.next if probe != None: probe.data = new_data print(f"El nodo {data} ha sido reemplazado por {new_data}") else: print(f"The target item {data} is not in the linked list") def delete(self, index): """Elimina nodo en posición dada.""" if index > self.count_nodes(): print("El indice supera la cantidad de nodos") else: if self.head is None: print("No hay nodos que eliminar.") elif self.head.next is None: print(f"Nodo: {self.head.data} eliminado.") self.head = None self.size -= 1 else: probe = self.head index -= 1 while index > 1 and probe.next.next != None: probe = probe.next index -= 1 removed_item = probe.next.data probe.next = probe.next.next print(f"Nodo:{removed_item} eliminado.") self.size -= 1 def pop(self): """Elimina ultimo nodo.""" data = self.head.data if self.head.next is None: self.head = None else: probe = self.head while probe.next.next != None: probe = probe.next data = probe.next.data probe.next = None self.size -= 1 print(f"Ultimo nodo {data} eliminado.") def search(self, data): """Busca nodo especificado.""" probe = self.head while probe != None and data != probe.data: probe = probe.next if probe != None: print(f"El nodo {data} ha sido encontrado.") return probe else: print(f"El nodo {data} no se encuentra en el grafo.") def count_nodes(self): """Imprime cantidad de nodos.""" return self.size def print(self): """Imprime cada nodo.""" probe = self.head while probe != None: print(probe.data) probe = probe.next def clear(self): self.head = None self.size = 0
Solo falto el método iter, pero muy bueno, gracias!
Muchas gracias por tu aporte.
Mi aporte:
¿Qué editor usaste?
Hola Jose Carlos, es VSC con una extensión para hacer imagenes del código
LinkedList con todos los métodos de List.
Implementé todos los métodos de list a mi clase de linked list, de forma que pueden usar los mismos métodos y sintaxis que usan para manipular una lista normal.
Incluyendo el
Código
SinglyLinkedList
from typing import Any from typing import Optional from typing import Iterator from typing import Union from typing import Iterable from node import Node class SinglyLinkedList: """Singly Linked List""" _head: Optional[Node] _tail: Optional[Node] _size: int def __init__(self, *items) -> None: """Initialize an empty list Args: *items: Items to be added to the list. """ self._head = None self._tail = None self._size = 0 if len(items) == 1 and isinstance(items[0], (Iterable, SinglyLinkedList)): items = items[0] for item in items: self.append(item) @property def size(self): """Returns the size of the linked list. Time complexity: O(1) """ return self._size def clear(self): """Clears the list. Removes all the items inside the list. """ self._head = None self._size = 0 def copy(self): """Returns a copy of the list. Time Complexity: O(1) """ new_list = SinglyLinkedList() if self._head is not None: # Caution: This is a shallow copy new_list._head = self._head new_list._size = self._size return new_list def depthcopy(self) -> 'SinglyLinkedList': """Returns a copy of the list and its nodes. Time complexity: O(n) Returns: SinglyLinkedList: Copy of the list. """ new_list = SinglyLinkedList() for item in self: new_list.append(item.value) return new_list def append(self, value: Any): """Appends a new value at the end of the list. Time complexity: O(1) """ node = Node(value) if self._head is None: self._head = node self._tail = self._head else: self._tail.next = Node(value) self._tail = self._tail.next self._size += 1 def extend(self, other: Iterable): """Extends the current list with the provided list. Time complexity: O(n) where n is the length of the list to extend. Args: other: List to be extended. """ for item in other: if isinstance(other, Node): self.append(item.value) else: self.append(item) def pop(self, index: int = -1) -> Any: """Removes an item from the list. Raises IndexError if the list is empty or index is out of range. Time complexity: O(n) where n is the length of the nodes. Args: index: Index of the item to be removed. Returns: Any: Item removed. """ if index < 0: index = self._size + index if self._head is None or index > self._size - 1: raise IndexError('Index out of range.') prev_pointer = self._head value: Node for idx, value in enumerate(self): if idx == index: if value == self._head: self._head = None self._tail = None else: prev_pointer.next = value.next self._tail = prev_pointer self._size -= 1 return value prev_pointer = value def index(self, target: object): """Return first index of value. Raises ValueError if the value is not present. Time complexity: O(n) where n is the length of nodes. Args: target: Value to look up. Returns: int: Index of the value. """ item: Node for index, item in enumerate(self): if item.value == target: return index raise ValueError(f'{target} is not in list') def count(self, target: object) -> int: """Counts the number of occurrences of the provided value. Time complexity: O(n) where n is the length of the nodes. Args: target: Value to be counted. Returns: int: Number of occurrences. """ count = 0 item: Node for item in self: if item.value == target: count += 1 return count def insert(self, index: int, value: object): """Insert before index. Time complexity: O(n) Args: index: Index to insert before. value: Value to insert. """ if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('Index out of range.') if index == 0: self._head = Node(value, self._head) else: prev_pointer = self._head item: Node for idx, item in enumerate(self): if idx == index: new_node = Node(value, item) prev_pointer.next = new_node break; prev_pointer = item self._size += 1 def remove(self, value): """Removes the first occurrence of value. Raises ValueError if the value is not present. Args: value: Value to be removed. """ common_error = ValueError('Value not found') if self._head is None: raise common_error if self._head.value == value: self._head = self._head.next else: prev_node: Optional[Node] = None item: Node for item in self: if item.value == value: prev_node.next = item.next if item == self._tail: self._tail = prev_node found = True break prev_node = item if not found: raise common_error self._size -= 1 def _sort_nodes(self, head: Node, reversed: bool = False): """Sorts the nodes of a linked list. Time complexity: O(n log n) Args: head: head node of the linked list. reversed: True to sort in descending order, False to sort in ascending order. Returns: tuple: (head, tail) of the sorted linked list. """ # If there are only 1 or 0 nodes heads that the list is already sorted. if head is None or head.next is None: return head temp = head slow = head fast = head # We need to divide the list in half. # The fast node will be the last node when the loop ends, # and the slow node will be at the middle of the list beacause # the fast node is traversing the list two steps at the once and the slow 1 at once. # temp will be the end of the first half. # slow will be the head of the second half. # fast will be the end of the second half. # Example: # head temp slow fast # [1, 2, 3, 4 , 5 , 6, 7, 8, 9] while fast is not None and fast.next is not None: temp = slow slow = slow.next fast = fast.next.next # Set the end of the first half temp.next = None left_half = self._sort_nodes(head, reversed=reversed) if isinstance(left_half, tuple): left_half = left_half[0] right_half = self._sort_nodes(slow, reversed=reversed) if isinstance(right_half, tuple): right_half = right_half[0] # Merge sorted_temp = Node(Node) current_node = sorted_temp while left_half is not None and right_half is not None: if (not reversed and left_half.value < right_half.value) or (reversed and left_half.value > right_half.value): current_node.next = left_half left_half = left_half.next else: current_node.next = right_half right_half = right_half.next current_node = current_node.next if left_half is not None: current_node.next = left_half left_half = left_half.next if right_half is not None: current_node.next = right_half right_half = right_half.next tail = current_node while tail.next is not None: tail = tail.next return sorted_temp.next, tail def sort(self, reversed: bool = False): """Sort the list in ascending order and return None. The reverse flag can be set to sort in descending order. Time complexity: O(n log n) Args: reversed: True to sort in descending order. Returns: None """ self._head, self._tail = self._sort_nodes(self._head, reversed) return None def search(self, target: object) -> bool: """Check if the provided value is in the list. Time complexity: O(n) where n is the length of the nodes. Args: target: Value to be searched inside the list. Returns: bool: True if found. False otherwise. """ return target in self def iter(self): """Allows to iterate over the list using a generator. Time complexity: O(n) Returns: Iterator[Node]: Iterator over the list. """ if self._head is not None: pointer = self._head while pointer is not None: val = pointer pointer = pointer.next yield val return None def reverse(self): """Reverses the list. Time complexity: O(n) Returns: None """ if self._head is not None: current_node: None = self._head remaining_values: Optional[Node] = self._head.next # Set the head next value to None beacuse now it will be the tail current_node.next = None while remaining_values is not None: temp_ref = current_node current_node: Node = remaining_values remaining_values = current_node.next current_node.next = temp_ref self._tail = self._head self._head = current_node # ========================== # Dunders # ========================== def __delitem__(self, index: Union[int, slice]): """Deletes an item from the list. Time complexity: O(n) Args: index: Index of the item to be removed. Returns: None """ if isinstance(index, slice): list_items = list(self) del list_items[index] self.clear() for item in list_items: self.append(item) else: if index > self._size - 1: raise IndexError('Index out of range.') if index == 0: self._head = self._head.next else: prev_pointer: Optional[Node] = None item: Node for idx, item in enumerate(self): if idx == index: prev_pointer.next = item.next if item == self._tail: self._tail = prev_pointer break prev_pointer = item self._size -= 1 return None def __setitem__(self, index: Union[int, slice], value: Union[object, Iterable]): """Set self[key] to value. Time complexity: O(n) Args: index: Index to be set. value: Value to assign. """ if isinstance(index, slice): if not isinstance(value, Iterable): raise TypeError('can only assign an iterable') if len(value) > 0: list_items = list(self) list_items[index] = value self.clear() for item in list_items: self.append(item) else: if index < 0: index = self._size + index if index > self._size - 1: raise IndexError('list assignment index out of range') if index == 0: self._head.value = value else: item: Node for idx, item in enumerate(self): if idx == index: item.value = value break def __add__(self, values: Iterable) -> 'SinglyLinkedList': """Returns a new list with the nodes of the current list a the values or nodes of the other list. Time complexity: O(n) where n is the length of values to add. Returns: SinglyLinkedList: Merged linked list. """ new_list = self.depthcopy() for item in values: new_list.append(item) return new_list def __iadd__(self, values: Iterable): """Appends values to the list when using the += operator. Time complexity: O(n) where n is the length of items to append. Returns: self """ for item in values: self.append(item) return self def __len__(self): """Returns the size of the linked list when using the built-in function len.""" return self._size def __mul__(self, times: int): """ Returns a new list with the items duplicated by provided factor. Args: times: Number of times to duplicate the list. Returns: SinglyLinkedList: Duplicated list. """ if times <= 0: return SinglyLinkedList() new_list = self.depthcopy() for _ in range(times - 1): new_list += self.depthcopy() return new_list def __rmul__(self, times: int): """ Returns a new list with the items duplicated by provided factor. Args: times: Number of times to duplicate the list. Returns: SinglyLinkedList: Duplicated list. """ return self.__mul__(times) def __imul__(self, times: int): """Duplicates the current list items by the provided factor and appends them to the end. Time complexity: O(a * b) where a is the number of duplicates to add and b is the length of the list. Args: times: Number of times to duplicate the list. Returns: self """ if times <= 0: self.clear() else: base = self.depthcopy() for _ in range(times - 1): self.extend(base.depthcopy()) return self def __iter__(self) -> Iterator[Node]: """Allows to iterate over the list using a generator. Time complexity: O(n) Returns: Iterator[Node]: Iterator over the list. """ return self.iter() def __contains__(self, target: object) -> bool: """Check if a value is in the list when using the 'in' operator. Time complexity: O(n) where n is the length of the nodes. """ output = False pointer = self._head while pointer is not None and pointer.value != target and pointer.next is not None: pointer = pointer.next if pointer is not None and pointer.value == target: return target return output def __getitem__(self, index: Union[int, slice]): """Get item with the index or slice from the linked list. Time Complexity: O(n) where n is the length of the nodes. Returns: Any: Item with the index or slice. """ if isinstance(index, slice): items = list(self)[index] new_list = SinglyLinkedList(items) return new_list if index > self.size - 1: raise IndexError('Index out of range') if index < 0: index = self._size + index for idx, value in enumerate(self): if index == idx: return value return None def __lt__(self, other: 'SinglyLinkedList') -> bool: """Check if the list is less than the other list. Time Complexity: O(n) where n is the length of the nodes of the list with less nodes. Args: other (SinglyLinkedList): Other list to be compared. Returns: bool: True if the list is equals to the other list. False otherwise. """ if len(self) >= len(other): return False for self_item, other_item in zip(self, other): if self_item.value != Node._parse_other_value(other_item): return False return True def __le__(self, other: 'SinglyLinkedList') -> bool: """Check if the list is less than or equals to the other list. Time Complexity: O(n) where n is the length of the nodes of the list with less nodes. Args: other (SinglyLinkedList): Other list to be compared. Returns: bool: True if the list is equals to the other list. False otherwise. """ if len(self) > len(other): return False for self_item, other_item in zip(self, other): if self_item.value != Node._parse_other_value(other_item): return False return True def __eq__(self, other: 'SinglyLinkedList') -> bool: """Check if the list is equal to the other list. Time Complexity: O(n) where n is the length of the nodes of the list with less nodes. Args: other (SinglyLinkedList): Other list to be compared. Returns: bool: True if the list is equals to the other list. False otherwise. """ if len(self) != len(other): return False for self_item, other_item in zip(self, other): if self_item.value != Node._parse_other_value(other_item): return False return True def __ge__(self, other: 'SinglyLinkedList') -> bool: """ Check if the list is greater or equal than the other list. Time Complexity: O(n) where n is the length of the nodes of the list with less nodes. Args: other (SinglyLinkedList): Other list to be compared. Returns: bool: True if the list is greater or equal than the other list. False otherwise. """ if len(self) < len(other): return False for self_item, other_item in zip(self, other): if self_item.value != Node._parse_other_value(other_item): return False return True def __gt__(self, other: 'SinglyLinkedList') -> bool: """ Check if the list is greater than the other list. Time Complexity: O(n) where n is the length of the nodes of the list with less nodes. Args: other (SinglyLinkedList): Other list to be compared. Returns: bool: True if the list is greater than the other list. False otherwise. """ if len(self) <= len(other): return False for self_item, other_item in zip(self, other): if self_item.value != Node._parse_other_value(other_item): return False return True
Node
class Node: """ Node class for a linked list. """ def __init__(self, value, next=None) -> None: """ Initialize a node with a value and a next node. Args: value: The value of the node. next: The next node. """ self.value = value self.next = next def copy(self) -> 'Node': """ Return a copy of the node. Returns: A copy of the node. """ return Node(self.value, self.next) @staticmethod def _parse_other_value(other): if isinstance(other, Node): return other.value return other def __lt__(self, other: 'Node') -> bool: """Check if the current value is less than the other value. Args: other: Node to be compared. Returns: bool: True if the current value is less than the other one. False otherwise. """ return self.value < self._parse_other_value(other) def __le__(self, other: 'Node') -> bool: """Check if the current value is less than or equals to the other value. Args: other: Node to be compared. Returns: bool: True if the current value is less than or equals to the other one. False otherwise. """ return self.value <= self._parse_other_value(other) def __eq__(self, other: 'Node') -> bool: """Check if the current value is equals to the other value. Args: other: Node to be compared. Returns: bool: True if the current value is equals to the other one. False otherwise. """ return self.value == self._parse_other_value(other) def __ge__(self, other: 'Node') -> bool: """Check if the current value is greater than or equals to the other value. Args: other: Node to be compared. Returns: bool: True if the current value is greater than or equals to the other one. False otherwise. """ return self.value >= self._parse_other_value(other) def __ge__(self, other: 'Node') -> bool: """Check if the current value is greater than the other value. Args: other: Node to be compared. Returns: bool: True if the current value is greater than the other one. False otherwise. """ return self.value > self._parse_other_value(other) def __str__(self) -> str: return str(self.value)
Cuando llegué al sort todo se puso raro 😅, pero después de unas horas llegué a la solución.
Realicé pruebas unitarias pero eran bastantes como para incluirlas.
Si tienen alguna sugerencia estaría cool que me la compartieran!
Muchas gracias por tu aporte.
Esta implementación de la lista enlazada (LinkedList) incluye los siguientes métodos:
len():
getitem(index):
setitem(index, value):
iter():
contains(value):
Verifica si un valor está presente en la lista.
append(data):
insert(index, data):
remove(data):
index(data):
count(data):
clear():
copy():
extend(iterable):
pop(index=None):
Devuelve una representación en cadena de la lista.
que buena nota, gracias
Aquí mi solución para crear uno de los métodos (Reemplazar):
def replace(self, target_item, new_data): new_node = Node(new_data) probe = self.head is_the_first_iteration = True previuos = self.head while probe.next != None and probe.data != target_item: probe = probe.next if not is_the_first_iteration: previuos = previuos.next is_the_first_iteration = False if probe.data == target_item and is_the_first_iteration: new_node.next = probe.next self.head = new_node elif probe.data == target_item: new_node.next = probe.next previuos.next = new_node if new_node.next == None: self.tail = new_node else: print("The target item is not in the list.")
Si tienes problemas entendiendo cómo funciona puedes checar Aquí en mi GitHub donde está el código comentado línea a línea y todos los métodos del reto creados. Saludos!
Muchas gracias por tu aporte.
Les dejo este link que da más detalle sobre los ++LinkedList++.
Mi aporte con lo aprendido y practicado ############ Interfaz Linked List ######
from linkedlist import LinkedList def wrong_option(): print('Option Not Exist') def _welcom(): print('*' * 50) print('############ L I N K E D L I S T ############') print('*' * 50) print('What would you like to do?:') print('[I]nsert') print('[S]earch Node') print('[C]lear LinkedList') print('[G]et length of Linkedlist') if __name__=="__main__": _welcom() command = input() command = command.upper() ll = LinkedList() if command == 'I': print('[1]Insert Node') print('[2]Insert List') command = int(input()) if command==1: print('[1]Insert at begining') print('[2]Insert at end') print('[3]Insert any position') command = int(input()) if command==1: data=input('Introduce data: ') ll.insert_at_begining(data) elif command==2: data=input('Introduce data: ') ll.insert_at_end(data) elif command==3: data=input('Introduce data: ') index=int(input('Introduce Index'))-1 ll.insert_at(index, data) else: wrong_option() elif command ==2: n=int(input('Enter number of elements : ')) list1=[input() for i in range(0,n)] ll.insert_value_from_list(list1) else: wrong_option() elif command=='R': print('Remove by: ') print('[I]ndex') print('[D]ata') command = input().upper() if command=='I': index=int(input('Introduce Index: ')) ll.remove_index(index) elif command=='D': data=input('Introduce Data: ') ll.remove_data(data) else: wrong_option() elif command=='S': print('Search by: ') print('[I]ndex') print('[D]ata') command = input().upper() if command=='I': index=int(input('Introduce Index: ')) ll.search_index(index) elif command=='D': data=input('Introduce Data: ') ll.search_data(data) else: wrong_option() elif command=='G': ll.get_length() elif command=='C': ll.clear() else: wrong_option() ll.print()
##### Linked List funcionts #####
from node import Node class LinkedList: def __init__(self): self.head=None #Function that insert a Node at the beginig of a LinkedList def insert_at_begining(self, data): node=Node(data,self.head) self.head=node #Function that insert a Node at the end of a LinkedList def insert_at_end(self, data): if self.head is None: self.head=Node(data, None) return itr =self.head while itr.next: itr=itr.next itr.next=Node(data, None) #Function that insert a Node in LinkedList def insert_at(self, index, data): if index<0 or index>self.get_length(): raise Exception("Invalid Index") else: itr=self.head if index==0: self.insert_at_begining(data) elif index==self.get_length(): self.insert_at_end(data) else: while index>1 and itr.next!=None: index-=1 itr=itr.next itr.next=Node(data, itr.next) #Function that insert a List in a LinkedList def insert_value_from_list(self, data_list): self.head=None for data in data_list: self.insert_at_end(data) #Function that returns the size of LinkedList def get_length(self): count=0 itr=self.head while itr: count+=1 itr=itr.next return count #Function that remove a Node of LinkedList by it Index def remove_index(self, index): if index<0 or index>=self.get_length(): return count=0 itr=self.head while itr: if count==index-1: itr.next=itr.next.next break itr=itr.next count+=1 #Function that remove a Node of LinkedList by Data def remove_data(self, data): itr=self.head previous=self.head while itr.next: if itr.data==data: if itr==self.head: self.head=itr.next else: previous.next=itr.next return itr.data previous=itr itr=itr.next def _iter(self): itr=self.head while itr: val=itr.data itr=itr.next yield val #Function that search a Node by Data def search_data(self, data): for node in self._iter(): if data==node: print(f'Data {data} found') #Function that search a Node by Index def search_index(self ,index): #pendiente por indice itr=self.head count=1 while itr!=None and index<=self.get_length() : if count==index: data=itr.data print(f'In the index {index} you will found the data {data}') break else: count+=1 itr=itr.next #Replace a node with a new one def replace(self, data, new_data): itr=self.head while itr != None and itr.data!=data: itr=itr.next if itr!=None: itr.data = new_data print(f'The node {data} has been replaced by {new_data}') else: print(f'The target item {data} is not in the Linked List') #Clear the Linked List def clear(self): self.head=None self.size=0 def print(self): if self.head is None: print("Linked list is empty") return itr=self.head llstr='' while itr: llstr+=str(itr.data) + '-->' itr =itr.next print(llstr)
Por si a caso,
itr es la varaible iterable
Añadiendo el método iter
def iter(self): current = self.tail while current: value = current.data current = current.next yield value
reto cumplido agrege a mi clase el metodo eliminar, buscar, actualizar, colocar al inicio, insertar en cualquier lugar y un ultimo crear una lista donde muestra en formato de lista como estan conectados los diferenters nodos
Pesimo curso, el anterior era muy bueno.
Por si alguien le sirve, dejo en detalle como intercambiar dos posiciones con index, con comentarios, así se tienen varios conceptos juntos.
Ejemplo: D -> A A -> B B -> C C -> E E
my_new_list.exchange(0, 3)
C -> A A -> B B -> D D -> E E
La clase completa con los métodos anteriores:
from node import Node class SinglyLinkedList: def __init__(self): self.head = None self.size_list = 0 def append(self, data): node = Node(data) if self.head == None: self.head = node else: current = self.head while current.next: current = current.next current.next = node self.size_list += 1 def size(self): return self.size_list def iter(self): current = self.head while current: val = current.data current = current.next yield val def delete(self, data): current = self.head previous = self.head while current: if current.data == data: if current == self.head: self.head = current.next else: previous.next = current.next self.size_list -= 1 return current.data previous = current current = current.next def search(self, data): found = False for node in self.iter(): if data == node: print(f"Data {data} found!") found = True if not found: print(f"Data {data} not found!") def clear(self): self.head = None self.head = None self.size_list = 0 # Print values in the linked list def show(self): probe = self.head while probe != None: print(probe.data) probe = probe.next # Searching a node def search_node(self, item): probe = self.head while probe != None and item != probe.data: probe = probe.next if probe != None: print(f"Target item {item} has been found!") else: print(f"Target item {item} is not in the linked list!") # Replace data in a node with other data def replace_node(self, item, new_item): probe = self.head while probe != None and item != probe.data: probe = probe.next if probe != None: probe.data = new_item print(f"{new_item} replaced the old value {item} in the node") else: print(f"The target item {item} is not in the linked list") # Insert node at the beginning of the list def insert_node_begin(self, data): self.head = Node(data, self.head) # Insert new node in the end of the list def insert_node_ending(self, data): new_node = Node(data) if self.head is None: self.head = new_node else: probe = self.head while probe.next != None: probe = probe.next probe.next = new_node # Delete the node at beginning of the list def delete_node_begin(self): removed_item = self.head.data self.head = self.head.next print(f"The node {removed_item} was deleted") # Delete the node in the end of the list def delete_node_end(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"The node {removed_item} was deleted") # Add node in determined position def add_node_position(self, item, index): 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(item, probe.next) # Delete node in determined position def delete_node_position(self, index): if index <= 0 or self.head.next is None: removed_item = self.head.data self.head = self.head.next print(f"The node {removed_item} was deleted") else: probe = self.head while index > 1 and probe.next.next != None: probe = probe.next index -= 1 removed_item = probe.next.data probe.next = probe.next.next print(f"The node {removed_item} was deleted ") llist = SinglyLinkedList() llist.append("A") llist.append("B") llist.append("C") llist.append("D") llist.show() # Insert node at the beginning llist.insert_node_begin("Z") print("List with new node at the beginning") llist.show() # Search a node llist.search_node("C") # Replace a node llist.replace_node("B", "F") print("New list") llist.show() # Insert node in the end llist.insert_node_ending("H") print("List with new node in the end") llist.show() # Delete the node beginning of the list llist.delete_node_begin() print("New list with node deleted at beginnining") llist.show() # Delete the node in the end of the list llist.delete_node_end() print("New list with node deleted in the end") llist.show() # Add node in position 3 llist.add_node_position("P", 3) print("New list with new node added in position 3") llist.show() # Delete the node in position 1 llist.delete_node_position(1) print("New list without the node in position 1 ") llist.show()
creo que llamar tail al primer valor que entra no es muy habitual, usualmente se le llama head al primera valor. Ejemplo:
class Node: def __init__(self, data, next=None): self.data = data self.next = None class SinglyLinkedList: def __init__(self): self.head = None self.size: int = 0
Mi aporte con todos los métodos:
from nodes import Node class singlyLinkedList(): ##constructor def __init__(self) -> None: self.head = None self.tail = None self.size = 0 ## add a node at the begining def push(self, value): """Add a node at the begining""" new_node = Node(value) if self.head == None: self.head = new_node else: new_node.next = self.head self.head = new_node self.size += 1 ## add a node at the end of linked list (floating tail) def append(self, value): """add a node at the end of linked list (floating tail)""" new_node = Node(value) if self.head == None: self.head = new_node else: current = self.head while current.next: current = current.next current.next = new_node self.size += 1 ## delete first node of list def deleteFirst(self): """delete first node of list""" current = self.head if self.head == None: print('The list is empty!') else: self.head = current.next self.size -= 1 ## delete laste node of list def deleteLast(self): """delete first node of list""" current = self.head if self.head == None: print('The list is empty!') else: while current: if current.next.next == None: current.next = None current = current.next self.size -= 1 ## insert node at specified position def insert(self, value, position=int): """insert node at specified position (equals index like using array.insert())""" current = self.head pos = 0 if position > self.size: print('Position out of list size!') else: while current: if position == pos + 1: current.next = Node(value, current.next) break current = current.next pos += 1 self.size += 1 ## delete node at specified position def delete(self, position): """delete node at specified position (equals index like using array.remove()). Not valid for first or last position (use deleteFirst or deleteLast instead)""" current = self.head pos = 0 if position > self.size - 1 or position <= 0: print('Position not valid! Use deleteFirst or deleteLast instead') else: while current: if position == pos + 1: current.next = current.next.next break current = current.next pos += 1 self.size -= 1 def size(self): return str(self.size) def printList(self): current = self.head print('Data in Single Linked List:', end='\n') while current is not None: print(current.data, end=" ") current = current.next print('') def iter(self): current = self.head while current: val = current.data current = current.next yield val if __name__ == '__main__': linkedList = singlyLinkedList() for i in range(6,0,-1): linkedList.push(i) for i in range(7,11): linkedList.append(i) linkedList.printList() linkedList.deleteFirst() linkedList.deleteLast() linkedList.insert(17, 3) linkedList.delete(3) linkedList.printList()
class Nodo: def __init__(self, valor, siguiente_nodo = None): self.valor = valor self.siguiente_nodo = siguiente_nodo class Lista_nodo: def __init__(self): self.limpiar() def limpiar(self): self.nodo_actual = None self.__SEGURO__ = False self.nodo_tmp = None self.tam = 0 @staticmethod def a_lista_nodo(data): nueva_lista = Lista_nodo() if type(data) == list or type(data) == tuple: for val in data: Lista_nodo.append(val) elif type(data) == dict: for K, V in data.items(): nueva_lista.append((K,V)) elif type(data) == Nodo: nueva_lista.nodo_actual = data nueva_lista.tam = 1 while data.siguiente_nodo: nueva_lista.tam += 1 data = data.siguiente_nodo elif type(data) == str: for val in data.split(" "): nueva_lista.append(val) else: nueva_lista.append(data) return nueva_lista def add(self, struct, indice = -1): Lista_nodo_2 = struct if type(struct) != Lista_nodo: Lista_nodo_2 = Lista_nodo.a_lista_nodo(struct) if self.tam == 0: self = Lista_nodo_2 return elif Lista_nodo_2.tam == 0: return self.tam += Lista_nodo_2.tam Lista_nodo_2.__SEGURO__ = True tmp_2 = Lista_nodo_2.index(-1) Lista_nodo_2.__SEGURO__ = False if indice == 0: tmp_2.siguiente_nodo = self.nodo_actual self.nodo_actual = Lista_nodo_2.nodo_actual return try: self.__SEGURO__ = True tmp = self.index(indice) except AssertionError: raise AssertionError("Indice inexistente") finally: self.__SEGURO__ = False self.nodo_tmp.siguiente_nodo = Lista_nodo_2.nodo_actual tmp_2.siguiente_nodo = tmp def append(self,valor): nodo_nuevo = Nodo(valor) self.tam += 1 if not self.nodo_actual: self.nodo_actual = nodo_nuevo return nodo_siguiente = self.nodo_actual while nodo_siguiente.siguiente_nodo: nodo_siguiente = nodo_siguiente.siguiente_nodo nodo_siguiente.siguiente_nodo = nodo_nuevo def index(self,indice): if not self.tam: raise AssertionError("Error sin elementos") def INDEX(INDICE): if INDICE > self.tam - 1 or INDICE < 0: raise AssertionError("Error de indice fuera de los limites") i = 0 self.nodo_tmp = nodo = self.nodo_actual while i != INDICE and nodo.siguiente_nodo: self.nodo_tmp = nodo nodo = nodo.siguiente_nodo i += 1 if self.__SEGURO__: return nodo return self.nodo_tmp.siguiente_nodo.valor if indice < 0: return INDEX(self.tam + indice) else: return INDEX(indice) def pop(self,indice = -1): self.__SEGURO__ = True try: self.nodo_tmp.siguiente_nodo = self.index(indice).siguiente_nodo self.tam -= 1 except AssertionError: raise AssertionError("Indice inexistente") finally: self.__SEGURO__ = False def find(self,valor): for val , indice in self.iter_items(): if val == valor: print("valor encontrado") return indice print("el valor no existe") return None def printing(self,elementos_mostrados_en_fila = 10): print("|",end="") salto = elementos_mostrados_en_fila - 1 for val, i in self.iter_items(): if i < salto: print(f" {val} |",end="") else: salto += elementos_mostrados_en_fila - 1 print(f" {val} |") print("") def iter(self): for val, i in self.iter_items(): yield val def iter_items(self): nodo_siguiente = self.nodo_actual if not nodo_siguiente: return i = 0 while nodo_siguiente.siguiente_nodo: val = nodo_siguiente.valor nodo_siguiente = nodo_siguiente.siguiente_nodo yield (val, i) i += 1 yield (nodo_siguiente.valor,i) if __name__ == "__main__": from random import randint lista = Lista_nodo() print("\nmetodo append [ Nodo.append(",end="") for i in range(1,8): val = randint(1,20) print(f"{val},",end="") lista.append(val) print(") ]\n") print("metodo pop [Nodo.pop(\"con o si indice\")]\n") lista.printing() i = 4 lista.pop(i) print(f"Nodo.pop({i})") lista.printing() print("\nmetodo index [Nodo.index(int)]\n") print(f"Nodo[{i}] = {lista.index(i)}") print("\nmetodo iter [Nodo.iter()]\n") for val in lista.iter(): print(val,end= ",") print("\n\nmetodo iter_items [Nodo.iter_items()]\n") for val, idx in lista.iter_items(): print(f"[{idx}] = {val}",end=" | ") print("\n\nmetodo find [Nodo.find(\"valor\")]\n") j = 11 print(f"indice = {lista.find(j)} Nodo.find({j})\n") string = "hola adios" nodo = Nodo("uno") print(f"\nmetodo add Node.add(data,posicion)\n") lista.printing(15) lista.add(string,4) print(f"Node.add(str, 4) str = {string}") lista.printing(15) lista.add(nodo,0) print(f"Node.add(nodo, 0) nodo simple = {nodo.valor}") lista.printing(15) dicionario = {"one" : 1, "two":2,"three":3} lista.add(dicionario,-2) print(f"Node.add(dicionario, 0) nodo simple = {dicionario}") lista.printing(15) nueva_lista = Lista_nodo() for i in range(1,5): val = randint(87,126) nueva_lista.append(chr(val)) print(f"Node.add(lista_nodos, 3) otra lista de nodos = ",end="") nueva_lista.printing() lista.add(nueva_lista,3) lista.printing(15)
Aquí mi solución con todos los métodos:
Les comparto la clase que cree usando las operaciones presentadas en el video. Decidi que el head sería el index 0.
from node import Node class SimpleLinkedList(): def __init__(self): self.head = None def range(self, start, stop): # * Creación de los nodos enlazados (linked list) for count in range(stop, start, -1): self.head = Node(count, self.head) def __str__(self): # * Recorrer e imprimir valores de la lista probe = self.head result = '' while probe != None: result += f'{probe.data} ' probe = probe.next result = result.strip() return result def search(self, target_item): # * Busqueda de un elemento probe = self.head while probe != None and target_item != probe.data: probe = probe.next if probe != None: 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 != None and target_item != probe.data: probe = probe.next if probe != None: probe.data = new_item print( f"{new_item} replace the old value in the node number {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) self.head = Node(new_item, self.head) def append(self, new_item): # * Insertar un nuevo elemento/nodo al final(tail) new_node = Node(new_item) 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 shift(self): # * Eliminar un elmento/nodo al inicio(head) removed_item = self.head.data self.head = self.head.next print(f'Removed_item: {removed_item}') return removed_item def pop(self): # * Eliminar un elmento/nodo al final(tail) 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'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.head is None or index <= 0: self.head = Node(new_item, 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 delete_by_index(self,index): # * Eliminar un nuevo elemento/nodo por "indice" (Cuenta de Head - Tail) if self.head is None or index <= 0: removed_item = self.head.data self.head = self.head.next print(removed_item) else: probe = self.head while index > 1 and probe.next.next != None: probe = probe.next index -= 1 removed_item = probe.next.data probe.next = probe.next.next print(f'Removed_item: {removed_item}') return removed_item
En este código pruevo el funcionamiento
from simple_linked_list import SimpleLinkedList simple_list = SimpleLinkedList() simple_list.range(0,6) print(simple_list) simple_list.search(2) simple_list.search(-1) simple_list.replace(3,'replace') print(simple_list) simple_list.unshift('shift') print(simple_list) simple_list.append('apppend') print(simple_list) simple_list.shift() print(simple_list) simple_list.pop() print(simple_list) simple_list.insert("insert",3) print(simple_list) simple_list.delete_by_index(3) print(simple_list)
y las salidas
1 2 3 4 5 6 Target item 2 has been found Target item -1 is not in the linked list replace replace the old value in the node number 3 1 2 replace 4 5 6 shift 1 2 replace 4 5 6 shift 1 2 replace 4 5 6 apppend Removed_item: shift 1 2 replace 4 5 6 apppend Removed_item: apppend 1 2 replace 4 5 6 1 2 replace insert 4 5 6 Removed_item: insert 1 2 replace 4 5 6
