Contenido del curso
Día 1
Día 2
Día 3
Día 4
Día 5
Día 6
Día 7
Día 8
Día 9
Día 10
Día 11
Día 12
Día 13
Día 14
Día 15
Día 16
Día 17
Día 18
Día 19
Día 20
Día 21
Singly Linked List en Python
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.