Contenido del curso
Singly Linked List en Python
Singly Linked List en Python
Una Singly Linked List (lista enlazada simple) es una estructura de datos lineal en la que cada elemento (nodo) contiene un valor y un puntero al siguiente nodo en la lista. La lista enlazada comienza con un nodo llamado cabeza (head) que apunta al primer elemento de la lista, y termina con un nodo llamado cola (tail) que apunta a None.
Complejidad Algorítmica
La siguiente tabla muestra la complejidad algorítmica (notación Big O) de las diferentes operaciones en las singly linked lists:
| Algoritmo | Notación Big O |
|---|---|
| Acceder a Elementos | O(n) |
| Inserción al Inicio | O(1) |
| Inserción al Final | O(n) |
| Inserción en Medio | O(n) |
| Eliminación al Inicio | O(1) |
| Eliminación al Final | O(n) |
| Eliminación en Medio | O(n) |
Ventajas de las Singly Linked Lists
Limitaciones de las Singly Linked Lists
Implementación de Singly Linked List en Python
En Python, se puede implementar una singly linked list utilizando clases. Cada nodo de la lista es un objeto que tiene dos propiedades: value, que almacena el valor del nodo, y next, que apunta al siguiente nodo en la lista.
Veamos un ejemplo de cómo se puede construir una singly linked list en Python:
class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None self.length = 0 def append(self, value): new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node self.length += 1 def prepend(self, value): new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head = new_node self.length += 1 def delete(self, value): if self.head is None: return if self.head.value == value: self.head = self.head.next self.length -= 1 return current_node = self.head while current_node.next: if current_node.next.value == value: current_node.next = current_node.next.next self.length -= 1 return current_node = current_node.next
En la implementación anterior, tenemos dos clases: Node y LinkedList. La clase Node representa un nodo en la lista, mientras que la clase LinkedList es la lista en sí misma.
El método append agrega un nuevo nodo al final de la lista. Si la lista está vacía, los punteros head y tail se actualizan para que apunten al nuevo nodo. De lo contrario, se actualiza el puntero next del último nodo en la lista para que apunte al nuevo nodo, y el puntero tail se actualiza para que apunte al nuevo nodo.
El método prepend agrega un nuevo nodo al inicio de la lista. Si la lista está vacía, los punteros head y tail se actualizan para que apunten al nuevo nodo. De lo contrario, se actualiza el puntero next del nuevo nodo para que apunte al nodo actual de la cabeza, y el puntero head se actualiza para que apunte al nuevo nodo.
El método delete elimina un nodo con un valor dado de la lista. Si el valor se encuentra en el nodo de la cabeza, el puntero head se actualiza para que apunte al siguiente nodo. De lo contrario, se recorre la lista hasta encontrar el nodo anterior al nodo que se desea eliminar. Una vez encontrado, se actualiza el puntero next del nodo anterior para que salte el nodo a eliminar.
Utilizando esta implementación, podemos aprovechar las ventajas de las singly linked lists para realizar operaciones eficientes de inserción y eliminación. Sin embargo, es importante tener en cuenta las limitaciones y elegir la estructura de datos adecuada según los requisitos específicos del problema.
Paola Alapizco
Estudiante
Waldir Zapata Garcia
Estudiante
Juan Diego Ussa Aponte
EstudianteWaldir Zapata Garcia
Estudiante
Emilio Sala
Estudiante
Nicolas Alpargatero
Estudiante
Jhon Freddy Tavera Blandon
EstudiantePara quienes deseen profundizar más en esta estructura de datos les adjunto un video donde explican detalladamente las Linked List / Lista Enlazada. . Espero les sea de ayuda.
class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None self.length = 0 def append(self, value): new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node self.length += 1 def prepend(self, value): new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head = new_node self.length += 1 def delete(self, value): if self.head is None: return if self.head.value == value: self.head = self.head.next self.length -= 1 return current_node = self.head while current_node.next: if current_node.next.value == value: current_node.next = current_node.next.next self.length -= 1 return current_node = current_node.next # Método para imprimir la lista de nodos def print_list(self): node = self.head while node != None: print(node.value, end =" => ") node = node.next element=LinkedList() #instancia de la clase element.append(5) element.append(1) element.prepend(2) element.print_list()
La Notación Big O es una forma de describir la complejidad algorítmica de un algoritmo en términos de cómo su tiempo de ejecución o espacio requerido crece a medida que aumenta el tamaño de la entrada. Se utiliza para clasificar algoritmos según su rendimiento y eficiencia. Por ejemplo, en el caso de una "Singly Linked List", las operaciones de acceso, inserción y eliminación tienen diferentes complejidades en notación Big O, como O(n) para acceder a elementos y O(1) para la inserción al inicio. Esto permite entender y comparar la eficiencia de diferentes enfoques algorítmicos.
un aporte sobre listas enlazadas
link: https://pythondiario.com/2018/07/linked-list-listas-enlazadas.html
https://www.geeksforgeeks.org/insert-node-middle-linked-list/
Aqui un video que comenta sobre otro video de la comparación entre listas y vectores https://www.youtube.com/watch?v=cvZArAipOjo
Lo de la Big O al final me da curiosidad, pues eso depende de la implementación, y acceder all Tail también puede ser O(1)
.
Dejo una clase que me gusto del tema:
La ventaja principal de una Singly Linked List es que permite una inserción y eliminación eficiente de elementos en cualquier posición de la lista. Sin embargo, a diferencia de las listas nativas de Python, las Singly Linked Lists no ofrecen acceso aleatorio a los elementos (por índice), ya que para acceder a un elemento específico, debemos recorrer la lista desde el inicio hasta el nodo deseado.
