[教程]Go语言链表操作

有时可以让 Struct 的一个指针成员指向它自己，利用这种特性 Struct 对象可以作为链表或者二叉树的元素，通常叫做节点（Node）。链表简介链表是一种常见的重要数据结构，它的主要特点是能动态地...

有时可以让 Struct 的一个指针成员指向它自己，利用这种特性 Struct 对象可以作为链表或者二叉树的元素，通常叫做节点（Node）。

链表简介

链表是一种常见的重要数据结构，它的主要特点是能动态地进行存储分配。我们在使用数组存放数据时，必须事先分配固定长度的存储空间（即元素个数）。比如，有的班级有 60 名学生，而有的班级只有 30 名学生，如果要用同一个数组先后存放不同班级的学生信息，则数组长度至少为60。如果班级人数难以确定，则必须把数组定义得足够大，显然这将会浪费内存。

链表则没有这种缺点，它会根据需要动态开辟内存单元，不会造成内存的浪费。另外，链表还可以动态增添新节点、删除旧节点。下图所表示的是一种最简单的单向链表的结构。

图：单向链表

单向链表中有一个头指针变量，图中以 Head 表示，头指针存放链表第一个元素的地址。链表中每一个元素称为“节点”，每个节点都应包括两个部分：用户数据和下一个节点的地址。

从上图可以看出，Head 指向第一个元素，第一个元素又指向第二个元素……直到最后一个元素 Tail。Tail 不再指向其他元素，它称为“表尾”，它的地址部分是“nil”，表示没有，链表到此结束。

可以看出，链表各元素在内存中可以不连续存放。在链表中要找到一个元素，必须先找到上一个元素，根据它提供的 Next 地址才能找到要找的目标。如果不提供“头指针”Head，则整个链表都无法访问。另外，链表节点之间必须一环扣一环，中间不能断开。否则，链表将丢失节点、不完善。

通过上面的介绍可以看到，链表这种数据结构，必须利用指针变量才能实现，即一个节点中应包含一个指针变量，用它存放下一个节点的地址。

Struct 和 Method 设计单链表

利用 Struct 可以包容多种数据类型的特性，使用它作为链表的节点是最合适不过了。一个结构体内可以包含若干成员，这些成员可以是基本类型、自定义类型、数组类型，也可以是指针类型。这里可以使用指针类型成员来存放下一个节点的地址。

例如，可以定义这样一个结构体类型：

type Node struct {
    Data int
    Next * Node
}

其中成员 Data 用来存放节点中的有用数据，Next 是指针类型的成员，它指向 Node struct 类型数据，这其实就是下一个节点的数据类型，它和上一个节点应该是同一种类型。

对于一个链表，链表头部 Head 最重要。所以要建立一个链表，首先要声明一个指向 Node 的指针类型的 Head，然后再让 Head 的 Next 指向链表的第一个节点，如果还有第二个节点，第一个节点的 Next 再指向第二个节点……直到最后一个节点，让它的 Next 为 nil，即链表到此结束。使用这种方法，就可以建立如上面图中所示的单向链表。

下面是一个链表综合操作的例子，该例中使用链表动态存储学生基本信息。学生基本信息使用结构体 Student 来记录，共有两个字段：学号（Id）和姓名（Name）。链表节点 Node 也包含两个字段：匿名字段（Student）和 Next 指针。

该例不但要使用 Node 节点建立一个能管理学生信息的单向链表，还要使用 Go语言面向对象程序设计思想，在 Node 对象上实现 4 个操作方法，以方便对链表的管理和维护。

• Creat() 方法创建一个新链表，并返回 head 指针。

• PrintLink() 用于链表的输出打印。

• Insert() 方法可以将新节点插入链表，并返回 head 指针。

• Delete() 方法会将节点从链表删除，并返回 head 指针。

在设计过程中，Student 和 Node 的定义，以及 4 个方法的实现在 link 包中完成，最后程序总体功能的验证和测试在 main 包中完成。由于篇幅所限，4 个操作方法的相关算法实现本教程就不再赘述，有兴趣的读者可以参阅数据结构方面的教程。

Link 包中的代码如下：

package link

import (
    "fmt"
)

type Student struct {
    Id int
    Name string
}

type Node struct {
    Student
    Next *Node
}

func (head *Node) Creat() *Node {
    head = nil
    return head
}
func (p *Node) PrintLink() {
    for p != nil {
        fmt.Printf("%d, %s\n", p.Id, p.Name)
        p = p.Next
    }
}

func (newNode *Node) Insert(head *Node) *Node {
    var p0, p1, p2 *Node
    p0 = newNode
    p1 = head
    if head == nil {
        head = p0
        p0.Next = nil
    } else {
        for (p0.Id > p1.Id) && p1.Next != nil {
            p2 = p1
            p1 = p1.Next
        }
        if p0.Id <= p1.Id {
            if head == p1{
                head = p0
            } else {
                p2.Next = p0
                p0.Next = p1
            }
        } else {
            p1.Next = p0
            p0.Next = nil
        }
    }
    return head
}

func (delNode *Node) Delete(head *Node) *Node {
    var p1, p2 *Node
    if head == nil {
        fmt.Println("List nil!")
        goto End
    }
    p1 = head
    for delNode.Id != p1.Student.Id && p1.Next != nil {
        p2 = p1
        p1 = p1.Next
    }
    if delNode.Id == p1.Student.Id {
        if p1 == head {
            head = p1.Next
        } else {
            p2.Next = p1.Next
        }
        fmt.Printf("Delete %d\n", delNode.Id)
    } else {
        fmt.Printf("Node %d not been found!\n", delNode.Id)
    }
End:
    return head
}

【示例】链表综合操作。

// 链表综合操作
package main

import (
    "link"
)

func main() {
    var head *link.Node
    stu1 := link.Node{link.Student{100, "李明"}, nil}
    stu2 := link.Node{link.Student{101, "张晓"}, nil}
    stu3 := link.Node{link.Student{102, "赵琼"}, nil}
    stu4 := link.Node{link.Student{103, "王乐"}, nil}
    //创建新链表
    head = head.Creat()
    //插入节点
    head = stu1.Insert(head)
    head = stu2.Insert(head)
    head = stu3.Insert(head)
    head = stu4.Insert(head)
    //输出链表
    head.PrintLink()
    //删除节点
    head = stu3.Delete(head)
    head.PrintLink()
}

编译并运行该程序，输出结果为：

100, 李明
101, 张晓
102, 赵琼
103, 王乐
Delete 102
100, 李明
101, 张晓
103, 王乐

通过示例的测试与验证，基本能体会到 Go语言面向对象程序设计思想的强大，它没有其他面向对象程序设计语言那么复杂，但设计出来的程序结构清晰而优雅。