Ir a estructuras de datos: lista vinculada

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 vinculada
Insert(i, t)agrega un elemento t en la posición i
RemoveAt(i)elimina un nodo en la posición i
IndexOf()devuelve la posición del artículo t
IsEmpty()devuelve verdadero si la lista está vacía
Size()devuelve el tamaño de la lista vinculada
String()devuelve una representación de cadena de la lista
Head()devuelve el primer nodo, por lo que podemos iterar en él

Voy a crear unItemLinkedListtipo 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”

Ir a estructuras de datos: lista vinculada

Análisis e implementación de la estructura de datos de Linked List en Go

Implementación

Pruebas

Crear una estructura de datos de lista enlazada concreta

Más tutoriales de go: