ESTRUCTURA Y ORGANIZACION DE DATOS

CONCEPTO DE LISTAS

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.