Manual C

Capítulo

32

Listas, pilas
y colas en C
  Contenido
• Listas enlazadas
• Clasificación de listas enlazadas
• Operaciones en listas enlazadas
• Inserción de un elemento en una lista
• Búsqueda de un elemento de una lista
• Borrado de un nodo en una lista
• Concepto de pila
• El tipo pila implementado con arreglos
• El tipo pila implementado como una lista enlazada
•Concepto de cola
• El tipo cola implementado con arreglos (arrays) circulares
• El tipo cola implementado con una lista enlazada
• Resumen
• Ejercicios
• Problemas

Introducción
En este capítulo se estudian estructuras de datos dinámicas. Al contrario que las estructuras de datos
estáticas (arrays —listas, vectores y tablas— y estructuras) en las que el tamaño en memoria se establecedurante la compilación y permanece inalterable durante la ejecución del programa, las estructuras de datos dinámicas crecen y se contraen a medida que se ejecuta el programa.
Una lista enlazada (ligada o encadenada, linked list) es una colección de elementos (denominados
nodos) dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente elemento por
un “enlace” o“referencia”. En el capítulo se desarrollan algoritmos para insertar, buscar y borrar elementos en las listas enlazadas.

964

Capítulo 32

Listas, pilas y colas en C

Una pila es una estructura de datos que almacena y recupera sus elementos atendiendo a un estricto orden. Las pilas se conocen también como estructuras LIFO (Last-in, first-out, último en entrarprimero en salir), todas las inserciones yretirada de elementos se realizan por un mismo extremo
denominado cima de la pila. Las pilas se utilizan frecuentemente en programas y en la vida diaria.
Las colas se conocen como estructuras FIFO (First-in, First-out, primero en entrar-primero en salir), debido a la forma y orden de inserción y de extracción de elementos de la cola. Las colas tienen
numerosas aplicaciones en el mundo de lacomputación: colas de mensajes, colas de tareas a realizar
por una impresora, colas de prioridades.

Conceptos clave
• Asignación de memoria
• Eliminar un nodo en una lista enlazada
• Estructura FIFO
• Lista enlazada
• Memoria libre

• Puntero nulo
• Punteros
• Recorrido de una lista
• Referencia
• Variables puntero

Listas enlazadas
Una lista enlazada es unacolección o secuencia de elementos dispuestos uno detrás de otro, en la que
cada elemento se conecta al siguiente por un “enlace” o “puntero”. La idea básica consiste en construir una lista cuyos elementos, llamados nodos, se componen de dos partes o campos: la primera
c
­ ontiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Dato, TipoElemento, Info, etc.) y la segundaparte o campo es un puntero (denominado enlace o sgte) que apunta al siguiente elemento de la lista.
Nodo

puntero

Nodo

puntero

Nodo

Figura 32.1 Lista enlazada (representación simple).
La representación gráfica más extendida es aquella que utiliza una caja (un rectángulo) con dos
secciones en su interior. En la primera sección se escribe el elemento o valor del dato, y en lasegunda, el enlace o puntero mediante una flecha que sale de la caja y apunta al nodo siguiente.
e1

e2

e3

...

en

e1, e2, ... en son valores del tipo TipoElemento

Figura 32.2 Lista enlazada (representación gráfica típica).

Estructura de una lista
Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes (campos), un puntero al siguienteelemento de la lista y un valor, que puede ser de cualquier tipo.
Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre dos
nodos; ello indica que el enlace tiene la dirección en memoria del siguiente nodo. En la figura 32.2

Clasificación de las listas enlazadas

en

en

en

NULL

Figura 32.3 Diferentes representaciones gráficas del nodo...