Go语言链表操作

有时可以让 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语言面向对象程序设计思想的强大,它没有其他面向对象程序设计语言那么复杂,但设计出来的程序结构清晰而优雅。