Listas EnlazadasCurso: Análisis y Diseño de Algoritmos
Armando Arce Orozco, M.Sc.Escuela de Computación
Setiembre 2020
1
Introducción
Una serie de estructuras de datos permiten implementaroperaciones sobre listas de forma más eficiente que las listasbasadas en arreglos
• Listas enlazadas simples• Listas doblemente enlazadas• Listas con saltos
2
Listas enlazadas simples
3
Listas enlazadas simples
Otro método de implementar listas se basa en utilizar enlacesentre elementos.
• En este caso la lista se compone de una serie de objetosque se encuentran enlazados entre ellos.
• A cada uno de estos objetos individuales se les conocecomo nodos de enlace.
4
Nodo de enlace
El nodo de enlace se compone de dos elementos: el enlace alsiguiente objeto, y el dato del elemento que almacena.
function node(val,lnk)return {
data = val,link = lnk
}end
5
Lista enlazada simple
La lista basada en enlaces mantiene una referencia al nodoinicial de lista.
6
Operaciones en lista enlazada
function linked_list()local head = node(nil,nil)local len = 0
end
function linked_list.size()return len
end
function LinkedList.empty()return (len == 0)
end
7
Operaciones en lista enlazada (cont.)
function linked_list.front()if (len==0) then
error("list empty")endreturn head.link.data
end
8
Agregar y eliminar al inicio de la lista
function linked_list.push_front(val)head.link = node(val,head.link)len = len + 1
end
function linked_list.pop_front(val)if (len==0) then
error("list empty")endlocal tmp = head.link.datahead.link = head.link.linklen = len - 1return tmp
end 9
Manejo de iteradores
function linked_list.begin()return (linked_list_itr(linked_list,head))
end
function linked_list.end()return (linked_list_itr(linked_list,nil))
end
10
Manejo de iteradores
function linked_list_itr(lnk)local pointer = lnk
end
function linked_list_itr.pointer()return pointer
end
function linked_list_itr.equals(itr)return (pointer==itr.pointer())
end
11
Manejo de iteradores
function linked_list_itr.get()return pointer.data
end
function linked_list_itr.next()if (pointer == nil) then
error('invalid iterator')endpointer = pointer.link
end
12
Insertar mediante iteradores
function linked_list.insert_after(itr,val)if (itr.pointer() == nil) then
error('invalid iterator')enditr.pointer().link = node(val,itr.pointer().link)len = len + 1
end
13
Insertar mediante iteradores
14
Borrar mediante iteradores
function linked_list.erase_after(itr,val)if (itr.pointer() == nil) then
error('iterator out of range')endlocal tmp = itr.pointer().dataitr.pointer().link = itr.pointer().link.linklen = len - 1return tmp
end
15
Borrar mediante iteradores
16
Listas doblemente enlazadas
17
Listas enlazadas dobles
18
Insertar en lista enlazada doble
19
Borrar en lista enlazada doble
20
Listas con saltos
21
Listas con saltos
22
Inserción en lista con saltos
23
Referencia bibliográfica
• Clifford A. Shaffer. Data Structures and Algorithm Analysis inC++, Third Edition, Dover Publications, 2011. Cap. 4
24