= 'Habitación 103 - Vacante'
En este capítulo, presentaremos el tipo de estructura de datos más básico y común:Estructura de datos lineal。
Estructura de datos linealEs como una fila de personas haciendo cola:
- Cada persona (elemento) tiene una relación clara de anterior y posterior
- Excepto el primero y el último, cada persona tiene un predecesor y un sucesor
- Entre los elementos de datos existe una relación lineal uno a uno
Imagina que estás haciendo cola para comprar café u ordenando los libros de una estantería.
Estas situaciones tienen algo en común: los elementos están dispuestos uno tras otro, formando una línea.
En ciencias de la computación, este conjunto de datos ordenados secuencialmente es una estructura de datos lineal.
La característica de las estructuras de datos lineales es que, excepto el primer y el último elemento, cada elemento tiene exactamente unpredecesory unsucesor。
Estructuras de datos lineales comunes:
- Arreglo: como una fila de taquillas numeradas, cada una con una posición fija
- Lista enlazada: como una cadena de personas tomadas de la mano, donde cada una solo recuerda a la persona anterior y a la siguiente
- pila: como una pila de platos, solo se puede tomar o colocar desde la parte superior
- Cola: como hacer cola para comprar boletos, primero en llegar, primero en ser atendido
La siguiente figura muestra el sistema de clasificación de las estructuras de datos lineales; cada estructura tiene sus escenarios de aplicación y características de rendimiento específicos:

La siguiente figura muestra el proceso de operación básica de la pila; la pila sigue el principio LIFO (último en entrar, primero en salir):

