L'implémentation sous-jacente de la liste chaînée Golang

1. Introduction à la liste chaînée

Une liste chaînée est une structure de données composée de nœuds. Chaque nœud contient des données et un pointeur vers le nœud suivant. Par rapport aux tableaux, les listes chaînées présentent l’avantage d’une expansion dynamique car elles n’ont pas besoin d’allouer un espace mémoire continu au début. Les listes chaînées sont divisées en plusieurs types tels que les listes chaînées unidirectionnelles, les listes chaînées doublement et les listes chaînées circulaires.

Dans cet article, nous discuterons de la mise en œuvre sous-jacente des listes chaînées unidirectionnelles dans Golang.

2. Implémentation d'une liste chaînée unidirectionnelle

En Golang, l'implémentation sous-jacente d'une liste chaînée unidirectionnelle utilise des pointeurs pour construire la relation entre les nœuds. Chaque nœud est défini comme suit :

type Node struct {
    val interface{}
    next *Node
}

où val représente la valeur du nœud, et next représente le pointeur vers le nœud suivant. La liste chaînée unidirectionnelle est définie comme suit : val 表示节点的值，next 表示指向下一个节点的指针。单向链表定义如下：

type SinglyLinkedList struct {
    head *Node
}

其中 head 表示链表的头节点，即第一个节点。

接下来，我们将实现链表的常见操作，包括插入、删除、查找和遍历。

1、插入操作

我们先介绍两种插入操作：在链表头插入和在链表末尾插入。

在链表头插入操作如下：

func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
    node := &Node{val: val}
    node.next = l.head
    l.head = node
}

创建一个新节点 node，将节点的值设置为 val，然后将其指向原头节点 l.head，最后更新 l.head 指向新节点即可。

在链表末尾插入操作如下：

func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
    node := &Node{val: val}
    if l.head == nil {
        l.head = node
    } else {
        curr := l.head
        for curr.next != nil {
            curr = curr.next
        }
        curr.next = node
    }
}

先创建一个新节点 node，如果链表为空，则将新节点设置为头节点。否则，从头节点开始遍历链表，直到找到最后一个节点 curr.next == nil，将其 next 指向新节点即可。

2、删除操作

删除操作包括删除一个指定节点和删除链表中的所有指定节点（相同节点值）。

删除指定节点操作如下：

func (l *SinglyLinkedList) DeleteNode(node *Node) {
    curr := l.head
    if curr == node {
        l.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next == node {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

若要删除的节点是头节点，则直接将 l.head 指向其下一个节点即可。否则从头节点开始遍历链表，找到要删除的节点（curr.next == node），将其 next 指向其下一个节点即可。

删除链表中的所有指定节点操作如下：

func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
    for l.head != nil && l.head.val == val {
        l.head = l.head.next
    }

    curr := l.head
    for curr != nil {
        for curr.next != nil && curr.next.val == val {
            curr.next = curr.next.next
        }
        curr = curr.next
    }
}

若头节点的值为 val，则依次删除指定节点。接着从头节点开始遍历链表，依次删除相同值的节点即可。

3、查找操作

查找操作主要有两种方式：通过指定节点值查找节点和查找该节点在链表中的索引。

通过指定节点值查找节点操作如下：

func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
    curr := l.head
    for curr != nil {
        if curr.val == val {
            return curr
        }
        curr = curr.next
    }
    return nil
}

从头节点开始遍历链表，依次比较节点的值与指定值 val，一旦匹配则返回该节点，否则返回 nil。

查找该节点在链表中的索引操作如下：

func (l *SinglyLinkedList) FindIndex(node *Node) int {
    curr := l.head
    index := 0
    for curr != nil {
        if curr == node {
            return index
        }
        curr = curr.next
        index++
    }
    return -1
}

从头节点开始遍历链表，依次比较节点是否与指定节点 node 相同，如果相同，则返回该节点所在的索引，否则返回 -1。

4、遍历操作

遍历操作主要有两种方式：遍历所有节点和遍历所有节点的值。

遍历所有节点操作如下：

func (l *SinglyLinkedList) Traverse() []*Node {
    nodes := make([]*Node, 0)
    curr := l.head
    for curr != nil {
        nodes = append(nodes, curr)
        curr = curr.next
    }
    return nodes
}

从头节点开始遍历链表，将所有节点按顺序加入 nodes 切片中，并返回该切片。

遍历所有节点的值操作如下：

func (l *SinglyLinkedList) TraverseValues() []interface{} {
    values := make([]interface{}, 0)
    curr := l.head
    for curr != nil {
        values = append(values, curr.val)
        curr = curr.next
    }

    return values
}

从头节点开始遍历链表，将所有节点的值按顺序加入 valuesrrreee

où head représente le nœud principal de la liste chaînée, c'est-à-dire le premier nœud.

Ensuite, nous implémenterons les opérations courantes des listes chaînées, notamment l'insertion, la suppression, la recherche et le parcours.

1. Opération d'insertion🎜🎜Nous introduisons d'abord deux opérations d'insertion : l'insertion en tête de la liste chaînée et l'insertion à la fin de la liste chaînée. 🎜🎜L'opération d'insertion en tête de la liste chaînée est la suivante : 🎜rrreee🎜Créez un nouveau nœud node, définissez la valeur du nœud sur val, puis pointez-le au nœud principal d'origine l.head, et enfin mettre à jour l.head pour pointer vers le nouveau nœud. 🎜🎜L'opération d'insertion à la fin de la liste chaînée est la suivante : 🎜rrreee🎜Créez d'abord un nouveau nœud node Si la liste chaînée est vide, définissez le nouveau nœud comme nœud principal. Sinon, parcourez la liste chaînée en commençant par le nœud principal jusqu'à ce que le dernier nœud curr.next == nil soit trouvé, et pointez son next vers le nouveau nœud. 🎜🎜2. Opération de suppression🎜🎜L'opération de suppression comprend la suppression d'un nœud spécifié et la suppression de tous les nœuds spécifiés (même valeur de nœud) dans la liste chaînée. 🎜🎜L'opération de suppression d'un nœud spécifié est la suivante : 🎜rrreee🎜Si le nœud à supprimer est le nœud principal, pointez simplement l.head directement vers son nœud suivant. Sinon, parcourez la liste chaînée en commençant par le nœud principal, recherchez le nœud à supprimer (curr.next == node) et pointez son next vers son nœud suivant. 🎜🎜L'opération de suppression de tous les nœuds spécifiés dans la liste chaînée est la suivante : 🎜rrreee🎜Si la valeur du nœud principal est val, supprimez les nœuds spécifiés dans l'ordre. Parcourez ensuite la liste chaînée en commençant par le nœud principal et supprimez les nœuds avec la même valeur dans l’ordre. 🎜🎜3. Opération de recherche 🎜🎜Il existe deux méthodes principales d'opération de recherche : rechercher un nœud en spécifiant la valeur du nœud et rechercher l'index du nœud dans la liste chaînée. 🎜🎜L'opération de recherche d'un nœud en spécifiant la valeur du nœud est la suivante : 🎜rrreee🎜Parcourez la liste chaînée à partir du nœud principal, comparez la valeur du nœud avec la valeur spécifiée val dans l'ordre , et renvoie le nœud une fois qu'il correspond, sinon renvoie nil . 🎜🎜L'opération pour trouver l'index du nœud dans la liste chaînée est la suivante : 🎜rrreee🎜Parcourez la liste chaînée à partir du nœud principal et comparez les nœuds dans l'ordre pour voir s'ils sont identiques au nœud spécifié node S'ils sont identiques, renvoie l'index où se trouve le nœud. Sinon, renvoie -1. 🎜🎜4. Opération de traversée🎜🎜Il existe deux méthodes principales d'opération de traversée : parcourir tous les nœuds et parcourir les valeurs de tous les nœuds. 🎜🎜L'opération de parcours de tous les nœuds est la suivante : 🎜rrreee🎜Parcourez la liste chaînée à partir du nœud principal, ajoutez tous les nœuds à la tranche nodes dans l'ordre et renvoyez la tranche. 🎜🎜L'opération de parcours des valeurs de tous les nœuds est la suivante : 🎜rrreee🎜Parcourez la liste chaînée à partir du nœud principal, ajoutez les valeurs de tous les nœuds à la tranche valeurs dans commandez et retournez la tranche. 🎜🎜3. Résumé🎜🎜En Golang, l'implémentation sous-jacente de listes chaînées unidirectionnelles utilise des pointeurs pour construire des relations entre les nœuds. En implémentant des opérations courantes telles que l'insertion, la suppression, la recherche et le parcours, nous comprenons mieux la nature et les avantages des listes chaînées, et comprenons également mieux comment Golang implémente les listes chaînées au niveau inférieur. Dans le développement réel, les listes chaînées peuvent être appliquées à de nombreux scénarios, tels que le cache LRU, les listes chaînées inversées, etc. 🎜

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!