Estructuras de datos compuestas: listas lineales y no lineales
Objetivo: El alumno aprenderá las formas de representar y operar las principales listas lineales y no lineales en la computadora.
Dominar pilas, colas, colas dobles, listas circulares, listas doblemente ligadas y árboles (incluyendo árboles binarios) te permite diseñar software eficiente, mantenible y escalable. En este artículo encontrarás definiciones claras, operaciones esenciales, representaciones en memoria y algoritmos paso a paso con sus complejidades Big-O.
2.1 Listas lineales
Una lista lineal es una colección de elementos donde cada elemento (excepto el primero y el último) tiene un único predecesor y un único sucesor. La posición relativa de cada elemento es significativa y las operaciones suelen ocurrir en extremos específicos o posiciones concretas.
2.1.1 Pilas
2.1.1.1 Definiciones y operaciones
- DefiniciónEstructura LIFO (Last-In, First-Out). El último elemento en entrar es el primero en salir.
- Operaciones
- push(x): inserta x en el tope.
- pop(): elimina y devuelve el tope.
- peek()/top(): devuelve el tope sin eliminar.
- isEmpty(): verifica si está vacía.
- size(): cantidad de elementos.
- Complejidad push/pop/peek O(1); size O(1).
2.1.1.2 Representación y algoritmos
Representación con arreglo (vector): el índice top apunta al último elemento.
Considera overflow/underflow.
- Algoritmo push:
- Si top = capacidad − 1 → overflow.
- Incrementa top.
- arr[top] ← x.
- Algoritmo pop:
- Si top = −1 → underflow.
- x ← arr[top].
- Decrementa top.
- Devuelve x.
Representación ligada (lista): nodo {dato, next}; tope apunta al primer nodo.
- push: crea nodo n; n.next ← tope; tope ← n.
- pop: si tope = null → underflow; x ← tope.dato; tope ← tope.next; devuelve x.
Uso típico: deshacer/rehacer, recorrido en profundidad (DFS), evaluación de expresiones.
2.1.2 Cola
2.1.2.1 Definiciones y operaciones
- DefiniciónEstructura FIFO (First-In, First-Out). El primero en entrar es el primero en salir.
- Operaciones
- enqueue(x): inserta al final.
- dequeue(): elimina y devuelve el frente.
- front(): consulta el frente.
- isEmpty(); isFull() (si es un arreglo con capacidad fija).
- Complejidad enqueue/dequeue O(1); front O(1).
2.1.2.2 Representación y algoritmos
Arreglo circular: índices front y rear; tamaño size; capacidad cap.
- enqueue(x):
- Si size = cap → overflow.
- rear ← (rear + 1) mod cap.
- arr[rear] ← x.
- size ← size + 1.
- dequeue():
- Si size = 0 → underflow.
- x ← arr[front].
- front ← (front + 1) mod cap.
- size ← size − 1; devuelve x.
Lista ligada: punteros front y rear.
- enqueue: crea nodo; rear.next ← nodo; rear ← nodo (si vacía, front ← rear).
- dequeue: si vacía → underflow; x ← front.dato; front ← front.next; si front = null, rear ← null; devuelve x.
Uso típico: planificadores, colas de impresión, buffers de E/S.
2.1.3 Cola doble (Deque)
2.1.3.1 Definiciones y operaciones
- DefiniciónEstructura que permite inserciones y eliminaciones tanto por el frente como por el final.
- Operaciones
- insertFront(x); insertRear(x).
- deleteFront(); deleteRear().
- getFront(); getRear().
- Complejidad Todas O(1) en implementaciones adecuadas.
2.1.3.2 Representación y algoritmos
Arreglo circular con front, rear, size y cap.
- insertFront(x): si size = cap → overflow; front ← (front − 1 + cap) mod cap; arr[front] ← x; size++.
- insertRear(x): si size = cap → overflow; rear ← (rear + 1) mod cap; arr[rear] ← x; size++.
- deleteFront(): si size = 0 → underflow; front ← (front + 1) mod cap; size--.
- deleteRear(): si size = 0 → underflow; rear ← (rear − 1 + cap) mod cap; size--.
Lista doblemente ligada para deques no acotados.
Uso típico: ventanas deslizantes, cachés LRU, planificación de tareas.
2.1.4 Lista circular (simple)
2.1.4.1 Definiciones y operaciones
- DefiniciónLista ligada donde el último nodo apunta al primero, formando un ciclo.
- Operaciones
- insertar al frente y al final.
- eliminar al frente y al final.
- buscar; recorrer (ciclo controlado).
- Complejidad Inserción/eliminación en extremos O(1) con puntero tail; búsqueda O(n).
2.1.4.2 Representación y algoritmos
Representación ligada: mantener puntero tail (último). tail.next es la cabeza.
- insertFront(x):
- Crear nodo n con dato x.
- Si lista vacía: n.next ← n; tail ← n.
- Si no: n.next ← tail.next; tail.next ← n.
- insertRear(x): como insertFront; luego tail ← tail.next (si insertaste delante) o enlaza n y actualiza tail a n.
- deleteFront():
- Si vacía → underflow.
- Si tail = tail.next → tail ← null.
- Si no: tail.next ← tail.next.next.
- deleteRear(): recorrer hasta el nodo previo a tail; ajustar enlaces y actualizar tail.
Uso típico: planificación circular (round-robin), buffers cíclicos.
2.1.5 Listas doblemente ligadas
2.1.5.1 Definiciones y operaciones
- DefiniciónLista de nodos con punteros a anterior (prev) y siguiente (next).
- Operaciones
- insertar al frente, al final y antes/después de un nodo.
- eliminar un nodo dado.
- recorrido hacia adelante y hacia atrás.
- Complejidad Inserción/eliminación en extremos O(1); búsqueda O(n).
2.1.5.2 Representación y algoritmos
Representación ligada: nodos {dato, prev, next}; punteros head y tail.
- insertFront(x): crea n; n.next ← head; n.prev ← null; si head ≠ null, head.prev ← n; head ← n; si tail = null, tail ← n.
- insertRear(x): crea n; n.prev ← tail; n.next ← null; si tail ≠ null, tail.next ← n; tail ← n; si head = null, head ← n.
- delete(node p): si p.prev ≠ null → p.prev.next ← p.next; si p.next ≠ null → p.next.prev ← p.prev; actualizar head/tail si aplica.
Uso típico: navegadores (atrás/adelante), editores, cachés LRU.
2.2 Listas no lineales
Las estructuras no lineales organizan datos jerárquica o relacionalmente, permitiendo múltiples caminos entre elementos. El ejemplo clásico son los árboles.
2.2.1 Árboles
2.2.1.1 Conceptos y definiciones
- Árbol: conjunto de nodos con una raíz y subárboles disjuntos.
- Raíz, padre, hijo, hermano, hoja (grado 0), nivel, altura (máximo nivel), grado de un nodo (número de hijos).
- Recorridos: preorden (raíz, izq, der), inorden (izq, raíz, der), postorden (izq, der, raíz), por niveles (BFS).
- Propiedad: un árbol con n nodos tiene n − 1 aristas.
2.2.1.2 Representación de árboles en la computadora
- Nodo con lista de hijos: nodo {dato, hijos[]} o primerHijo/sigHermano.
- Arreglo de padres: parent[i] = índice del padre (útil para árboles estáticos).
- Lista de adyacencia o matriz de adyacencia: común en grafos/árboles generales.
Algoritmos de recorrido (visita)
- Preorden:
- Visitar nodo actual.
- Para cada hijo, aplicar preorden.
- Por niveles (BFS):
- Inicializa cola con la raíz.
- Mientras la cola no esté vacía: extrae frente, visita, encola hijos.
Complejidad de recorridos: O(n).
2.2.2 Árboles binarios
2.2.2.1 Conceptos y definiciones
- Árbol binario: cada nodo tiene hasta 2 hijos: izquierdo y derecho.
- Especiales: completo, lleno, perfecto, degenerado.
- Árbol binario de búsqueda (BST): para cada nodo, claves izquierda ≤ clave < claves derecha.
- Recorridos: preorden, inorden (ordena claves en BST), postorden, por niveles.
2.2.2.2 Representación en la computadora
- Nodos enlazados: {clave, left, right}.
- Arreglo (estilo heap): índice i; left = 2i + 1; right = 2i + 2 (eficiente si está casi lleno).
Algoritmos clave (BST)
- search(k):
- Si nodo = null → no encontrado.
- Si k = nodo.clave → encontrado.
- Si k < nodo.clave → busca en left; de lo contrario, en right.
- insert(k):
- Si árbol vacío → crea raíz con k.
- Compara con el nodo actual; avanza a left o right según k.
- Inserta cuando encuentres enlace null.
- delete(k) (resumen):
- Sin hijos: elimina el nodo.
- Un hijo: enlaza padre con el hijo.
- Dos hijos: reemplaza con sucesor inorden (mínimo del subárbol derecho) y elimina el sucesor.
Complejidad promedio: búsqueda/insertar/eliminar O(log n). Peor caso (desbalanceado): O(n). Considera estructuras balanceadas (AVL, Red-Black) para garantizar O(log n).
Operaciones fundamentales con ejemplos en Python
A continuación se muestran operaciones típicas de estructuras de datos lineales y no lineales, cada una acompañada de un ejemplo práctico en Python que puedes copiar y ejecutar.
Pilas (Stack)
Operaciones: push (apilar), pop (desapilar), peek (cima), is_empty (vacía).
# Implementación con lista (LIFO)
stack = []
def push(x):
stack.append(x) # O(1)
def pop_():
return stack.pop() # O(1) - lanza IndexError si está vacía
def peek():
return stack[-1] if stack else None
def is_empty():
return len(stack) == 0
# Uso
push(10); push(20); push(30)
print(peek()) # 30
print(pop_()) # 30
print(is_empty()) # FalseColas (Queue FIFO)
Operaciones: enqueue (encolar), dequeue (desencolar), front (frente), rear (final), is_empty (vacía).
from collections import deque
q = deque()
def enqueue(x):
q.append(x) # O(1) amortizado
def dequeue():
return q.popleft() if q else None # O(1)
def front():
return q[0] if q else None
def rear():
return q[-1] if q else None
def is_empty():
return len(q) == 0
# Uso
enqueue('A'); enqueue('B'); enqueue('C')
print(front()) # 'A'
print(dequeue()) # 'A'
print(rear()) # 'C'Cola doble (Deque)
Operaciones: appendleft, append (derecha), popleft, pop (derecha), peek izquierda/derecha.
from collections import deque
dq = deque()
dq.appendleft(1) # <- inserta por la izquierda
dq.append(2) # inserta por la derecha ->
print(dq) # deque([1, 2])
print(dq.popleft()) # 1
print(dq.pop()) # 2Cola de prioridad (Priority Queue / Min-Heap)
Operaciones: push (insertar con prioridad), pop_min (extraer mínima), peek_min (ver mínima), is_empty.
import heapq
pq = [] # almacena tuplas (prioridad, item)
def push(item, priority):
heapq.heappush(pq, (priority, item)) # O(log n)
def pop_min():
return heapq.heappop(pq)[1] if pq else None # O(log n)
def peek_min():
return pq[0][1] if pq else None # O(1)
def is_empty():
return not pq
# Uso
push('tarea-urgente', 1)
push('tarea-media', 5)
push('tarea-baja', 9)
print(peek_min()) # 'tarea-urgente'
print(pop_min()) # 'tarea-urgente'Lista enlazada simple
Operaciones: insert_head, insert_tail, search, delete, traverse.
class Node:
def __init__(self, data, nxt=None):
self.data = data
self.next = nxt
class LinkedList:
def __init__(self):
self.head = None
def insert_head(self, data): # O(1)
self.head = Node(data, self.head)
def insert_tail(self, data): # O(n)
if not self.head:
self.head = Node(data)
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = Node(data)
def search(self, target): # O(n)
cur = self.head
while cur:
if cur.data == target:
return cur
cur = cur.next
return None
def delete(self, target): # O(n)
cur, prev = self.head, None
while cur:
if cur.data == target:
if prev:
prev.next = cur.next
else:
self.head = cur.next
return True
prev, cur = cur, cur.next
return False
def traverse(self): # O(n)
cur, out = self.head, []
while cur:
out.append(cur.data)
cur = cur.next
return out
# Uso
ll = LinkedList()
ll.insert_head(3)
ll.insert_tail(5)
ll.insert_head(1)
print(ll.traverse()) # [1, 3, 5]
print(ll.search(3) is not None) # True
ll.delete(3)
print(ll.traverse()) # [1, 5]Árbol binario de búsqueda (BST)
Operaciones: insert, search, inorder (recorrido), delete.
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key): # O(h)
if not root:
return BSTNode(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def search(root, key): # O(h)
if not root or root.key == key:
return root
return search(root.left, key) if key < root.key else search(root.right, key)
def inorder(root): # O(n)
return inorder(root.left) + [root.key] + inorder(root.right) if root else []
def delete(root, key): # O(h)
if not root:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
# sucesor inorden (mínimo en subárbol derecho)
succ = root.right
while succ.left:
succ = succ.left
root.key = succ.key
root.right = delete(root.right, succ.key)
return root
# Uso
root = None
for k in [7, 3, 9, 1, 5, 8, 10]:
root = insert(root, k)
print(inorder(root)) # [1, 3, 5, 7, 8, 9, 10]
print(search(root, 5) is not None) # True
root = delete(root, 7)
print(inorder(root)) # [1, 3, 5, 8, 9, 10]Grafos (lista de adyacencia)
Operaciones: add_vertex, add_edge, BFS, DFS, shortest_path_unweighted.
from collections import deque, defaultdict
class Graph:
def __init__(self):
self.adj = defaultdict(list)
def add_vertex(self, v):
self.adj[v] # garantiza existencia
def add_edge(self, u, v, undirected=True):
self.adj[u].append(v)
if undirected:
self.adj[v].append(u)
def bfs(self, start):
visited = set([start])
order = []
q = deque([start])
while q:
u = q.popleft()
order.append(u)
for w in self.adj[u]:
if w not in visited:
visited.add(w)
q.append(w)
return order
def dfs(self, start):
visited, order = set(), []
def _dfs(u):
visited.add(u)
order.append(u)
for w in self.adj[u]:
if w not in visited:
_dfs(w)
_dfs(start)
return order
def shortest_path_unweighted(self, s, t):
q = deque([s])
parent = {s: None}
while q:
u = q.popleft()
if u == t:
break
for w in self.adj[u]:
if w not in parent:
parent[w] = u
q.append(w)
if t not in parent:
return None
path, cur = [], t
while cur is not None:
path.append(cur)
cur = parent[cur]
return list(reversed(path))
# Uso
g = Graph()
for v in ['A', 'B', 'C', 'D', 'E']:
g.add_vertex(v)
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'E')
print(g.bfs('A')) # ['A', 'B', 'C', 'D', 'E']
print(g.dfs('A')) # posible orden DFS
print(g.shortest_path_unweighted('A', 'E')) # ['A', 'C', 'E']Consejo rápido
- Pilas y colas: ideales para control de flujo y buffers.
- Listas enlazadas: inserciones/eliminaciones frecuentes sin realocación.
- Árboles y grafos: modelan jerarquías y redes; elige BFS/DFS según la necesidad.
- Colas de prioridad: cuando importa extraer siempre el elemento “más importante”.
2.3 Métodos de ordenamiento y búsqueda
Explora guías detalladas de cada algoritmo con animaciones, análisis de complejidad y mejores prácticas. Selecciona un método para ir a su artículo dedicado:
Consejo: elige el algoritmo según el tamaño de datos, distribución, restricciones de memoria y estabilidad requerida.
Conclusión
Las estructuras de datos compuestas son la columna vertebral de soluciones eficientes: pilas y colas resuelven flujos; deques y listas circulares optimizan escenarios en tiempo real; listas doblemente ligadas facilitan recorridos bidireccionales; y los árboles organizan información jerárquica permitiendo búsquedas rápidas. Dominar sus representaciones (arreglos y listas ligadas) y operaciones básicas te prepara para implementar algoritmos robustos.
Continúa con métodos de ordenamiento y búsqueda
Estructuras de datos compuestas