Arreglo (Array)
Arreglo estático
| Característica | Descripción | Complejidad temporal |
|---|---|---|
| Acceder a un elemento | Acceso directo mediante índice | O(1) |
| Insertar elemento | Requiere mover los elementos posteriores | O(n) |
| Eliminar elemento | Requiere mover los elementos posteriores | O(n) |
| Asignación de espacio | Tamaño fijo, preasignado | O(1) |
Arreglo dinámico
| Característica | Descripción | Complejidad temporal |
|---|---|---|
| Acceder a un elemento | Acceso directo mediante índice | O(1) |
| Insertar elemento | Puede requerir expansión y copia | Promedio O(1), peor caso O(n) |
| Eliminar elemento | Requiere mover los elementos posteriores | O(n) |
| Asignación de espacio | Expansión automática | O(n) (al expandirse) |
Lista enlazada (Linked List)
Lista enlazada simple
| Operación | Descripción | Complejidad temporal |
|---|---|---|
| Acceder a un elemento | Requiere recorrer desde el principio | O(n) |
| Inserción en la cabeza | Inserción directa | O(1) |
| Inserción en la cola | Requiere recorrer hasta la cola | O(n) |
| Inserción en el medio | Requiere encontrar primero la posición | O(n) |
| Eliminar elemento | Requiere encontrar primero la posición | O(n) |
Lista enlazada doble
| Operación | Descripción | Complejidad temporal |
|---|---|---|
| Acceder a un elemento | Requiere recorrer desde el principio o desde el final | O(n) |
| Inserción en la cabeza | Inserción directa | O(1) |
| Inserción en la cola | Inserción directa (si hay un puntero a la cola) | O(1) |
| Inserción en el medio | Requiere encontrar primero la posición | O(n) |
| Eliminar elemento | Requiere encontrar primero la posición | O(n) |
Pila (Stack)
| Operación | Descripción | Complejidad temporal |
|---|---|---|
| push (apilar) | Agregar un elemento en la cima de la pila | O(1) |
| pop (desapilar) | Eliminar el elemento de la cima de la pila | O(1) |
| peek (ver) | Ver el elemento de la cima de la pila | O(1) |
| isEmpty (verificar si está vacía) | Comprobar si la pila está vacía | O(1) |
Cola (Queue)
| Operación | Descripción | Complejidad temporal |
|---|---|---|
| enqueue (encolar) | Agregar un elemento al final de la cola | O(1) |
| dequeue (desencolar) | Eliminar el elemento del frente de la cola | O(1) |
| front (ver el frente) | Ver el elemento del frente de la cola | O(1) |
| isEmpty (verificar si está vacía) | Comprobar si la cola está vacía | O(1) |
Diagrama comparativo de estructuras de datos lineales
Arreglo: el edificio de apartamentos fijo de los datos
El arreglo es la estructura de datos lineal más simple y directa.
Podemos imaginarlo como unedificio de apartamentos con un número fijo de pisos。
Conceptos básicos y características
- Almacenamiento contiguo: el arreglo ocupa un bloquecontiguode memoria, como las habitaciones de un edificio de apartamentos que están una al lado de la otra.
- Tamaño fijo: el arreglo debe definir su capacidad (longitud) al crearse y, generalmente, no puede cambiar después, igual que el número de habitaciones de un edificio de apartamentos queda fijo una vez construido.
- Acceso por índice: cada elemento (habitación) tiene un número único, llamadoíndice. En la mayoría de los lenguajes de programación, los índices comienzan desde
00. Puedes acceder directa y rápidamente a cualquier elemento mediante el índice, con una complejidad temporal de O(1).O(1)。
Operaciones principales y ejemplos de código
Usemos Python para demostrar el arreglo (en Python normalmente se usa `list`listpara simularlo, pero ten en cuenta que la `list` de Pythonlistes dinámica) y sus operaciones principales.
Ejemplo
apartment_building = ['Habitación 101-Juan Pérez', Habitación 102 - Li Si, Habitación 103 - Wang Wu, Habitación 104 - Vacante, Habitación 105 - Vacante]
print(Situación de los residentes del edificio de apartamentos:, apartment_building)
# 2. Acceder a los elementos (por índice)
# Acceder a la habitación 102
tenant = apartment_building[1] # El índice comienza en 0, por lo que 1 corresponde al segundo elemento
print(fEl residente de la habitación 102 es: {tenant})
# 3. Actualizar elementos
# El nuevo residente Zhao Liu se mudó a la habitación 104
apartment_building[3] = Habitación 104 - Zhao Liu
print(Tras la mudanza de Zhao Liu:, apartment_building)
# 4. Insertar elementos (agregar al final es relativamente eficiente, simulando una "ampliación")
# Supongamos que se permite añadir una habitación 106 al final
apartment_building.append(Habitación 106 - Sun Qi)
print(Después de añadir la habitación 106:, apartment_building)
# 5. Eliminar elementos
# Wang Wu, de la habitación 103, se ha mudado
# Método 1: marcar como vacante (eliminación lógica)
# apartment_building
# Método 2: eliminar el elemento, los elementos posteriores deben desplazarse hacia adelante (eliminación física, poco eficiente)
removed_tenant = apartment_building.pop(2) # Eliminar el elemento con índice 2
print(f{removed_tenant} se ha mudado.)
print(Tras la mudanza de Wang Wu:, apartment_building)
Salida:
寓楼住户情况: ['101室-张三', '102室-李四', '103室-王五', '104室-空置', '105室-空置'] 102室的住户是:102室-李四 赵六入住后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置'] 加盖106室后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置', '106室-孙七'] 103室-王五 已搬走。 王五搬走后: ['101室-张三', '102室-李四', '104室-赵六', '105室-空置', '106室-孙七']
Ventajas y desventajas
| Ventajas | Desventajas |
|---|---|
| Acceso aleatorio rápido: mediante el índice se puede acceder a cualquier elemento en tiempo constante. | Tamaño fijo: una vez creado un arreglo estático, su capacidad es difícil de cambiar. |
| Alta eficiencia de memoria: almacenamiento contiguo, no se necesita espacio adicional para almacenar las relaciones entre elementos. | Alto costo de inserción/eliminación: Insertar o eliminar elementos en el medio requiere desplazar muchos elementos posteriores para mantener la continuidad. |
Lista enlazada: el tren de búsqueda del tesoro de los datos
Cuando el tamaño fijo de los arrays y la ineficiencia de las inserciones y eliminaciones se convierten en un problema, aparecen las listas enlazadas. Una lista enlazada es como untren, donde cada vagón (nodo) lleva carga (datos) y se conecta con el siguiente vagón mediante un gancho (puntero).
Conceptos básicos y tipos
Cadanodode una lista enlazada contiene al menos dos partes:
- Campo de datos: almacena el valor real de los datos.
- Campo de puntero: almacena la dirección en memoria del siguiente nodo.

La figura anterior muestra una estructura delista enlazada simple. El puntero de cabecera apunta al primer nodo, elNextpuntero de cada nodo apunta al siguiente nodo, y el del último nodoNextapunta aNULL, lo que indica el final de la lista.
Tipos principales de listas enlazadas:
- Lista enlazada simple: el nodo solo apunta al siguiente nodo.
- Lista doblemente enlazada: el nodo apunta tanto al anterior como al siguiente, permitiendo recorrer en ambos sentidos.
- Lista circular enlazada: el nodo final apunta al nodo cabecera, formando un anillo.
Operaciones principales y ejemplos de código
Implementemos una lista enlazada simple.
Ejemplo
"""Definir la clase de nodo de la lista enlazada"""
def __init__(self, data):
self.data = data # Campo de datos
self.next = None # Campo de puntero, inicialmente apunta a vacío
class LinkedList:
"""Definir la clase de lista enlazada simple"""
def __init__(self):
self.head = None # Puntero de cabecera de la lista
def append(self, data):
"""Agregar un nodo al final de la lista enlazada"""
new_node = ListNode(data)
if not self.head: # Si la lista está vacía, el nuevo nodo se convierte en el nodo cabecera
self.head = new_node
return
last_node = self.head
while last_node.next: # Recorrer hasta el último nodo
last_node = last_node.next
last_node.next = new_node # Colgar el nuevo nodo al final
def prepend(self, data):
"""Agregar un nodo al inicio de la lista enlazada"""
new_node = ListNode(data)
new_node.next = self.head
self.head = new_node
def delete(self, key):
"""Eliminar el primer nodo cuyo valor sea key"""
current_node = self.head
# Si lo que se va a eliminar es el nodo cabecera
if current_node and current_node.data == key:
self.head = current_node.next
current_node = None
return
prev_node = None
# Recorrer buscando el nodo a eliminar
while current_node and current_node.data != key:
prev_node = current_node
current_node = current_node.next
if current_node is None: # No se encontró
return
# Una vez encontrado, omitir el nodo para reconectar
prev_node.next = current_node.next
current_node = None
def print_list(self):
"""Imprimir todos los elementos de la lista enlazada"""
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("NULL")
# Probar la lista enlazada
print("=== Demostración de operaciones con lista enlazada simple ===")
train = LinkedList()
train.append("Vagón 1 - Carbón")
train.append("Vagón 2 - Madera")
train.prepend("Locomotora") # Agregar al inicio
train.append("Vagón 3 - Acero")
print("Tren inicial: ")
train.print_list() # Salida: Locomotora -> Vagón 1 - Carbón -> Vagón 2 - Madera -> Vagón 3 - Acero -> NULL
train.delete("Vagón 2 - Madera")
print("Después de descargar la madera: ")
train.print_list() # Salida: Locomotora -> Vagón 1 - Carbón -> Vagón 3 - Acero -> NULL
Salida:
=== 单向链表操作演示 === 初始列车: 车头 -> 车厢1-煤炭 -> 车厢2-木材 -> 车厢3-钢材 -> NULL 卸下木材后: 车头 -> 车厢1-煤炭 -> 车厢3-钢材 -> NULL
Ventajas y desventajas
| Ventajas | Desventajas |
|---|---|
| Tamaño dinámico: no requiere asignar espacio fijo de antemano; puede crecer y reducirse con flexibilidad. | Sobrecarga de memoria: cada nodo necesita espacio adicional para almacenar punteros. |
| Inserción/eliminación eficiente: cuando se conoce la posición del nodo, solo hay que modificar punteros, sin necesidad de mover muchos elementos. | Acceso secuencial: no se puede acceder directamente por índice como en un array; hay que recorrer desde el principio. |
| Poco amigable con la caché: los nodos se almacenan de forma dispersa en memoria, lo que dificulta la precarga de la caché de la CPU. |
Pila: el apilamiento de platos de los datos
Una pila es unaestructura de datos LIFO (último en entrar, primero en salir), como los platos apilados en un restaurante: siempre tomas el de arriba (el último que se puso).
Conceptos básicos y operaciones
Una pila solo permite en un extremo (llamadocima de la pila) realizar la inserción (push/apilar) y la eliminación (pop/desapilar). El otro extremo se llamafondo de la pila。
Operaciones principales:
- push(data): empuja un dato a la cima de la pila.
- pop(): saca y devuelve el elemento de la cima.
- peek() / top(): observa el elemento de la cima sin sacarlo.
- is_empty(): comprueba si la pila está vacía.

Escenarios de aplicación y ejemplos de código
La pila tiene aplicaciones muy amplias en ciencias de la computación, por ejemplo: pila de llamadas a funciones, avanzar/retroceder en el navegador, evaluación de expresiones, comprobación de paréntesis, etc.
Ejemplo
"""Implementar una pila usando una lista"""
def __init__(self):
self.items = []
def push(self, item):
"""Push (apilar)"""
self.items.append(item) # El final de la lista actúa como cima de la pila
def pop(self):
"""Pop (desapilar); si la pila está vacía, devuelve None"""
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
"""Ver el elemento de la cima"""
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
"""Comprobar si la pila está vacía"""
return len(self.items) == 0
def size(self):
"""Devolver el tamaño de la pila"""
return len(self.items)
# Ejemplo de uso: comprobación de paréntesis balanceados
def is_balanced_parentheses(expression):
"""
Comprueba si los paréntesis de una expresión coinciden correctamente.
Por ejemplo: (()) está balanceado, (() no lo está.
"""
stack = Stack()
# Mapa de coincidencia de paréntesis
matching_bracket = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in '([{': # Si es un paréntesis de apertura, se apila
stack.push(char)
elif char in ')]}': # Si es un paréntesis de cierre
if stack.is_empty():
return False # La pila está vacía, hay demasiados paréntesis de cierre
top_char = stack.pop()
if matching_bracket[char] != top_char: # Comprobar si coinciden
return False
# Al terminar el bucle, la pila debe estar vacía
return stack.is_empty()
# Probar la pila y la comprobación de paréntesis
print("\n"=== Demostración de pila y paréntesis balanceados ===")
plate_stack = Stack()
plate_stack.push("Plato 1")
plate_stack.push("Plato 2")
plate_stack.push("Plato 3")
print(f"Sacar el plato superior: {plate_stack.pop()}") # Salida: Plato 3
print(f"Ahora el plato superior es: {plate_stack.peek()}") # Salida: Plato 2
# Probar la comprobación de paréntesis
test_cases = ["((1+2)*3)", "({[ ]})", "((())", ")( )"]
for test in test_cases:
result = "balanceados" if is_balanced_parentheses(test) else "no balanceados"
print(f"La expresión '{test}' tiene los paréntesis {result}.")
Salida:
=== 栈与括号匹配演示 ===
取出最上面的盘子: 盘子3
现在最上面的盘子是: 盘子2
表达式 '((1+2)*3)' 的括号是 平衡 的。
表达式 '({[ ]})' 的括号是 平衡 的。
表达式 '((())' 的括号是 不平衡 的。
表达式 ')( )' 的括号是 不平衡 的。
Cola: el pasillo de espera de los datos
Una cola es unaestructura de datos FIFO (primero en entrar, primero en salir), como en cualquier lugar de la vida donde hay que hacer cola (por ejemplo, la caja de un supermercado): el que llega primero recibe el servicio primero.
Conceptos básicos y operaciones
Una cola permite en un extremo (llamadofinal de la cola) realizar la inserción (enqueue/encolar), y en el otro extremo (llamadofrente de la cola) realizar la eliminación (dequeue/desencolar).
Operaciones principales:
- enqueue(data): agrega datos al final de la cola.
- dequeue(): elimina y devuelve datos desde el frente de la cola.
- front() / peek(): observa los datos del frente sin eliminarlos.
- is_empty(): comprueba si la cola está vacía.
Escenarios de aplicación y ejemplos de código
La cola se usa comúnmente en escenarios donde se deben procesar tareas en orden, como: cola de trabajos de impresión, cola de mensajes, búsqueda en anchura, etc.
Ejemplo
class Queue:
"""Implementar una cola usando collections.deque"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""Enqueue (encolar)"""
self.items.append(item) # Agregar desde la derecha (final de la cola)
def dequeue(self):
"""Dequeue (desencolar); si la cola está vacía, devuelve None"""
if not self.is_empty():
return self.items.popleft() # Eliminar desde la izquierda (frente de la cola)
return None
def front(self):
"""Ver el elemento del frente"""
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
"""Comprobar si la cola está vacía"""
return len(self.items) == 0
def size(self):
"""Devolver el tamaño de la cola"""
return len(self.items)
# Ejemplo de uso: simular trabajos de impresión
print("\n"=== Simulación de cola y trabajos de impresión ===")
printer_queue = Queue()
# Simular la llegada de tres trabajos de impresión
tasks = ["Currículum de Alice.pdf", "Informe de Bob.doc", "Gráfico de Charlie.png"]
for task in tasks:
printer_queue.enqueue(task)
print(f"La tarea '{task}' se ha añadido a la cola de impresión.")
# Procesar los trabajos de impresión
print("\n"Comenzando a imprimir...")
while not printer_queue.is_empty():
current_task = printer_queue.dequeue()
print(f"Imprimiendo: {current_task}")
# Simular el tiempo de impresión
print("Todos los trabajos de impresión se han completado.")
Salida:
=== 队列与打印任务模拟 === 任务 'Alice的简历.pdf' 已加入打印队列。 任务 'Bob的报告.doc' 已加入打印队列。 任务 'Charlie的图表.png' 已加入打印队列。 开始打印... 正在打印: Alice的简历.pdf 正在打印: Bob的报告.doc 正在打印: Charlie的图表.png 所有打印任务已完成。
Resumen y comparación
Hemos aprendido cuatro estructuras de datos lineales básicas. La siguiente tabla te ayuda a repasar y comparar rápidamente sus características principales:
| Característica | Array | Lista enlazada | pila | Cola |
|---|---|---|---|---|
| Método de almacenamiento | Memoria contigua | Memoria dispersa, conectada mediante punteros | Basada en un array o una lista enlazada | Basada en un array o una lista enlazada |
| Forma de acceso | Acceso aleatorio (mediante índice) | Acceso secuencial (debe recorrer) | Solo la cima de la pila (LIFO) | Solo el frente de la cola (FIFO) |
| Eficiencia de inserción/eliminación | Rápido al final, lento en el medio/al inicio (requiere mover elementos) | Rápido cuando se conoce la posición (solo hay que cambiar punteros) | Operaciones en la cima de la pila, O(1) | Encolar al final, desencolar al frente, O(1) |
| Tamaño | Fijo (arreglo estático) | Dinámico | Dinámico | Dinámico |
| Aplicaciones principales | Búsqueda rápida, colección fija | Inserción/eliminación frecuente, tamaño incierto | Llamadas a funciones, retroceso (backtracking), coincidencia de paréntesis | Programación de tareas, buffer, BFS |
¿Cómo elegir?
- NecesitaAcceso aleatorio rápidoy se conoce el volumen de datos, elijaArreglo (array)。
- NecesitaInsertar o eliminar con frecuencia en cualquier posiciónelementos, y cuando el volumen de datos varía mucho, elijaLista enlazada。
- Necesita implementar"Deshacer"función oProcesamiento inversoen orden, considerepila。
- Necesita seguir"Primero en llegar, primero en ser atendido"el orden de procesamiento de tareas, useCola。