Clase teorica

Estructuras de datos
Clase teórica 3
Contenido
• Listas simple y doblemente enlazadas

Lista enlazada
Una lista enlazada (o ligada) es una estructura de datos
que permite almacenar elementospero, a diferencia de
los arreglos, no necesariamente en posiciones
consecutivas de memoria (ni siquiera deben estar “en
orden”).
Arreglo:

Lista enlazada:

Material elaborado por: JuliánMoreno

Lista enlazada
En una lista, cada elemento se encuentra “contenido” dentro
de un nodo el cual generalmente contiene, además del
elemento, un apuntador o referencia a otro nodo (o a otros
dos)y el índice de dicho elemento dentro de la lista.
Siendo así, la lista como tal no contiene mayor cosa,
generalmente solo la referencia a ciertos nodos de la lista
(normalmente primero y último) yel tamaño de la misma.
Dependiendo de si cada nodo apunta solamente al siguiente
en la lista diremos que esta es simplemente enlazada, o si
apunta tanto al siguiente como al anterior diremos quees
doblemente enlazada. La diferencia entre una y otra son las
operaciones que permiten (en una doblemente enlazada por
ejemplo se puede ir de atrás hacia adelante, mientras que en
la simple no)Enlace

Contenedor

Facultad de Minas, Departamento de Ciencias de la Computación y la Decisión

Lista enlazada
Lista simplemente enlazada:
Lista

Nodo

Nodo

Nodo

first = 0x05
last= 0x10
size = 3

index = 0
next = 0x07

index = 1
next = 0x10

index = 2
next = null

0x04

0x05

0x06

0x07

0x08

0x09

0x10

Lista doblemente enlazada:
Lista

NodoNodo

Nodo

first = 0x05
last = 0x10
size = 3

index = 0
next = 0x07
prev = null

index = 1
next = 0x10
prev = 0x05

index = 2
next = null
prev = 0x07

0x04

0x05

0x06

0x070x08

0x09

0x10

Búsqueda en una lista enlazada

Búsqueda en una lista enlazada

Ya que conocemos la “arquitectura” de una lista enlazada,
pasemos a analizar cada una de las...