Golang程序 实现链表

在Go编程语言中，linked list是一个由一系列节点组成的线性数据结构，这些节点通过next pointer相互链接，next pointer指向下一个地址。我们将在本程序中使用两种方法实现链表。在第一种方法中，将使用结构，在第二个例子中，将使用列表结构。

方法一：使用结构

在这种方法中，这个链接列表中有三个节点，每个节点的值为 1、2 或 3。每个节点的下一个指针指向列表中它后面的节点，而头部变量指向第一个节点。在每个节点的下一个指针之后，for-loop在链接列表中循环，直到它到达一个下一个指针为零的节点，这表示列表的结束。

算法

• 第1步– 创建一个包main，并在程序中声明fmt(格式包)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步 – 创建一个节点结构，其字段为next和num_val。节点的值存储在value中，next是指向列表中它后面的节点的指针。

• 第3步 – 在主函数中创建一个头部节点，并将列表中的第一个值设置为它的num_value。

• 第4步 – 应创建第二个节点，并将其num_value设置为列表中的下一个值。

• 第5步 – 通过设置头部节点的下一个指针到第二个节点，你可以连接头部节点和第二个节点。

• 第6步 – 要添加更多的节点并连接它们，重复第3和第4步来完成连接的列表。

• 第7步 – 在头节点的下一步，创建一个当前指针并设置它。

• 第8步 – 当你使用for循环遍历连接列表时，跟踪每个节点的下一个指针。

• 第9步 – 使用fmt.Println()函数打印for循环内的当前节点的值，ln表示新行。

• 第10步– 通过更新为下一个指针的值，当前指针被改变为列表中的下一个节点。

• 第11步 – 重复第7-9步，直到当前节点的下一个指针为nil，表示列表的结束。

例子

在这个例子中，我们将使用结构来实现链表。

package main
import "fmt"

type node struct { //create a struct
   num_val int
   next    *node
}

func main() {
   head := &node{num_val: 1}
   head.next = &node{num_val: 2}
   head.next.next = &node{num_val: 3}
   fmt.Println("The implementation of linked list is given as following:")

   current := head
   for current != nil {               //run a for loop to print values of current node
      fmt.Println(current.num_val)
      current = current.next
   }
}

输出

The implementation of linked list is given as following:
1
2
3

方法2：使用列表结构

在这个实现中，链接列表被实现为一个List结构，其头部字段指向根节点。通过构造一个新的节点，将其下一个指针设置为现有的头部节点，并修改 List 结构的头部字段以指向新的节点，Insert 方法在列表的开始添加一个具有指定值的新节点。在每个节点的下一个指针之后，Print方法打印出列表中每个节点的值。

算法

• 第1步 – 创建一个包main，并在程序中声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步– 创建一个List结构，给它的头部字段一个*Node的类型。

• 第3步– 创建一个Node结构，将value和next作为其两个字段。节点的值存储在value中，next是指向列表中它后面的节点的一个指针。

• 第4步– 创建一个Insert方法，接受一个值作为List结构的参数。

• 第5步– 在Insert方法中创建一个具有指定值的新节点n。

• 第6步– 将新节点的下一个指针设置为列表结构的当前头部。

• 第7步– 为了指向新节点，更新List结构的头部字段。

• 第8步– 为List结构创建一个名为Print的方法，在链接列表中进行迭代并输出每个节点的值。

• 第9步– 在主函数中创建一个List结构，使用Insert方法向其添加一些节点。

• 第10步 – 要打印列表中每个节点的值，请调用 Print 方法。

例子

在这个例子中，我们将使用列表结构来实现链表。

package main
import "fmt"

type List struct { //create a list struct
   head *Node
}

type Node struct {
   value_num int
   next      *Node
}

func (l *List) Insert(value_num int) {
   n := &Node{value_num: value_num}
   n.next = l.head
   l.head = n
}

func (l *List) Print() {
   current := l.head
   for current != nil {
      fmt.Println(current.value_num)
      current = current.next
   }
}

func main() {
   list := &List{}  //create a list struct
   fmt.Println("The implementation of linked list is given as:")
   list.Insert(3)
   list.Insert(2)
   list.Insert(1)
   list.Print()
}

输出

The implementation of linked list is given as:
1
2
3

总结

我们用两个例子执行了实现链表的程序。在第一个例子中，我们使用了结构，在第二个例子中，我们使用列表结构来实现链表。