3.1 Operaciones con datos: inserción, eliminación, búsqueda
Inserción (Insert):
Operación de añadir un nuevo elemento a una estructura de datos. La inserción puede ocurrir al inicio, al final o en una posición arbitraria de la estructura de datos.
Eliminación (Delete):
Operación de eliminar un elemento de una estructura de datos. La eliminación puede basarse en el valor del elemento, en el índice o en la posición del elemento en la estructura de datos.
Búsqueda (Search):
Operación de encontrar un elemento en una estructura de datos. La búsqueda puede basarse en el valor u otros criterios.
Ejemplos de operaciones:
- Arrays: La inserción y eliminación requieren mover elementos, lo que puede ser costoso en tiempo —
O(n). - Listas enlazadas: La inserción y eliminación pueden ocurrir en
O(1), si se conoce la posición del nodo. - Tablas hash: La búsqueda, inserción y eliminación generalmente se realizan en
O(1)en el caso promedio. - Árboles: Las operaciones de búsqueda, inserción y eliminación pueden realizarse en
O(log n)en árboles balanceados.
3.2 Conceptos básicos: array, lista, pila, cola
Array
Array es una secuencia de elementos de un único tipo, a los que se puede acceder mediante un índice.
Complejidad de operaciones: Acceso por índice — O(1), inserción y eliminación — O(n).
Ejemplo: Creación de un array, modificación de un elemento y muestra del resultado
# Creamos un array de números
arr = [1, 2, 3, 4, 5]
# Cambiamos el elemento con índice 2 (tercer elemento, ya que la indexación comienza en 0)
arr[2] = 10
# Mostramos el array modificado
print(arr) # Salida: [1, 2, 10, 4, 5]
# Añadimos un nuevo elemento al final del array
arr.append(6)
print(arr) # Salida: [1, 2, 10, 4, 5, 6]
# Eliminamos un elemento por índice
del arr[1]
print(arr) # Salida: [1, 10, 4, 5, 6]
Lista
Lista es una colección de elementos donde cada elemento contiene una referencia al siguiente (lista enlazada simple) o al siguiente y anterior (lista doblemente enlazada) elemento.
Complejidad de operaciones: Inserción y eliminación — O(1) si se conoce la posición, búsqueda — O(n).
Ejemplo: Creación de una simple lista enlazada y su recorrido
# Definimos la estructura de un nodo de lista
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Creamos una lista enlazada simple
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# Enlazamos los nodos
node1.next = node2
node2.next = node3
# Establecemos el inicio de la lista
list_head = node1
# Recorremos la lista y mostramos los datos
current = list_head
while current:
print(current.data)
current = current.next
# Salida:
# 101
# 102
# 103
Pila (Stack)
Pila es una colección de elementos con el principio LIFO (Last In, First Out): el último en entrar es el primero en salir.
Complejidad de operaciones: Inserción (push) y eliminación (pop) — O(1).
Ejemplo: Implementación y uso de una pila para verificar el balance de paréntesis
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# Probamos distintas expresiones
print(is_balanced("({[]})")) # Salida: True
print(is_balanced("([)]")) # Salida: False
print(is_balanced("((")) # Salida: False
Cola (Queue)
Cola es una colección de elementos con el principio FIFO (First In, First Out): el primero en entrar es el primero en salir.
Complejidad de operaciones: Inserción (enqueue) y eliminación (dequeue) — O(1).
Ejemplo: Implementación y uso de una cola para simular el procesamiento de tareas
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"Tarea '{task}' añadida a la cola")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"Procesando tarea: '{task}'")
else:
print("La cola está vacía")
def display_queue(self):
print("Cola de tareas actual:", list(self.queue))
# Creamos y usamos una cola de tareas
task_queue = TaskQueue()
task_queue.add_task("Enviar email")
task_queue.add_task("Actualizar base de datos")
task_queue.add_task("Crear informe")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# Salida:
# Tarea 'Enviar email' añadida a la cola
# Tarea 'Actualizar base de datos' añadida a la cola
# Tarea 'Crear informe' añadida a la cola
# Cola de tareas actual: ['Enviar email', 'Actualizar base de datos', 'Crear informe']
# Procesando tarea: 'Enviar email'
# Procesando tarea: 'Actualizar base de datos'
# Cola de tareas actual: ['Crear informe']
3.3 Diferencias entre diferentes tipos de estructuras de datos
Aquí están las diferencias clave entre diferentes tipos de estructuras de datos:
Arrays:
- Acceso: Acceso rápido por índice —
O(1). - Cambio de tamaño: Tamaño fijo, aumentar requiere copiar todos los elementos —
O(n). - Adecuado para: Acceso aleatorio a elementos, cuando el tamaño de los datos se conoce de antemano.
Listas enlazadas:
- Acceso: Acceso lento por índice —
O(n). - Cambio de tamaño: Tamaño fácilmente modificable, inserción y eliminación toman
O(1). - Adecuado para: Adición y eliminación frecuente de elementos.
Pila:
- Principio de operación:
LIFO. - Operaciones: Inserción y eliminación solo en un extremo —
O(1). - Adecuado para: Orden inverso de ejecución de tareas, gestión de llamadas a funciones.
Cola:
- Principio de operación:
FIFO. - Operaciones: Inserción y eliminación en diferentes extremos —
O(1). - Adecuado para: Gestión de tareas en el orden de llegada.
3.4 Aplicación de diferentes estructuras de datos
Ejemplos de aplicación de diferentes estructuras de datos en la práctica:
Arrays
Almacenamiento de datos de longitud fija, como los días de la semana o los meses del año.
Ejemplo: Uso de un array para trabajar con los días de la semana
# Creamos un array con los días de la semana
days = ["Lunes", "Martes", "Miércoles", "Jueves", "Viernes", "Sábado", "Domingo"]
# Obtenemos el día de la semana por índice (por ejemplo, el tercer día)
print(days[2]) # Salida: Miércoles
# Cambiamos el nombre del día
days[0] = "Lunes (inicio de semana)"
print(days[0]) # Salida: Lunes (inicio de semana)
# Recorremos todos los días de la semana
for day in days:
print(day)
# Salida:
# Lunes (inicio de semana)
# Martes
# Miércoles
# Jueves
# Viernes
# Sábado
# Domingo
Listas enlazadas
Implementación de colecciones dinámicas, donde los elementos pueden añadirse y eliminarse desde el medio de la colección.
Ejemplo: Implementación y uso de una lista enlazada para almacenar una lista de tareas
class TodoItem:
def __init__(self, tarea):
self.tarea = tarea
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, tarea):
new_item = TodoItem(tarea)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("La lista de tareas está vacía")
else:
while current:
print(f"- {current.tarea}")
current = current.next
# Creamos y usamos una lista de tareas
todo = TodoList()
todo.add_task("Comprar alimentos")
todo.add_task("Llamar a mamá")
todo.add_task("Preparar presentación")
print("Mi lista de tareas:")
todo.display_tasks()
# Salida:
# Mi lista de tareas:
# - Comprar alimentos
# - Llamar a mamá
# - Preparar presentación
Pila
Orden inverso de ejecución de tareas, por ejemplo, manejo de llamadas a funciones en recursión, deshacer operaciones (undo).
Ejemplo: Uso de una pila para invertir una cadena
def reverse_string(s):
stack = []
# Ponemos cada carácter de la cadena en la pila
for char in s:
stack.append(char)
reversed_s = ''
# Sacamos caracteres de la pila, formando la cadena inversa
while stack:
reversed_s += stack.pop()
return reversed_s
# Ejemplo de uso
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Cadena original: {original}")
print(f"Cadena invertida: {reversed_str}")
# Salida:
# Cadena original: Hello, World!
# Cadena invertida: !dlroW ,olleH
Cola
Gestión de tareas en el orden de llegada, por ejemplo, trabajos en cola en una impresora, colas de atención al cliente.
Ejemplo: Simulación de una cola de impresión de documentos
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"Documento '{document}' añadido a la cola de impresión")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"Imprimiendo documento: '{document}'")
else:
print("La cola de impresión está vacía")
def display_queue(self):
print("Cola de impresión actual:", list(self.queue))
# Creamos y usamos una cola de impresión
printer = PrinterQueue()
printer.add_document("Informe")
printer.add_document("Presentación")
printer.add_document("Contrato")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# Salida:
# Documento 'Informe' añadido a la cola de impresión
# Documento 'Presentación' añadido a la cola de impresión
# Documento 'Contrato' añadido a la cola de impresión
# Cola de impresión actual: ['Informe', 'Presentación', 'Contrato']
# Imprimiendo documento: 'Informe'
# Imprimiendo documento: 'Presentación'
# Cola de impresión actual: ['Contrato']
En este ejemplo, hemos creado una simple simulación de una cola de impresión. Los documentos se añaden al final de la cola y se imprimen en el orden en que llegaron, lo que demuestra el principio FIFO (First In, First Out).
GO TO FULL VERSION