如何用 Go 实现单链表

一、概念介绍

下面这副图是我们单链表运煤车队。

每节运煤车就是单链表里的元素,每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连,作为单链表运煤车,从1号车厢开始,每节车厢都知道后面拉着哪一节车厢,却不知道前面是哪节车厢拉的自己。第一节车厢没有任何车厢拉它,我们就叫它车头,第五节车厢后面拉其他车厢,我们称为车尾。

作为单链表它最大的特点就是能随意增加车队的长度,也能随意减少车队的长度。这是比数组公交车最大的优点。

二、Go语言实现讲解

1、节点

每节车厢都由车体、绳索和煤炭构成。在Go语言中表示这种自定义组合体的类型就是结构,当然为了通用性,我们这里要把车厢转换成节点也就是元素,煤炭转换成数据,绳索转换成指针。

type Node struct {
    data Object
    next *Node
}

用张图来描述这种对应关系。

这里结构体Node表示车厢,data表示煤炭用Object类型,next是牵着下节车厢的绳索,用指针表示。

对于车厢来说,除了放煤炭外,还能放瓜果、衣物、饭菜等等,所以这里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处疑点,元芳你怎么看?属下认为

第一,node如果为空,则添加无任何意义;

第二,代码中存在重复的地方;

这第三么,卑职如何才能知道新增结果?

下面大卫哥顺着元芳的思路改进下代码。

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的定义和实现。

(2)以data作为参数,考虑单链表的实现。

(3)将单链表的head独立出来,此时的head是独立的,不存放data,如下图,考虑单链表的实现,并比较这种实现。

(4)如果将head和tail都独立出来,都不存放data,此时的单链表如何实现?这样实现的代码在插入删除操作时候是不是更容易点?

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

懒人记的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Code_iOS

数据结构:链表

工程代码 Github: Data_Structures_C_Implemention -- Link List

671
来自专栏后端之路

跳表在手天下我有之ConcurrentSkipListMap

背景 Jdk给我们提供了大量的map来供我们研发使用。通常情况下我们使用HashMap 需要插入顺序或者访问我们可以使用LinkedHashMap 需要排序我们...

28610
来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

692
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

721
来自专栏向治洪

SparseArray到底哪点比HashMap好

SparseArray是android里为<Interger,Object>这样的Hashmap而专门写的class,目的是提高效率,其核心是折半查找函数(bi...

1867
来自专栏Bingo的深度学习杂货店

Q28 Implement strStr()

Implement strStr(). Return the index of the first occurrence of needle in haysta...

31410
来自专栏开发与安全

数据结构:队列的顺序存储结构(循环队列)

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头...

1867
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

1896
来自专栏小樱的经验随笔

Codeforces 810C Do you want a date?(数学,前缀和)

C. Do you want a date? time limit per test:2 seconds memory limit per test:256 m...

2455
来自专栏移动开发面面观

HashTable,HashMap与ConcurrentHashMap源码分析

1095

扫码关注云+社区