数据结构系列：列表？线性表？这俩货到底什么关系？

在刚开始接触数据结构的时候，我一度以为python的内置类型'列表'就是'线性表'(一对一的关系)……我相信很多刚接触数据结构的'新人'可能和我一样对线性表有一定的误解，所以今天主要分享下线性表中列表相关的底层实现，以及一些相关的应用。

01 了解线性表

1) 先说下python列表和线性表到底什么关系

线性表是一个抽象的概念，python的内置数据类型'列表'仅仅是线性表的一种实现方式。也就是说列表是在线性表这个大集合之下的。

2) 工作中主要使用的线性表结构有哪些

线性表包括列表，栈，队列等不同的抽象数据结构，不同的线性表主要体现在于对于数据项的增删改查的方式以及性能差异

3) 线性表的标准概念

线性结构是一种有序数据项的集合，可以有零个或多个数据项，其中每个数据项都有唯一的前驱和后继，除了第一个没有前驱，最后一个没有后继

通过以上我们知道了：其实我们在工作中主要使用的只有3种：列表，栈，队列。这三种常见的线性表，不仅仅使用的场景多，而且相关的知识点巨多，由于篇幅问题，本篇将只分享列表相关的概念，底层实现以及相关的应用，另外两种线性表结构会在后面的文章中分享。

02 列表

Python提供了一系列通常称为序列的复合数据类型。 List是Python中使用最频繁且用途最广泛的数据类型之一。使用列表，我们能非常容易地实现列表中数据的存储，数据的定位等等，你有想过，列表为什么这么好用吗？相信搞懂原理，不仅可以加深你对列表的使用方法，也可以在一些场景中对于是否应该使用列表有一个清晰的认识。

列表有两种经典的实现，一种是基于数组实现，一种则是基于链表实现。我们至少要知道，Python中的内置列表是基于数组实现的，我们先介绍这种。

03 数组相关

1) 概念

数组你就可以浅显的理解为一个固定形状，大小的箱子，里面的物品只能排列成一排，我们可以通过第一个物品的位置定位到其他物品的位置，也可以将新的箱子加进去，也可以将已有物品从箱子中取出等等

就和我们上述描述的一致：数组是一段连续的内存地址，在内存中数据项是相互挨在一起的，只要知道了此列表在内存地址中的起始位置，就能通关偏移量的大小定位到其他数据项的位置，基于索引

2) 数组的两大特点

-支持随机访问

-存储在一块连续的内存上

3) 数组的相关操作

如果你要增加数组大小，步骤如下

-创建一个新的，更大的数组（申请更大的内存空间）

-将原数据复制到新的数组中（这样新数组就有更大的空间容纳数据项）

-将指向就数组的变量重新指向新数组，旧数组的内存则被回收

如果你要减小数组的大小，步骤如下

-创建一个更小的数组

-将原数组内容复制到新数组

-将新数组设置为新的数组对象

数组中删除一项

-先将目标索引位置的数据项从数组中移除

-将索引位置之后的所有数组向前移动一位

数组中插入一项

-先检查数组大小是否够用，不够用先申请空间

-从数组最后一项的位置开始直到要插入数据项的索引位置，将每个数据项都往后移动一个位置

-这样就会在目标位置空出一个位置给新的数据项插入

4) 数组操作的时间复杂度

说到这数组的特性基本上就差不多了，因为python中的列表基于数组实现，所以上述中的特性就是列表的特性，至少可以理解为什么列表很多操作需要耗费比较大的内存等原因了。

接下来我们分享下另一种列表的实现方法，链表。

04 链表相关

链表其实不难，只是说对于新同学来讲是一个比较新鲜的概念，而且很多的操作和惯有思维比起来有些跳跃。

1) 特点

-由于数组结构的列表对于删除和插入的性能不是很好，所以构造了以链表作为底层结构的实现

-链表结构和数组结构的不同主要体现在每个数据项不光含有数据信息，还另外维护了一个指针元素，这两部分合起来称之为一个节点。而链表实现的基本元素就是节点，单链表的节点包含两个部分，数据项的引用以及到下一个节点的引用

-链表结构中，对于单纯的数据项，在内存中的相对位置没有规则，但是可以通过每个节点中指针信息指向下一个数据项在内存中的位置，这样就形成链条一样的形状，故称之为链表结构

2) 节点类

链表是由一个一个的节点构成，那么必然会先构造节点，我们先看下节点类

节点类的构成很简单：数据项+下一个数据的位置信息

3) 生成链表

链表也很好生成，将节点类连接起来就行了

接下来我们分享下，链表是如何实现列表中的接口的，直接上代码

4) 遍历

5) 搜索目标值

6) 搜索第i项位置的数据

7) 在任意索引位置插入节点

8) 在任意位置删除节点

9) 链表操作的时间复杂度

05 总结

我们分享了两种实现列表全部接口的底层原理，数组其实要简单些，链表稍微复杂一点点，各有优势（链表自己敲一遍代码，理解这个链子的使用，就可以理解的差不多了）。后面两篇文章会分享栈和队列这两种数据结构的特点和原理(大型框架中使用最频繁的数据结构)

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢。