= '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:

  1. Arreglo: como una fila de taquillas numeradas, cada una con una posición fija
  2. Lista enlazada: como una cadena de personas tomadas de la mano, donde cada una solo recuerda a la persona anterior y a la siguiente
  3. pila: como una pila de platos, solo se puede tomar o colocar desde la parte superior
  4. 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 desde00. 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

# 1. Crear array
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:

  1. Campo de datos: almacena el valor real de los datos.
  2. 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

class ListNode:
    """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

class Stack:
    """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

from collections import deque  # Usar deque de Python, que proporciona operaciones eficientes en ambos extremos

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。
Otras extensiones