How to implement linked list in golang

Linked list is a common data structure that consists of a series of nodes, each node contains data and a pointer to the next node. In this article, we will use Go language to implement a simple linked list.

1. Define node type

First, we need to define a node type. The node should contain a data element and a pointer to the next node. The code is as follows:

type Node struct {
    Data interface{} //节点存储的数据
    Next *Node       //指向下一个节点的指针
}

We use interface{} to save node data, which allows the linked list to store any type of data.

2. Define the linked list type

Next, we need to define a linked list type. It should contain a pointer to the first node. At the same time, we also added two methods: AddNode and Traverse.

type LinkedList struct {
    Head *Node //指向第一个节点的指针
}

//添加一个节点
func (l *LinkedList) AddNode(data interface{}) {
    newNode := &Node{Data: data}

    if l.Head == nil {
        l.Head = newNode
    } else {
        current := l.Head
        for current.Next != nil {
            current = current.Next
        }
        current.Next = newNode
    }
}

//遍历链表并执行函数
func (l *LinkedList) Traverse(fn func(interface{})) {
    current := l.Head
    for current != nil {
        fn(current.Data)
        current = current.Next
    }
}

The AddNode method adds a node to the end of the linked list. If the linked list is empty, the added node becomes the first node. Otherwise, we traverse the linked list, find the last node and add the new node as its next node.

The Traverse method uses a callback function to operate each node in the linked list. It iterates through each node in the linked list and then executes the passed function on each node. We can use this method to traverse the linked list and print each node:

func main() {
    list := LinkedList{}
    list.AddNode("A")
    list.AddNode("B")
    list.AddNode("C")

    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })
}

The above code will print:

A
B
C

3. Delete Node

Now, let’s add a method to Delete the node in the linked list.

//删除链表中的节点
func (l *LinkedList) RemoveNode(target interface{}) {
    if l.Head == nil {
        return
    }

    if l.Head.Data == target {
        l.Head = l.Head.Next
        return
    }

    current := l.Head
    for current.Next != nil {
        if current.Next.Data == target {
            current.Next = current.Next.Next
            return
        }
        current = current.Next
    }
}

The RemoveNode method takes a parameter that identifies the node to be deleted and traverses the linked list to find the node. If the node is found, change the next pointer of the current node to remove it from the linked list. If the linked list is empty or the node is not found, no action is performed.

Complete code:

package main

import "fmt"

type Node struct {
    Data interface{} //节点存储的数据
    Next *Node       //指向下一个节点的指针
}

type LinkedList struct {
    Head *Node //指向第一个节点的指针
}

//添加一个节点
func (l *LinkedList) AddNode(data interface{}) {
    newNode := &Node{Data: data}

    if l.Head == nil {
        l.Head = newNode
    } else {
        current := l.Head
        for current.Next != nil {
            current = current.Next
        }
        current.Next = newNode
    }
}

//遍历链表并执行函数
func (l *LinkedList) Traverse(fn func(interface{})) {
    current := l.Head
    for current != nil {
        fn(current.Data)
        current = current.Next
    }
}

//删除链表中的节点
func (l *LinkedList) RemoveNode(target interface{}) {
    if l.Head == nil {
        return
    }

    if l.Head.Data == target {
        l.Head = l.Head.Next
        return
    }

    current := l.Head
    for current.Next != nil {
        if current.Next.Data == target {
            current.Next = current.Next.Next
            return
        }
        current = current.Next
    }
}

func main() {
    list := LinkedList{}
    list.AddNode("A")
    list.AddNode("B")
    list.AddNode("C")

    //遍历链表
    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })

    //删除节点并再次遍历链表
    list.RemoveNode("B")
    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })
}

The above code will print:

A
B
C
A
C

4. Summary

In this article, we use Go language to implement a Simple linked list. Linked lists are an important data structure that are widely used in many algorithm and software development scenarios. When writing actual code, consider adding additional functionality and evaluate performance.

The above is the detailed content of How to implement linked list in golang. For more information, please follow other related articles on the PHP Chinese website!