第一节 如何用Go实现单链表
一、概念介绍 下面这副图是我们单链表运煤车队。 每节运煤车就是单链表里的元素,每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连,作为单链表运煤车,从1号车厢开始,每节车厢都知道后面拉着哪一节车厢,却不知道前面是哪节车厢拉的自己。第一节车厢没有任何车厢拉它,我们就叫它车头,第五节车厢后面拉其他车厢,我们称为车尾。 作为单链表它最大的特点就是能随意增加车队的长度,也能随意减少车队的长度。这是比数组公交车最大的优点。 二、Go语言实现讲解 1、节点 type Node struct { data Object next *Node } 用张图来描述这种对应关系。 对于车厢来说,除了放煤炭外,还能放瓜果、衣物、饭菜等等,所以这里data的类型必须通用,当然Go里是没有Java里的Object类型的,所以我们就自己定义了一个。 type Object interface{} 2、链表 type List struct { size uint64 // 车辆数量 head *Node // 车头 tail *Node // 车尾 } 3、方法 (1)初始化 第一步就是组装单链表车队,这就是初始化。不过开始的时候车队是个空壳,一个车厢没有。 func (list *List) Init() { (*list).size = 0 // 此时链表是空的 (*list).head = nil // 没有车头 (*list).tail = nil // 没有车尾 } (2)添加元素 当前的单链表是空的,所以我们要向里面添加元素。 func (list *List) Append(node *Node) { (*list).head = node // 这是单链表的第一个元素,也是链表的头部 (*list).tail = node // 同时是单链表的尾部 (*list).size = 1 // 单链表有了第一个元素 } 现在单链表有了第一个元素,我还想再添加一个元素,当然是添加到单链表尾部。 func (list *List) Append(node *Node) { if (*list).size == 0 { // 无元素的时候添加 (*list).head = node // 这是单链表的第一个元素,也是链表的头部 (*list).tail = node // 同时是单链表的尾部 (*list).size = 1 // 单链表有了第一个元素 } else { // 有元素了再添加 oldTail := (*list).tail (*oldTail).next = node // node放到尾部元素后面 (*list).tail = node // node成为新的尾部 (*list).size++ // 元素数量增加 } } 分析上面的代码存在3处疑点,元芳你怎么看?属下认为 func (list *List) Append(node *Node) bool { if node == nil { return false } (*node).next = nil // 将新元素放入单链表中 if (*list).size == 0 { (*list).head = node } else { oldTail := (*list).tail (*oldTail).next = node } // 调整尾部位置,及链表元素数量 (*list).tail = node // node成为新的尾部 (*list).size++ // 元素数量增加 return true } (3)插入元素 一天领导让大卫哥把他小舅子安排到第一个,于是大卫哥为了拍好领导马屁。绞尽脑汁弄了一个方法。 *func (list List) Insert(node *Node) bool { if node == nil { return false } (*node).next = (*list).head // 领导小舅子排到之前第一名前面 (*list).head = node // 领导小舅子成为第一名 (*list).size++ return true }** 来托关系插队的人越来越多,领导的关系户不能动,只能插后面人的队了。于是大卫哥又修改了代码,增加了位置参数。 func (list *List) Insert(i uint,node *Node) bool { // 空的节点、索引超出范围和空链表都无法做插入操作 if node == nil || i > (*list).size || (*list).size == 0 { return false } if i == 0 { // 直接排第一,也就领导小舅子才可以 (*node).next = (*list).head (*list).head = node } else { // 找到前一个元素 preItem := (*list).head for j := 1 ; j < i; j++ { // 数前面i个元素 preItem = (*preItem).next } // 原来元素放到新元素后面,新元素放到前一个元素后面 (*node).next = (*preItem).next (*preItem).next = preItem } (*list).size++ return true } (4)删除元素 插队的关系户太多,影响了正常排队的人,被人投诉,大卫哥只好想办法删除一些。 func (list *List) Remove(i uint,node *Node) bool { if i >= (*list).size { return false } if i == 0 { // 删除头部 node = (*list).head (*list).head = (*node).next if (*list).size == 1 { // 如果只有一个元素,那尾部也要调整 (*list).tail = nil } } else { preItem := (*list).head for j := 1; j < i; j++ { preItem = (*preItem).next } node = (*preItem).next (*preItem).next = (*node).next if i == ((*list).size - 1) { // 若删除的尾部,尾部指针需要调整 (*list).tail = preItem } } (*list).size-- return true } (5)获取 为了获取某个位置的元素,我们需要一个方法。 func (list *List) Get(i uint) *Node { if i >= (*list).size { return nil } item := (*list).head for j := 0; j < i ; j++ { // 从head数i个 item = (*item).next } return item } 到这里基本框架已经出来了,不过还有几个接口还没实现,作为课后作业。 三、小结 单链表就和列车类似,一个接着一个,所以本节从列车类比介绍了单链表的Go语言实现。在接口实现部分大卫哥以序号作为链表中每个节点的操作关键字。在实际应用中,我们往往以data中的某一个字段作为操作关键字。所以这也衍生出链表的不同接口,大家可以参考大卫哥留的链接中的代码实现作为理解。同时有些实现将表头独立出来并不存放数据,这在一定程度上简化了代码的实现。 代码下载 四、习题 (1)补全GetSize,RemoveAll,GetHead和GetTail的定义和实现。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |