首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >浅谈链表--数据结构的重要根基

浅谈链表--数据结构的重要根基

作者头像
Crossin先生
发布2019-11-13 19:27:06
8260
发布2019-11-13 19:27:06
举报

链表是什么

链表、列表,说起来有点相似,作用也有点类似,但可别傻傻分不清楚。我们一般说的列表,是一个连续的序列,用来存储一组数据。而链表,虽然也是有序的存储结构,但它不限定要“连续”的。

打个比方:列表就好像火车,每一节车厢连在一起,如果你知道车头在哪里,大致就也能知道第8节车厢在哪。

链表,就像是去往同个目的地的车队,有很多辆车,大家排着队行驶。虽是一个整体,但队伍的顺序是可以很容易调整的。

从概念定义上来说,链表是一种以线性顺序存储的数据结构,但并不要求按顺序存储。它由节点组成,每个节点除了储存自身数据外,还包含一个指向下一个节点的引用(或指针)。

这就是一个包含5个节点的链表示意图:

通常,我们会有一个 head 引用指向链表的开头,而链表的结尾,下一个节点则指向空值 None。

除了上图演示的单向链表外,还存在双向链表(每个节点还增加一个指向前一个节点的引用)和循环链表(最后一个节点的下一个节点会指向第一个节点)。

链表有什么用

老问题又来了:为什么要有链表?

链表相较顺序存储列表,最大的好处就是很容易往序列中添加和删除元素,单看插入和删除操作,最优可达到O(1)的复杂度。这个从上面举的火车和车队的例子就可以想象出来。另外,链表的好处还有不需要连续的存储空间,且不需要预先知道数据集的大小

但链表也有它的不足,就是如果你要查找某个节点,或访问指定序号的节点,效率则比较低。

所以,链表更适合需要频繁增删元素但很少查找元素,或者无法预知数据规模的场景

举一个例子:玩过格斗游戏的人,都知道有个“搓招”的设定,就是你按下一定顺序的按键(如 →↓↘→AB),就会触发角色的特殊招式。当玩家操作角色时,会不停按下各个按键,这时如果你想判断最近的按键组合是否符合某一固定招式,就可以用链表来记录最近的按键历史,并且在过程中不断更新。

那么,为何我们标题说链表是数据结构的重要根基呢?因为从上面的描述我们可以看出,链表的节点是非常灵活的,可以组织成不同的结构。例如我们上次提到的栈,就完全可以改为用链表实现。其他的一些数据结构,如队列、树、图,一些算法,如 LRU(最近最少使用算法),文件系统等,均会用到链表这种数据结构。

最近又火起来的概念:区块链,它也是某种意义上的链表。

链表的实现

我们用 Python 语言来自己实现一个单向链表结构,以加深理解。

功能需求:

创建一个 SingleLinkedList 类,具备以下功能:

  1. SingleLinkedList() - 创建新的单链表,不需要参数,返回空链表。
  2. addFirst(item) - 将元素添加到链表头,需要参数,无返回值。
  3. remove(item) - 删除链表内元素,需要参数,并修改单链表的内容。
  4. isEmpty() - 检查单链表是否为空,不需要参数,返回布尔值。
  5. length() - 返回单链表中元素个数,不需要参数,返回整数。

开发思路:

照例先来几张示意图,理一下上述几个功能:

1. 创建节点、单链表并 addFirst(item)

2. 继续 addFirst(item) 添加节点。

3. 多次添加节点后就会出现我们开头的单链表。

4. 删除储存数据为4的头部节点

5. 删除链表中间储存元素为2的中间节点

在删除链表元素的过程包含两个步骤:

1. 遍历链表,找到删除的元素。我们从 head 节点找起,直到 next 节点为 None 的尾部节点

2. 当找到元素后,将其前一个节点的 next 节点指向它原本的 next 节点,也就实现了从列表中删除元素

代码实现:

class Node:    def __init__(self, initdata):        self.data = initdata        self.next = None
    def __str__(self):        # 方便后续输出观察数据          return str(self.data)
class SingleLinkedList:    def __init__(self):        self.head = None # 记录头部节点        self.size = 0 # 记录链表长度
    def isEmpty(self):        return self.head == None
    def addFirst(self, item):        temp = Node(item) # 创建节点        temp.next = self.head # 新节点指向原先的头节点         self.head = temp # 重新指向头节点        self.size += 1
    def remove(self, item):        currentNode = self.head # 查找节点,从头部节点开始        found = False # False 表示还没找到要删除的节点        previous = None # 记录当前节点的前一个节点,当删除节点为头节点时,previous 等于 None        while currentNode != None and not found: # 尾节点指向 None,所以currentNode != None, 表示链表还没有查找完。            if currentNode.data == item: # 发现数据                found = True            else: # 没有找到节点,就接着向下一个节点寻找                previous = currentNode # 记录当前节点的上一个节点                currentNode = currentNode.next # 将当前节点向下一个节点移动        if not found: # 数据不存在链表中            raise raise ValueError('SingleLinkedList.remove(item): item not in SingleLinkedList')        if previous == None: # 发现要删除的节点是头节点            self.head = currentNode.next        else: # 要删除的节点是中间节点或尾部节点            previous.next = currentNode.next # 将当前节点的上一个节点指向当前节点的下一个节点        self.size -= 1
    def length(self):        return self.size            if __name__ == '__main__':        u = SingleLinkedList()    u.isEmpty()    print(u.head)    u.addFirst(4)    print(u.head)    u.addFirst('dog')    print(u.head)    u.addFirst(True)    print(u.head)    u.addFirst('ok')    print(u.head)    u.remove('dog')    print(u.head)    u.length()

以上便是一个单链表的 Python 实现。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-11-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Crossin的编程教室 微信公众号,前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档