专栏首页Crossin的编程教室浅谈链表--数据结构的重要根基

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

链表是什么

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

打个比方:列表就好像火车,每一节车厢连在一起,如果你知道车头在哪里,大致就也能知道第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 实现。

本文分享自微信公众号 - Crossin的编程教室(crossincode)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Python 第37课】 字典

    今天介绍一个python中的基本类型--字典(dictionary)。 字典这种数据结构有点像我们平常用的通讯录,有一个名字和这个名字对应的信息。在字典中,名字...

    Crossin先生
  • 如何用100行Python代码做出魔性声控游戏“八分音符酱”

    最近几天,一款魔性的小游戏在微博上刷屏了,各大平台的主播也纷纷如感染病毒一样直播自己怎么玩这个游戏(被游戏玩)。 这个游戏叫做《不要停!八分音符酱♪》。它是一款...

    Crossin先生
  • 小孩子学什么编程?

    Python 之所以受到广大开发者的欢迎,有一大原因就是语法简单易上手。不过要单论“简单”,Scratch 笑了。

    Crossin先生
  • 每天一算:Delete Node in a Linked List

    LeetCode上第237号问题:Delete Node in a Linked List

    五分钟学算法
  • 总结了一些指针易出错的常见问题(四)

    指针与结构体 简介:我们可以使用C的结构体来表示数据结构元素,比如链表或树的节点,指针是把这些元素联系到一起的纽带。 typedef struct _pers...

    互联网金融打杂
  • 《剑指offer》第11期:两个链表题目

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • 数据结构之链表与递归

    1、提起链表,有一块非常重要的内容,就是递归,这是因为链表本身具有天然的递归性,同时,链表也是一种结构非常简单的数据结构,使得链表是一种非常好的来学习和研究递归...

    别先生
  • 什么是链表?

    链表是数据结构之一,其中的数据呈线性排列。在链表中,数据的添加和删除都较为方便,就是访问比较耗费时间。

    武培轩
  • linux0.11进程睡眠唤醒原理分析

    进程的睡眠是通过调用sleep_on函数,该函数修改了进程的状态并且通过schedule函数切换到其他进程执行,从而实现进程的挂起,TASK_UNINTERRU...

    theanarkh
  • [LintCode] Linked List Cycle(带环链表)

    给出 -21->10->4->5, tail connects to node index 1,返回 true。

    HoneyMoose

扫码关注云+社区

领取腾讯云代金券