7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 1/13

Jairo Armando Riaño Herrera 1

LISTAS ENLAZADAS

Estructura de datos dinámica que consiste en una secuenciade nodos en los que se guardan datos de diferentes tipos yuna o dos referencias al nodo siguiente o anterior(apuntador). Se diferencia de los vectores en que el ordende los elementos enlazados puede ser diferente al de

almacenamiento en memoria o en disco, permitiendo queel orden de recorrido sea diferente al de almacenamiento

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 2/13

Jairo Armando Riaño Herrera 2

LISTAS ENLAZADAS

En una lista enlazada es posible insertar y eliminar nodos encualquier orden de la secuencia de nodos:

● Al nicio de la lista

● Al !inal de la lista

● En un nodo intermedio

En una lista no es posible el acceso aleatorio, sino que losnodos se deben recorrer en un orden secuencial a partir deun nodo o referencia conocida a partir de la cual se realizantodas las operaciones

 

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 3/13

Jairo Armando Riaño Herrera 3

TIPOS DE LISTAS ENLAZADAS

●

Sencillas● "obles

● #irculares Sencillas

●

#irculares "obles 

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 4/13

Jairo Armando Riaño Herrera 4

LISTAS ENLAZADAS

Eliana $aime %oberto &ario $enny#amilo

#abeza#abeza

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 5/13

Jairo Armando Riaño Herrera 5

DIAGRAMA DE CLASES

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 6/13

Jairo Armando Riaño Herrera 6

LISTAS DOBLES

Estructura de datos que implementa un par de referencias,una al nodo siguiente y otra al nodo anterior, de manera quese puede recorrer la lista 'acia adelante y 'acia atrás.

Eliana $aime %oberto &ario

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 7/13

Jairo Armando Riaño Herrera 7

LISTAS DOBLES

a clase que gestiona la lista mantiene una referencia alprimer elemento, y con el obetivo de facilitar el recorrido'acia atrás, se puede de igual manera mantener unareferencia al *ltimo.

Eliana $aime %oberto &ario

#abeza +ltimo

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 8/13

Jairo Armando Riaño Herrera 8

LISTAS DOBLES

nsertar rimer Elemento

nsertar al nicio

nsertar al !inal

Eliana&ario

+ltimo+ltimo#abeza#abeza

Eliana

+ltimo+ltimo#abeza

&ario Eliana %oberto

#abeza#abeza +ltimo+ltimo

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 9/13

Jairo Armando Riaño Herrera 9

LISTAS DOBLES

nsertar -rdenado$aime %obertoEliana eresa

&ario

nuevo

anterior actual/ 0

12

$aime %obertoEliana eresa&ario

ultimocabeza

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 10/13

Jairo Armando Riaño Herrera 10

LISTAS DOBLES

Eliminar 3odo *nico

&ario

ultimocabeza

ultimocabeza

null null

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 11/13

Jairo Armando Riaño Herrera 11

LISTAS DOBLES

Eliminar #abeza$aime %obertoEliana eresa&ario

ultimocabeza

ultimocabeza

$aime %oberto eresa&ario

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 12/13

Jairo Armando Riaño Herrera 12

LISTAS DOBLES

Eliminar 4ltimo$aime %obertoEliana eresa&ario

ultimocabeza

ultimo

$aime %obertoEliana &ario

cabeza

7/23/2019 ListasEnlazadas (1)

http://slidepdf.com/reader/full/listasenlazadas-1 13/13

Jairo Armando Riaño Herrera 13

LISTAS DOBLES

Eliminar 3odo nterior

$aime %obertoEliana eresa&ario

ultimocabeza anterior actual

$aime %obertoEliana eresa&ario

$aime %obertoEliana eresa

cabeza ultimo