Go 中的单链表实现

Salut la communauté DEV.to !

Ceci fait partie de ma série sur les structures de données et les algorithmes. Dans cet article, nous implémenterons une liste chaînée unique, puis dans les prochains articles de cette série, j'implémenterai également d'autres types de listes chaînées en utilisant Go.

Source de l'image : GeeksforGeeks

Pour implémenter une liste à chaînage unique, nous avons besoin de structures, d'un nœud et d'une liste à chaînage unique elle-même. Mais avant de commencer à coder, voici comment j'aime organiser mon code :

project
├── singly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

Nœud

Un nœud ne contient que des données et un pointeur vers le nœud suivant dans sa forme la plus simple. Voici donc la structure que nous allons utiliser comme nœud (dans le fichier node.go) :

type SinglyNode struct {
    data interface{}
    next *SinglyNode
}

Nous utilisons interface{} comme type de données pour les données dans la structure afin que nous puissions stocker toutes les données que nous voulons à l'intérieur du nœud.

Ensuite, nous devrions définir quelques méthodes pour utiliser la structure de nœud que nous venons de créer.

func NewSinglyNode(data interface{}) *SinglyNode {
    return &SinglyNode{data: data}
}

Si vous êtes habitué aux langages orientés objet, vous savez probablement ce qu'est un constructeur. Étant donné que Go n'est pas un langage orienté objet, il n'y a pas de classes mais, selon certaines conventions du monde Go, nous créons généralement une fonction préfixée par le mot New. Mais gardez à l’esprit que dans les langages POO, new est un mot-clé spécial qui signifie créer un objet. Ici, le Nouveau n'est qu'un préfixe de nom et rien de plus.

La fonction NewSinglyNode ne reçoit qu'un seul argument appelé data de type interface{} et renvoie un pointeur de SinglyNode.

Ensuite, nous définissons quelques getters et setters pour le nœud :

func (n *SinglyNode) SetData(data interface{}) {
    n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
    n.next = next
}

func (n *SinglyNode) GetData() interface{} {
    return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

Les SetData, Setnext et GetData sont assez explicites. Le GetNext renvoie deux valeurs, un pointeur vers le prochain SinglyNode et une erreur s'il n'y a pas de nœud suivant.

Voici une fonction supplémentaire que j'aime toujours ajouter pour pouvoir toujours savoir comment est la représentation sous forme de chaîne de ma structure :

func (n *SinglyNode) ToString() string {
    return n.data.(string)
}

Liste

Maintenant que nous en avons terminé avec notre nœud, nous devons implémenter la liste elle-même. Une liste à chaînage unique contient le premier nœud comme tête et, selon ma préférence, deux autres données appelées last contiennent le dernier nœud et une propriété country qui contient le nombre de nœuds ajoutés à la liste.

Voici donc les premières lignes du fichier list.go :

type SinglyLinkedList struct {
    head  *SinglyNode
    last  *SinglyNode
    count int
}

Et évidemment, une fonction de type constructeur pour créer facilement une SinglyLinkedList :

func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

La fonction la plus importante dans une liste chaînée est celle qui ajoute un nœud. Voici mon implémentation d'une telle fonction :

func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
    }
    l.last = node
    l.count++
}

La fonction fonctionne comme ci-dessous :

• Vérifiez si l'en-tête de la liste chaînée est vide, si c'est le cas, définissez le nœud reçu comme en-tête de la liste.
• Si la tête n'est pas vide, elle définit le nœud reçu comme propriété suivante du dernier nœud.
• Indépendamment de ce qui s'est passé auparavant, le nœud actuel doit être le dernier nœud afin que la prochaine fois qu'un nœud sera ajouté, il puisse être défini comme le suivant pour le dernier nœud de notre liste.
• Augmentez le nombre de un.

Voici une fonction qui reçoit des données, crée un nœud et le transmet à la fonction AttachNode :

func (l *SinglyLinkedList) Add(data interface{}) {
    l.AttachNode(NewSinglyNode(data))
}

Bien que cette fonction puisse sembler redondante, elle facilitera l'ajout de nœuds à la liste sans en créer un manuellement à chaque fois.

Une fonction pour obtenir également la propriété count :

func (l *SinglyLinkedList) Count() int {
    return l.count
}

La dernière fonction nécessaire est une fonction qui doit renvoyer le nœud suivant dans la liste chaînée :

func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

Je préfère nommer cette fonction comme la fonction GetNext définie pour les nœuds. Ceci est fait pour qu'il y ait plus de cohérence. Lors du premier accès à une liste chaînée, le type est une liste chaînée, il n'y a donc pas d'accès aux fonctions définies pour les nœuds. Définir une fonction du même nom vous permettra d'utiliser GetNext autant que vous le souhaitez pour parcourir votre liste.

Une fonction supplémentaire que j'ai toujours tendance à ajouter est une fonction permettant de récupérer un nœud par l'index :

func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

Cette fonction fait comme ci-dessous :

• Vérifiez si la tête est vide pour renvoyer une erreur
• Vérifiez si l'index 1 est supérieur au nombre de la liste pour renvoyer une erreur. Nous vérifions l'index 1 et non l'index puisque nous considérons les indices commençant à 0 tout comme les tableaux.
• Attribuez l.GetNext() à une variable nommée node (en ignorant l'erreur avec _) puis bouclez pour un de moins que l'index fourni car nous avons déjà le premier stocké dans la variable node, attribuant le nœud suivant du courant nœud comme nœud à nouveau.
• Renvoyer le nœud parcouru sans erreur.

Essai

Maintenant que nous avons notre liste chaînée et nos définitions de nœuds, nous pouvons la tester dans notre fichier main.go comme ci-dessous :

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    firstNode, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    secondNode, err := firstNode.GetNext()
    if err != nil {
        panic(err)
    }

    thirdNode, err := secondNode.GetNext()
    if err != nil {
        panic(err)
    }

    println(firstNode.ToString())  // One
    println(secondNode.ToString()) // Two
    println(thirdNode.ToString())  // Three
}

Ou en utilisant la fonction GetByIndex :

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    node, err := list.GetByIndex(2)
    if err != nil {
        panic(err)
    }

    fmt.Println(node.ToString()) // Three
}

---

Au fait ! Consultez mon e-book gratuit Node.js Essentials ici :

NodeJS 要点 |免费电子书

Adnan Babakan（他/他） ・ 2020 年 9 月 11 日

＃节点 #javascript ＃图书

如果您有任何问题或建议，请随时联系我。

以上是Go 中的单链表实现的详细内容。更多信息请关注PHP中文网其他相关文章！