Comprendre et appliquer les principes et méthodes de base des listes chaînées Golang

Principes de base et méthodes de mise en œuvre de la liste chaînée Golang

Une liste chaînée est une structure de données commune, qui se compose d'une série de nœuds, chaque nœud contient des données et un pointeur vers le nœud suivant. Chaque nœud est connecté les uns aux autres pour former une liste chaînée ordonnée. Dans Golang, nous pouvons implémenter des listes chaînées en utilisant des structures et des pointeurs. Ci-dessous, nous présenterons en détail les principes et méthodes de base des listes chaînées et joindrons des exemples de code spécifiques.

Structure de base de la liste chaînée

Tout d'abord, nous devons définir une structure de nœuds de liste chaînée dans Golang, nous pouvons utiliser des structures pour y parvenir.

type ListNode struct {
    Val  int       // 节点存储的数据
    Next *ListNode // 指向下一个节点的指针
}

Opérations de base des listes chaînées

Dans les listes chaînées, les opérations courantes incluent l'insertion, la suppression et la recherche. Nous présenterons ci-dessous la mise en œuvre spécifique de ces opérations une par une.

1. Opération d'insertion

L'opération d'insertion de la liste chaînée peut être distinguée entre deux situations : l'insertion en tête de la liste chaînée et l'insertion au milieu de la liste chaînée. L'implémentation spécifique de l'opération d'insertion est la suivante :

func Insert(head *ListNode, val int) *ListNode {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    if head == nil {
        return newNode
    }
    newNode.Next = head
    return newNode
}

Lors de l'insertion en tête de la liste chaînée, il suffit de pointer le pointeur Next du nouveau nœud vers le nœud principal de la liste chaînée d'origine, et de renvoyer le nouveau nœud comme nouveau nœud principal.

2. Opération de suppression

L'opération de suppression de la liste chaînée peut également être divisée en deux situations : supprimer le nœud spécifié dans la liste chaînée et supprimer le nœud avec la valeur spécifiée dans la liste chaînée. L'implémentation spécifique de l'opération de suppression est la suivante :

func DeleteNode(head *ListNode, target int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    cur := dummy
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == target {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

Lors de la suppression d'un nœud spécifié dans la liste chaînée, il suffit de pointer le pointeur Next du nœud actuel vers le pointeur Next du nœud suivant.

3. Opération de recherche

L'opération de recherche d'une liste chaînée est souvent utilisée pour déterminer si une certaine valeur existe dans la liste chaînée. L'implémentation spécifique de l'opération de recherche est la suivante :

func Search(head *ListNode, target int) bool {
    cur := head
    for cur != nil {
        if cur.Val == target {
            return true
        }
        cur = cur.Next
    }
    return false
}

Nous pouvons parcourir chaque nœud de la liste chaînée et déterminer si la valeur du nœud est égale à la valeur cible. Si elle est égale, retournez vrai, sinon continuez à parcourir jusqu'à la fin. liste chaînée.

Opération transversale de liste chaînée

L'opération transversale de liste chaînée est souvent utilisée pour imprimer la liste chaînée ou obtenir la longueur de la liste chaînée. L'implémentation spécifique de l'opération de parcours est la suivante :

func Traverse(head *ListNode) {
    cur := head
    for cur != nil {
        fmt.Println(cur.Val)
        cur = cur.Next
    }
}

func Length(head *ListNode) int {
    count := 0
    cur := head
    for cur != nil {
        count += 1
        cur = cur.Next
    }
    return count
}

Nous pouvons accéder à chaque nœud de la liste chaînée en déplaçant continuellement le pointeur et effectuer les opérations correspondantes.

Ce qui précède sont les principes et méthodes de base de la mise en œuvre de la liste chaînée Golang. En définissant la structure et le pointeur du nœud pour construire la liste chaînée, des opérations telles que l'insertion, la suppression, la recherche et le parcours sont réalisées. Grâce à ces opérations, nous pouvons traiter de manière flexible les données de la liste chaînée et mettre en œuvre davantage des fonctions plus complexes. J'espère que cet article pourra vous aider à comprendre les principes et les méthodes des listes chaînées.

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!