Listas encadenadas
Tiempo de lectura: 2 minutos
Operaciones de listas encadenadas. Una lista encadenadas se compone de una serie de registros en memoria, llamados nodos, que se referencian unos a otros utilizando un puntero.
Listas
Una lista encadenadas se compone de una serie de registros en memoria, llamados nodos, que se referencian unos a otros utilizando un puntero. De esta manera tenemos una referencia al inicio de la lista y luego punteros desde el nodo actual al siguiente. El último enlace apunta a nulo.
Nodos
Para trabajar con listas necesitamos un nodo. Un nodo contiene los datos y un puntero al siguiente nodo. Utilizaremos un puntero para referenciar el inicio de la lista. Si el puntero head tiene el valor nulo, la lista está vacía.
Luego definimos un puntero para ir recorriendo la listas (current):
type Node struct {
name string
next *Node
}
type List struct {
head *Node
}
current *Node Operaciones con la lista
A partir de aquí podemos definir diferentes operaciones para trabajar con la lista encadenada en memoria:
- añadir un nodo al final
- añadir un nodo en la posición actual
- añadir un nodo antes del nodo actual
- borrar un nodo
- borrar la lista
Hemos de tener presente que, para no perder el direccionamiento de la lista, se deben seguir los pasos de encadenamiento de forma ordenada. Si perdemos un puntero, perdemos los datos de la lista.
Añadir un nodo al final
Añadimos un nuevo nodo al final de la lista:
func (list *List) insertAtEnd(data string) {
// inicializa nuevo nodo
newNode := &Node{data: data, next: nil}
// si la lsta está vacía, lo encadena
if list.head == nil {
list.head = newNode
return
}
// busca el último nodo
current = list.head
for current.next != nil {
current = current.next
}
// encadena
current.next = newNode
} Añadir en la posición actual
Recorremos la lista hasta encontrar el valor deseado y realizamos la operación de inserción:
- apuntamos el nuevo nodo al valor del puntero actual
- apuntamos el valor del nodo actual, al nuevo nodo
func (list *List) insertAfter(afterValue, data string) {
// inicializa nuevo nodo
newNode := &Node{data: data, next: nil}
// apuntamos el current
current = list.head
// recorremos la lista buscan el valor indicado
for current != nil {
if current.data == afterValue {
newNode.next = current.next
current.next = newNode
return
}
current = current.next
}
// no se ha encontrado
fmt.Printf("No se encuentra el nodo %d\n", afterValue)
} Añadir delante del nodo actual
Esta operación es un poco más complicada porque hemos de comprobar si insertamos en el primer nodo o en uno posterior. En el primer caso, insertamos y apuntamos a la cabecera de la lista. En el segundo caso vamos buscando el nodo desde el nodo anterior (current.next.data) para tener la referencia del nodo anterior al localizado.
Una vez localizado, creamos un nodo cuyo siguiente apunta al mismo valor que el puntero del nodo actual y luego el nodo actual lo apuntamos al nuevo nodo.
func (list *List) insertBefore(beforeValue, data string) {
// Si está vacía, salimos
if list.head == nil {
return
}
// Si es el primer nodo de la lista, apuntamos
if list.head.data == beforeValue {
newNode := &Node{data: data, next: list.head}
list.head = newNode
return
}
current = list.head
for current.next != nil {
if current.next.data == beforeValue {
newNode := &Node{data: data, next: current.next}
current.next = newNode
return
}
current = current.next
}
fmt.Printf("No se encuentra el nodo %d\n", beforeValue)
} Borrar un nodo
Borrar significa dejar de apuntar al nodo que se quiere borrar. Si queremos borrar el último nodo de una lista:
func (list *List) deleteLast() {
// comprueba que no esté vacía
if list.head == nil {
fmt.Printf("Lista vacía\n")
return
}
// Si es el único nodo, se pierde
if list.head.next == nil {
list.head = nil
fmt.Printf("Único nodo borrado. Lista vacía\n")
return
}
// buscamos el último nodo, estando posicionados uno antes
current = list.head
for current.next.next != nil {
current = current.next
}
current.next = nil
fmt.Printf("Último nodo borrado\n")
} Otras operaciones
Todo el proceso anterior se ejecuta en memoria, pero si queremos conservar la lista tendremos que guardarla en un archivo. Definiremos las operaciones siguientes:
- guardar la lista en un archivo
- recuperar la lista de un archivo
Para borrar la lista bastará con poner el puntero de cabecera en nulo.
