Comment implémenter une liste doublement chaînée dans Golang

La liste doublement chaînée est une structure de données commune qui peut établir une association bidirectionnelle entre des éléments, rendant les opérations telles que l'insertion, la suppression et le parcours dans la liste chaînée très efficaces. Dans le langage Go, l'implémentation d'une liste doublement chaînée est très simple. Cet article explique comment utiliser Go pour implémenter une liste doublement chaînée.

Une liste doublement chaînée est une structure liée, et chaque nœud de celle-ci contient trois parties : le pointeur prédécesseur prev, le pointeur successeur next et les données du champ de données. En Go, nous pouvons définir une structure pour représenter les nœuds d'une liste doublement chaînée :

type ListNode struct {
    prev *ListNode
    next *ListNode
    data interface{}
}

où prev 和 next 分别指向当前节点的前驱和后继节点，data est les données stockées dans le nœud.

Pour implémenter une liste doublement chaînée, nous devons définir un type LinkedList, qui contient un pointeur vers le nœud de tête et le nœud de queue de la liste chaînée, ainsi que la longueur de la taille de la liste chaînée :

type LinkedList struct {
    head *ListNode
    tail *ListNode
    size int
}

Implémentons chacun fonctionnement de la liste doublement chaînée une par une.

Insérer des éléments

Insérer des éléments dans une liste doublement chaînée. Il existe trois situations principales :

1. Insérer des éléments en tête de la liste chaînée.
2. Insérer un élément à la fin de la liste chaînée.
3. Insérez un élément au milieu de la liste chaînée.

Dans Go, nous pouvons définir une méthode Insert pour implémenter les trois situations ci-dessus :

func (list *LinkedList) Insert(data interface{}) {
    node := &ListNode{data: data}
    if list.head == nil {
        list.head = node
        list.tail = node
    } else {
        node.prev = list.tail
        list.tail.next = node
        list.tail = node
    }
    list.size++
}

Tout d'abord, nous créons un nouveau nœud pour stocker les données à insérer. Si la liste chaînée est vide, le nouveau nœud sera utilisé comme nœud principal et nœud de queue. Sinon, insérez le nouveau nœud après le nœud de queue et mettez à jour le pointeur du nœud de queue vers le nouveau nœud. Enfin, la longueur de la liste chaînée est augmentée de 1.

Suppression d'éléments

Semblable à l'insertion d'éléments, la suppression d'éléments peut également impliquer trois situations :

1. Suppression de l'élément de tête de la liste chaînée.
2. Supprimez l'élément tail de la liste chaînée.
3. Supprimez l'élément au milieu de la liste chaînée.

Ce qui suit est un exemple d'implémentation de la méthode Delete :

func (list *LinkedList) Delete(data interface{}) {
    node := list.find(data)
    if node != nil {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            list.head = node.next
        }
        if node.next != nil {
            node.next.prev = node.prev
        } else {
            list.tail = node.prev
        }
        list.size--
    }
}

func (list *LinkedList) find(data interface{}) *ListNode {
    node := list.head
    for node != nil && node.data != data {
        node = node.next
    }
    return node
}

Tout d'abord, nous devons trouver le nœud à supprimer, qui est implémenté via une fonction auxiliaire find. Si le nœud à supprimer est trouvé, les pointeurs des nœuds prédécesseur et successeur doivent être mis à jour en fonction de la position du nœud. Si le nœud à supprimer est le nœud principal, mettez à jour le pointeur du nœud principal vers le nœud suivant ; si le nœud à supprimer est le nœud final, mettez à jour le pointeur du nœud principal vers le nœud précédent ; Enfin, réduisez la longueur de la liste chaînée de 1.

Traverser des éléments

Traverser une liste doublement chaînée est très simple. Il vous suffit de partir du nœud principal et de parcourir ensuite le pointeur successeur. Le parcours inverse peut commencer à partir du nœud de queue et parcourir le pointeur précédent prev. Voici deux méthodes pour implémenter respectivement le parcours avant et arrière :

func (list *LinkedList) Traverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.head
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.next
    }
    return result
}

func (list *LinkedList) ReverseTraverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.tail
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.prev
    }
    return result
}

Lors du parcours, nous devons créer une tranche pour enregistrer les résultats du parcours, puis commencer à partir du nœud de tête ou de queue, parcourir chaque nœud le long du pointeur et ajouter le nœud Les données sont stockées en tranches.

Résumé

Grâce au code ci-dessus, nous avons implémenté avec succès les opérations de base d'une liste doublement chaînée. Dans les applications pratiques, il existe de nombreuses extensions et optimisations des listes doublement chaînées, telles que l'insertion ou la suppression d'éléments à une certaine position dans la liste chaînée, l'accès aux éléments via des index, etc. Les lecteurs peuvent poursuivre leurs études et s’entraîner si nécessaire.

L'exemple de code de cet article a été téléchargé sur GitHub pour référence des lecteurs : https://github.com/linjiawei123/golang-doubly-linked-list

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!