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”


Más tutoriales de go: