Listas enlazadas

Listas Enlazadas
Además de los arrays, otra de las estructuras de datos muy utilizada es la lista enlazada. Esta estructura implica cuatro conceptos: clase auto-refenciada, nodo, campo de enlace y enlace.

Clase auto-referenciada: una clase con al menos un campo cuyo tipo de referencia es el nombre de la clase:
class Employee {
private int empno;
private String name;
privatedouble salary;

public Employee next;

// Other members

}
Employee es una clase auto-referenciada porque su campo next tiene el tipo Employee.

Nodo: un objeto creado desde una clase auto-referenciada.
Campo de enlace: un campo cuyo tipo de referencia es el nombre de la clase. En el fragmento de código anterior, next es un campo de enlace. Por el contrario, empno, name, y salaryson campos no de enlace.
Enlace: la referencia a un campo de enlace. En el fragmento de código anterior, la referencia next a un nodo Employee es un enlace.
Los cuatro conceptos de arriba nos llevan a la siguiente definición: una lista enlazada es una secuencia de nodos que se interconectan mediante sus campos de enlace. En ciencia de la computación se utiliza una notación especial parailustrar las listas enlazadas. En la siguiente imagen aparece una variante de esta notación que utilizaré a lo largo de esta sección:

La figura anterior presenta tres nodos: A, B y C. Cada nodo se divide en áreas de contenido (en naranja) y una o más áreas de enlace (en verde). Las áreas de contenido representan todos los campos que no son enlaces, y cada área de enlace representa un campo deenlace. Las áreas de enlace de A y C tienen unas flechas para indicar que referencian a otro nodo del mismo tipo (o subtipo). El único área de enlace de B incorpora una X para indicar una referencia nula. En otras palabras, B no está conectado a ningún otro nodo.

Aunque se pueden crear muchos tipos de listas enlazadas, las tres variantes más populares son la lista de enlace simple, la listadoblemente enlazada y la lista enlazada circular. Exploremos esas variantes, empezando con la lista enlazada.

Lista de Enlace Simple
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodocontiene null para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera. La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:

Un algoritmo común de las listas de enlace simple es la inserción de nodos. Estealgoritmo está implicado de alguna forma porue tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe. Antes de estudiar cada caso consideremos el siguiente pseudocódigo:

DECLARE CLASS Node
DECLARE STRINGname
DECLARE Node next
END DECLARE

DECLARE Node top = NULL
Este pseudocódigo declara una clase auto-referenciada llamada Node con un campo no de enlace llamado name y un campo de enlace llamado next. También declara una variable de referencia top (del tipo Node) que contiene una referencia al primer Node de una lista de enlace simple. Como la lista todavía no existe, el valor inicial detop es NULL. Cada uno de los siguientes cuatro casos asume las declaraciones de Node y top:

La lista de enlace simple no existe::
Este es el caso más simple. Se crea un Node, se asigna su referencia a top, se inicializa su campo no de enlace, y se asigna NULL a su campo de enlace. El siguiente pseudocódigo realiza estas tareas:
top = NEW Node

top.name = "A"
top.next = NULL
En la...