用 python 学习数据结构(一)链表

一、为什么要学习数据结构

python 语言和标准库自带了很多数据结构,比如 list、set、dict、tuple、queue、heapq等,所以很在标准库或者第三方库提供的数据结构够用的情况下,不需要自己再写数据结构。

当然,掌握了数据结构的原理之后,面对大量数据的时候,可以更轻松地选择合适的数据结构,以及在标准数据结构不够用的情况下,可以定制化实现自己的数据结构。

为什么要有数据结构呢? 可以考虑在不使用数据结构的情况下,如果需要处理100个数据,是不是就需要使用100个变量来表示它们,如果是10000个数据呢,直接就没法玩儿了。

所以,数据结构就是把大批量要处理的数据组织起来,方便编程的时候使用。数据组织的方式(结构)不同,就形成了多种多样的数据结构。每种结构都有各自的特点以及适用场景。比如,链表只能顺序存取一个数据,二叉搜索树可以 O(log(n))的时间复杂度存取数据,哈希表 可以使用 O(log(1))的复杂度存取数据但是比较适用于 key->value的数据类型。

二、链表是一种什么样的数据结构

接下来就讲一下 链表(List)这个数据结构的原理。

List是一种比较简单的数据结构,把数据通过指针(引用)串起来,组成一个链,操作者只需要拿着 head 或者 tail(双向链表) 就可以操作所有数据了。

ListNode1 --> ListNode2 --> ListNode3 --> ListNode4

每个 ListNode 包含 数据 以及对下一个 ListNode 的引用,如果我们要在某个位置上插入一个节点,比如在 ListNode3后面插入 ListNode5, 插入之后的情况就是:

ListNode1 --> ListNode2 --> ListNode3 --> ListNode5 --> ListNode4

三、python 语言实现简单的 List 结构

我们使用 python 一步步来实现一下这个数据结构,主要实现 find、insertBefore、insertAfter、remove、append、count 这几种操作。

这里主要是学习之用,所以这里的操作和一些标准库的 List 提供的操作接口不太一样。对于高级语言标准容器的List, 一般不会暴露内部的 ListNode。

关于List 的可迭代性,以及更标准的操作封装,放在下一次实现吧。

下面就是代码了,如果有些不对的地方,欢迎大家指正。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181015G01FX900?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券