Structures de données Go: liste liée

Analyse et implémentation de la structure de données Linked List dans Go

Une liste chaînée fournit une structure de données similaire à un tableau, mais avec le gros avantage que l'insertion d'un élément au milieu de la liste est très bon marché, par rapport à le faire dans un tableau, où nous devons déplacer tous les éléments après la position actuelle .

Alors que les tableaux gardent tous les éléments dans le même bloc de mémoire, les uns à côté des autres, les listes liées peuvent contenir des éléments dispersés dans la mémoire, en stockant un pointeur vers l'élément suivant.

Un inconvénient par rapport aux tableaux, par contre, est que si nous voulons choisir un élément au milieu de la liste, nous ne connaissons pas son adresse, nous devons donc commencer au début de la liste, et itérer sur la liste jusqu'à nous le trouvons.

Mise en œuvre

Une liste chaînée fournira ces méthodes:

  • Append(t)ajoute un élément t à la fin de la liste chaînée
  • Insert(i, t)ajoute un élément t à la position i
  • RemoveAt(i)supprime un nœud à la position i
  • IndexOf()renvoie la position de l'élément t
  • IsEmpty()renvoie true si la liste est vide
  • Size()renvoie la taille de la liste liée
  • String()renvoie une représentation sous forme de chaîne de la liste
  • Head()renvoie le premier nœud, donc nous pouvons itérer dessus

Je vais créer unItemLinkedListtype générique, sécurisé pour la concurrence, qui peut générer des listes chaînées contenant n'importe quel type en utilisantgenny, pour créer une implémentation de liste chaînée spécifique au type, encapsulant la structure de données spécifique à la valeur réelle contenant les données.

// 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 }

Des tests

Les tests décrivent l'utilisation de l'implémentation ci-dessus.

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)) } }

Création d'une structure de données de liste liée concrète

Vous pouvez utiliser cette implémentation générique pour générer des listes liées spécifiques à un type, en utilisant

//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”


Plus de tutoriels go: