Análisis e implementación de la estructura de datos de Linked List en Go
Una lista enlazada proporciona una estructura de datos similar a una matriz, pero con la gran ventaja de que insertar un elemento en el medio de la lista es muy económico, en comparación con hacerlo en una matriz, donde necesitamos desplazar todos los elementos después de la posición actual. .
Mientras que los arreglos mantienen todos los elementos en el mismo bloque de memoria, uno al lado del otro, las listas enlazadas pueden contener elementos esparcidos por la memoria, almacenando un puntero al siguiente elemento.
Una desventaja sobre las matrices, por otro lado, es que si queremos elegir un elemento en el medio de la lista, no sabemos su dirección, por lo que debemos comenzar desde el principio de la lista e iterar en la lista hasta lo encontramos.
Implementación
Una lista vinculada proporcionará estos métodos:
Append(t)
agrega un elemento t al final de la lista vinculadaInsert(i, t)
agrega un elemento t en la posición iRemoveAt(i)
elimina un nodo en la posición iIndexOf()
devuelve la posición del artículo tIsEmpty()
devuelve verdadero si la lista está vacíaSize()
devuelve el tamaño de la lista vinculadaString()
devuelve una representación de cadena de la listaHead()
devuelve el primer nodo, por lo que podemos iterar en él
Voy a crear unItemLinkedList
tipo genérico, seguro para la concurrencia, que puede generar listas enlazadas que contengan cualquier tipo usandogenny
, para crear una implementación de lista vinculada específica de tipo, encapsulando la estructura de datos específica de valor real que contiene los datos.
// Package linkedlist creates a ItemLinkedList data structure for the Item type
package linkedlist
import (
“fmt”
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Item the type of the linked list
type Item generic.Type
// Node a single node that composes the list
type Node struct {
content Item
next *Node
}
// ItemLinkedList the linked list of Items
type ItemLinkedList struct {
head *Node
size int
lock sync.RWMutex
}
// Append adds an Item to the end of the linked list
func (ll *ItemLinkedList) Append(t Item) {
ll.lock.Lock()
node := Node{t, nil}
if ll.head == nil {
ll.head = &node
} else {
last := ll.head
for {
if last.next == nil {
break
}
last = last.next
}
last.next = &node
}
ll.size++
ll.lock.Unlock()
}
// Insert adds an Item at position i
func (ll *ItemLinkedList) Insert(i int, t Item) error {
ll.lock.Lock()
defer ll.lock.Unlock()
if i < 0 || i > ll.size {
return fmt.Errorf(“Index out of bounds”)
}
addNode := Node{t, nil}
if i == 0 {
addNode.next = ll.head
ll.head = &addNode
return nil
}
node := ll.head
j := 0
for j < i-2 {
j++
node = node.next
}
addNode.next = node.next
node.next = &addNode
ll.size++
return nil
}
// RemoveAt removes a node at position i
func (ll ItemLinkedList) RemoveAt(i int) (Item, error) {
ll.lock.Lock()
defer ll.lock.Unlock()
if i < 0 || i > ll.size {
return nil, fmt.Errorf(“Index out of bounds”)
}
node := ll.head
j := 0
for j < i-1 {
j++
node = node.next
}
remove := node.next
node.next = remove.next
ll.size–
return &remove.content, nil
}
// IndexOf returns the position of the Item t
func (ll *ItemLinkedList) IndexOf(t Item) int {
ll.lock.RLock()
defer ll.lock.RUnlock()
node := ll.head
j := 0
for {
if node.content == t {
return j
}
if node.next == nil {
return -1
}
node = node.next
j++
}
}
// IsEmpty returns true if the list is empty
func (ll *ItemLinkedList) IsEmpty() bool {
ll.lock.RLock()
defer ll.lock.RUnlock()
if ll.head == nil {
return true
}
return false
}
// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
ll.lock.RLock()
defer ll.lock.RUnlock()
size := 1
last := ll.head
for {
if last == nil || last.next == nil {
break
}
last = last.next
size++
}
return size
}
// Insert adds an Item at position i
func (ll *ItemLinkedList) String() {
ll.lock.RLock()
defer ll.lock.RUnlock()
node := ll.head
j := 0
for {
if node == nil {
break
}
j++
fmt.Print(node.content)
fmt.Print(" ")
node = node.next
}
fmt.Println()
}
// Head returns a pointer to the first node of the list
func (ll ItemLinkedList) Head() Node {
ll.lock.RLock()
defer ll.lock.RUnlock()
return ll.head
}
Pruebas
Las pruebas describen el uso de la implementación anterior.
package linkedlist
import (
“fmt”
“testing”
)
var ll ItemLinkedList
func TestAppend(t *testing.T) {
if !ll.IsEmpty() {
t.Errorf(“list should be empty”)
}
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"first"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">IsEmpty</span>() {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"list should not be empty"</span>)
}
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">1</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 1 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"second"</span>)
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"third"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">3</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 3 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
}
func TestRemoveAt(t *testing.T) {
_, err := ll.RemoveAt(1)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">2</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 2 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
}
func TestInsert(t *testing.T) {
//test inserting in the middle
err := ll.Insert(2, “second2”)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
if size := ll.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
<span style="color:#75715e">//test inserting at head position
err = ll.Insert(0, “zero”)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
}
func TestIndexOf(t *testing.T) {
if i := ll.IndexOf(“zero”); i != 0 {
t.Errorf(“expected position 0 but got %d”, i)
}
if i := ll.IndexOf(“first”); i != 1 {
t.Errorf(“expected position 1 but got %d”, i)
}
if i := ll.IndexOf(“second2”); i != 2 {
t.Errorf(“expected position 2 but got %d”, i)
}
if i := ll.IndexOf(“third”); i != 3 {
t.Errorf(“expected position 3 but got %d”, i)
}
}
func TestHead(t *testing.T) {
ll.Append(“zero”)
h := ll.Head()
if “zero” != fmt.Sprint(h.content) {
t.Errorf(“Expected zero
but got %s”, fmt.Sprint(h.content))
}
}
Crear una estructura de datos de lista enlazada concreta
Puede utilizar esta implementación genérica para generar listas vinculadas de tipo específico, utilizando
//generate a `IntLinkedList` linked list of `int` values
genny -in linkedlist.go -out linkedlist-int.go gen "Item=int"
//generate a </span>StringLinkedList<span style="color:#e6db74">
linked list of </span>string<span style="color:#e6db74">
values
genny -in linkedlist.go -out linkedlist-string.go gen “Item=string”
Más tutoriales de go:
- Uso de NGINX Reverse Proxy para brindar servicios de Go
- Hacer una copia de una estructura en Go
- Los conceptos básicos de un servidor web Go
- Ordenar un tipo de mapa en Go
- Ir consejos en pocas palabras
- Explicación de las etiquetas Go
- Ir al formato de fecha y hora
- Procesamiento JSON con Go
- Ir a funciones variadas
- Hoja de referencia de Go Strings
- Explicación de la interfaz Go Empty
- Depuración de Go con VS Code y Delve
- Parámetros de devoluciones de Go Named
- Generación de cadenas y números aleatorios en Go
- Estructura del sistema de archivos de un proyecto de Go
- Algoritmo de búsqueda binaria implementado en Go
- Uso de indicadores de línea de comando en Go
- GOPATH explicado
- Cree una aplicación de línea de comandos con Go: lolcat
- Construyendo un comando CLI con Go: cowsay
- Uso de Shell Pipes con Go
- Tutorial de Go CLI: clon de la fortuna
- Enumere los archivos en una carpeta con Go
- Use Ir para obtener una lista de repositorios de GitHub
- Ve, agrega un trozo de cadenas a un archivo
- Ve, convierte una cadena en un segmento de bytes
- Visualice sus contribuciones locales de Git con Go
- Introducción a la creación de perfiles de memoria y CPU de Go
- Resolver el error "no admite la indexación" en un programa Go
- Medir el tiempo de ejecución en un programa Go
- Creación de un rastreador web con Go para detectar títulos duplicados
- Siga las mejores prácticas: ¿puntero o receptores de valor?
- Siga las mejores prácticas: ¿Debería utilizar un método o una función?
- Ir a estructuras de datos: Establecer
- Hoja de referencia de Go Maps
- Genere implementaciones para tipos genéricos en Go
- Ir a estructuras de datos: diccionario
- Ir a estructuras de datos: tabla hash
- Implementar oyentes de eventos en canales de paso
- Ir a estructuras de datos: apilar
- Ir a estructuras de datos: cola
- Ir a estructuras de datos: árbol de búsqueda binaria
- Ir a estructuras de datos: gráfico
- Ir a estructuras de datos: lista vinculada
- La guía completa de Go Data Structures
- Comparación de valores de Go
- ¿Go está orientado a objetos?
- Trabajar con una base de datos SQL en Go
- Usar variables de entorno en Go
- Ir al tutorial: API REST respaldada por PostgreSQL
- Habilitación de CORS en un servidor web Go
- Implementación de una aplicación Go en un contenedor Docker
- Por qué Go es un lenguaje poderoso para aprender como desarrollador PHP
- Ve, elimina el carácter de nueva línea io.Reader.ReadString
- Ir, cómo ver los cambios y reconstruir su programa
- Ve, cuenta los meses desde una fecha
- Acceder a los parámetros HTTP POST en Go