Comment implémenter des opérations de liste chaînée en langage Go ?

Linked List est une structure de données commune. Elle se compose d'une série de nœuds. Chaque nœud contient deux attributs clés : un champ de données (Data) et un champ de pointeur (Next). Parmi eux, le champ de données est utilisé pour stocker les données réelles et le champ de pointeur pointe vers le nœud suivant. De cette manière, les listes chaînées stockent les données de manière flexible et adaptée à de nombreux scénarios d'application différents.

Dans le langage Go, la structure de liste chaînée est également bien prise en charge. La bibliothèque standard intégrée de Go fournit le package conteneur/list, qui fournit une implémentation d'une liste doublement chaînée (Double Linked List) qui peut être appelée lorsque nous écrivons du code dans le langage Go. Dans cet article, nous explorerons comment implémenter des opérations de liste chaînée à l'aide du package conteneur/list.

Utilisation de base du package conteneur/liste

Tout d'abord, nous devons comprendre l'utilisation de base du package conteneur/liste. Ce package fournit une structure List qui contient deux pointeurs vers la tête et la queue des éléments. En même temps, cette structure implémente l'interface standard d'une liste doublement chaînée, comprenant PushBack(), PushFront(), InsertBefore(), InsertAfter(), Remove() et d'autres méthodes.

Voici quelques exemples d'opérations de liste chaînée courantes :

1. Créer un objet Liste

l := list.New()

#🎜 🎜 #Ajouter des éléments à la fin de la liste chaînée

2. l.PushBack("Go")
   l.PushBack("Java")

Ajouter des éléments en tête de la liste chaînée

3. l.PushFront("Python")

Insérer avant l'élément spécifié Un élément

4. elem := l.Back()
   l.InsertBefore("C++", elem)

Insérer un élément après l'élément spécifié

5. l.InsertAfter("JavaScript", elem)

#🎜 🎜#Supprimer l'élément spécifié#🎜🎜 #

l.Remove(elem)

6. Ces opérations de base de liste chaînée peuvent être utilisées directement dans notre programme. Cependant, le développement d'applications pratiques nécessite davantage d'opérations de liste chaînée. Ce qui suit présentera les méthodes d'implémentation des opérations de liste chaînée telles que l'insertion, la suppression, la recherche et le parcours.

Opération d'insertion de liste chaînée

L'opération d'insertion de liste chaînée peut être divisée selon les deux situations suivantes :

Insérer des éléments en tête de la liste chaînée

1. Pour insérer des éléments en tête de la liste chaînée, vous pouvez utiliser la méthode PushFront(). Les exemples sont les suivants :

l.PushFront(1)
l.PushFront(2)

Insérer des éléments au milieu ou à la fin de la liste chaînée

2. Pour insérer des éléments au milieu ou à la queue de la liste chaînée, vous devez utiliser la méthode InsertAfter() ou InsertBefore() et fournir la position de l'élément correspondant. Les exemples sont les suivants :

elem := l.Back() // 获取链表尾部元素
l.InsertBefore(99, elem) // 在尾部元素前插入新元素

Opération de suppression de liste chaînée

L'opération de suppression de liste chaînée peut être divisée dans les deux situations suivantes :

# 🎜🎜#Supprimer l'élément principal de la liste chaînée

Pour supprimer l'élément principal de la liste chaînée, vous pouvez utiliser la méthode Remove(). Un exemple est le suivant :

1. head := l.Front()
   l.Remove(head)

Supprimer un élément dans la liste chaînée

Pour supprimer un élément dans la liste chaînée, vous devez recherchez d'abord l'emplacement de l'élément, puis utilisez la méthode Remove() pour effectuer l'opération de suppression. Un exemple est le suivant :

2. // 找到需要删除的元素
   target := 2
   for e := l.Front(); e != nil; e = e.Next() {
       if e.Value == target {
           l.Remove(e)
           break
       }
   }

Opération de recherche d'une liste chaînée

L'opération de recherche d'une liste chaînée nécessite souvent de parcourir l'intégralité de la liste chaînée, la complexité temporelle est donc élevée. Cependant, pour les listes chaînées à petite échelle, l’opération de recherche est très rapide.

Trouver un élément dans la liste chaînée

Pour trouver un élément dans la liste chaînée, vous devez parcourir la liste chaînée jusqu'à ce que vous trouviez l'élément, ou la liste chaînée Complètement parcouru. L'exemple est le suivant :

1. // 找到需要查找的元素
   target := 2
   for e := l.Front(); e != nil; e = e.Next() {
       if e.Value == target {
           fmt.Println("Find it!")
           break
       }
   }

Trouver le plus grand élément de la liste chaînée

Pour trouver le plus grand élément de la liste chaînée, vous Il est également nécessaire de parcourir la liste liée et d'enregistrer le processus de traversée. La valeur maximale dans , l'exemple de code est le suivant : list est relativement courante et peut être utilisée pour la sortie, la modification, la recherche et d’autres opérations. Ce qu'il faut noter lors du parcours, c'est que nous devons parcourir chaque élément dans l'ordre des éléments de la liste chaînée.

Parcourir la liste chaînée du début à la fin

Vous pouvez utiliser les méthodes Front() et Next() pour parcourir la liste chaînée de du début à la fin. L'exemple de code est le suivant :# 🎜🎜#

max := 0
for e := l.Front(); e != nil; e = e.Next() {
    if e.Value.(int) > max {
        max = e.Value.(int)
    }
}
fmt.Println("Max value is:", max)

Parcourez la liste chaînée de bout en bout

1. Vous pouvez utiliser le retour ( ) et Prev() pour parcourir la liste chaînée de bout en bout. L'exemple de code est le suivant :# 🎜🎜#

   for e := l.Front(); e != nil; e = e.Next() {
       fmt.Println(e.Value)
   }

Summary

Cet article présente brièvement la méthode d'implémentation de linked. lister les opérations en langage Go. En utilisant le package conteneur/list, nous implémentons des opérations de base telles que l'insertion, la suppression, la recherche et le parcours de listes chaînées. Pour les opérations de liste chaînée dans les applications réelles, nous devons les encapsuler et les développer davantage en fonction des besoins spécifiques pour répondre aux besoins de l'entreprise.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!