Son tipos dinámicos que se construyen con nodos.
Suele utilizarse para nombrar a la enumeración que se lleva a cabo con un cierto propósito. Las listas se realizan en forma de columna y pueden completarse con ingredientes, cantidades, nombres de personas o cualquier otro dato, según el fin en cuestión.
Existen diferentes tipos de listas enlazadas:
Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Operaciones sobre listas enlazadas
Cuando se manipulan listas enlazadas, hay que tener cuidado con no usar valores que hayamos invalidado en asignaciones anteriores. Esto hace que los algoritmos de insertar y borrar nodos en las listas sean algo especiales.
Listas Simples Enlazadas
Nuestra estructura de datos tendrá dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, ó nulo para la lista vacía.
record Node {
data // El dato almacenado en el nodo
next // Una referencia al nodo siguiente, nulo para el último nodo
}
record List {
Node PrimerNodo // Apunta al primer nodo de la lista; nulo para la lista vacía
}
El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.node := list.PrimerNodo
while node not null {
node := node.next
}
El siguiente código inserta un elemento a continuación de otro en una lista simple. El diagrama muestra como funciona.
function insertAfter(Node node, Node newNode) {
newNode.next := node.next
node.next := newNode
}
Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.function insertBeginning(List list, Node newNode) {
newNode.next := list.firstNode
list.firstNode := newNode
}
De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista. Ver diagrama.
function removeAfter(Node node) {
obsoleteNode := node.next
node.next := node.next.next
destroy obsoleteNode
}
function removeBeginning(List list) {
obsoleteNode := list.firstNode
list.firstNode := list.firstNode.next
destroy obsoleteNode
}
Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el último elemento de la lista. Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendríamos que recorrer la lista en orden hasta llegar a la cola y luego añadir la segunda lista.
