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.
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
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)
}
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 :
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 :
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 :
如果您有任何问题或建议，请随时联系我。
以上是Go 中的单链表实现的详细内容。更多信息请关注PHP中文网其他相关文章！
