Scribd
Cargar
188 vistas15 páginas

Listas Doblemente Enlazadas en Java

Una lista doblemente enlazada consiste en nodos conectados que contienen campos para datos e índices hacia los nodos anterior y siguiente. Existen dos tipos: lineales donde los primero y último nodos apuntan a NULL, y circulares donde el primer nodo apunta al último y viceversa. Los nodos se pueden insertar o eliminar manipulando los índices.

Cargado por

Joseph Pop
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
188 vistas15 páginas

Listas Doblemente Enlazadas en Java

Una lista doblemente enlazada consiste en nodos conectados que contienen campos para datos e índices hacia los nodos anterior y siguiente. Existen dos tipos: lineales donde los primero y último nodos apuntan a NULL, y circulares donde el primer nodo apunta al último y viceversa. Los nodos se pueden insertar o eliminar manipulando los índices.

Cargado por

Joseph Pop
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

LISTAS DOBLEMENTE ENLAZADAS

Ing. Susana Beltrán


Estructura de datos
UMG
Una lista doblemente enlazada es una
colección de elementos llamados nodos.-

Un nodo tiene tres campos: un campo


izquierda, un campo dato y un campo
derecha. Los campos izquierda y derecha
son apuntadores a los nodos ubicados en
el lado izquierdo y el derecho de cada
nodo.-
Existen dos tipos de listas doblemente
ligadas:

Listas dobles lineales. En este tipo de


lista doble, tanto el puntero izquierdo del
primer nodo como el derecho del último
nodo apuntan a NULL.

51 99 83

izq. dato der. izq. dato der. izq. dato der.


Listas dobles circulares. En este tipo de
lista doble, el puntero izquierdo del primer
nodo apunta al último nodo de la lista, y el
puntero derecho del último nodo apunta al
primer nodo de la lista.

51 99 83

izq. dato der. izq. dato der. izq. dato der.


A continuación mostraremos algunos
algoritmos sobre listas enlazadas.

Llamaremos li al puntero izquierdo y ld al


puntero derecho, también usaremos el
apuntador top para hacer referencia al
primer nodo en la lista, y p para
referenciar al nodo presente.
Procedimiento de crear el primer nodo de
una lista doblemente enlazada

1. p=new nodo
2. p->dato= INFO
3. p->sig = NULL
4. p->ant = NULL
5. TOP = p
6. FIN = p
Procedimiento para insertar un nodo
al comienzo

1. p = new nodo
2. p->dato= INFO
3. p->sig = TOP
4. p->ant = NULL
5. TOP->ant = p
6. TOP = p
Algoritmo para insertar
Antes de ‘x’ Después de ‘x’
p = top p = top
lee(x) lee(x)
repite repite
si p->dato = x entonces si p->dato = x entonces
q = new nodo q = new nodo
leer(q->dato) leer(q->dato)
si p = top entonces q->sig = p->sig
top = q q->ant = p
q->sig = p p->sig->ant = q
q->ant = p->ant p->sig = q
p->sig->ant = q p = top
p->ant = q en caso contrario
p = top p = p->sig
en caso contrario hasta p=top
p = p->sig
hasta p = top
Algoritmo para borrar un nodo
p = top
lee(valor_a_borrar)
repite
si p->dato = valor_a_borrar entonces
p->sig->ant = p->ant
p->ant->sig = p->sig
si p = top entonces
si p->sig = p->ant entonces
top = NULL
en caso contrario
top = top->sig
dispose(p)
p = top
en caso contrario
p = p->sig
hasta p = top

También podría gustarte