闲聊数据结构之list

序言

听说要下雪了，在这寒冷的冬季。。。风太大，我听不见。。。

依稀记得有一次有人问，在你写一些代码的时候，你会选用什么数据结构呢？有什么选择的标准呢。。。当时也就当为了笑谈，好像并无什么特别的喜好，也没什么特别的感觉。。。

为什么不喜欢的东西丢了，还会念念不忘呢？

数据结构漫谈

数据结构，好像很高深一样，但是从未真正研究，但是真正看起来，耗费的时间和心血不是一点点。。。

原来看书，思维枯竭，现在看书。。。嗬，思维洪流，看一句话能无限的涌入各种相关的信息。。。内存溢出了解一下。。。

数据结构总是与算法息息相关，总体看来，数据结构只是保存数据的一种方式，而算法则是实现数据结构的各种操作，数据结构是静态的，是内存的一种表现形式，而算法则有很多种，一种程序的实现可以有各种方式。。。

程序？进程？数据结构？又有什么关系。。。

程序是各种逻辑控制加各种数据结构组成的，看看每天写的程序，除了if 就是else，除了for就是while，除了break就是continue。。。千奇百怪的控制流，而其中流淌的则是各种算法，这种才是生命，才是灵魂。。。

运行一个进程，其实就是一个程序的实例，那么运行同一个程序两次呢？依旧会运行两个进程，进程只是CPU的一种抽象，从而形成多道程序设计的假象，当然，多核的CPU可能不在此列。。。

为什么有了for循环，还需要while循环？

在python中，for循环可以用在很多地方，例如序列是根据下标来访问的，字典是根据键来访问的，也可以根据值来进行迭代，在for循环中，使用的各种可迭代的对象，只是一种值得迭代方式而已。。。而while循环则不同，必须有个判断条件，也就是结果为True或者False，while循环可以实现无限循环，而for不行，while循环还能实现计数循环，然后break跳出循环，这种for也是可以实现的。。。

我们每天可能接触各种各样的不同的数据结构，只是我们不知道而已，例如number，float，list，tuple，dict，set，frozenset，其实数据结构可以脱离语言而存在，而对于高级语言来说，提供了很多高级的数据结构，从而让编程更加容易，这也就是为什么java越来越流行，而c，c++等各种入门的门槛比较高了。。。

数据结构只是一种内存的表现形式，例如线性表，也就是python中的list，tuple，java中的ArrayList，用连续的内存来存放相关的数据，而这种方式的存储，是其最大的优势，也是最大的缺陷。

list，tuple采用连续的内存来保存一块数据，从而如果内存还剩下100M，我现在要申请100M的内存，而内存中并不一定是连续的，从而导致内存不足的报错。

采用连续的内存来保存一块数据，从而在访问数组元素的时候，总是能根据index进行随机访问，随机？random access，那么什么是顺序访问。。。所谓的随机就是得到了一个index，然后能找到这个对象存放的地址，然后访问其值，而对于顺序访问来说，必须先找到第一个，然后找第二个。。。随机访问在数组的访问的时间复杂度为O（1），也就是常量的访问时间。。。

采用连续的内存来保存一块数据，并且是有顺序的存放的，从而会导致在删除数据，插入数据的时候，需要将数据进行搬迁，也就是按位后移。。。从而导致了复杂度在O（n），最坏时间复杂度和平均时间复杂度。。。

删除的时候，也是一样的，要将所有的数据前移，从而时间复杂度也是O（n）。。

从而在选择list的时候，必须是要查询比较多的情况，而对于增加，删除是比较少的情况。。。

但是这种情况也是可以改善的，对于list来说，如果每次都插入的时候是在最后一个元素，也就是append的时候，这种情况就无需移动数据，从而时间复杂度在O（1），而对于删除来说，每次是最后的元素，也是O（1）。。

还有一种情况就是，如果对于序列来说，是不需要保证顺序的，那么在插入数据的时候，可以直接将数据的位置进行更换，从而达到复杂度为O（1）。。

线性表使用连续的内存。。。而在linux系统中，进程看到的内存根本就是假的。。。

linux中，使用的内存，是进程所拥有的单独的虚拟地址空间，独占的式的存在，并不知道其他进程有多少内存，虚拟内存通过映射到实际的物理内存，可能是连续的？也可能不是连续的。。。

所谓的连续，到底连续还是不连续。。。Emmm，很难搞清楚。。。

在使用list的时候，list和tuple其实两者的结构是差不多的，但是两者的区别在于，一个是可变的list，一个不可变的tuple，从而list提供了增删改查的操作，而对于tuple，则仅仅提供了查的操作。。如果进行了其他的操作，那么就是创建了一个新的tuple对象而已。。。

使用一个数据结构，其实也就是使用它的各种方法来进行操作。。。而对象，也只是一个数据结构而已，使用的也是各种操作，从而达成自己的想要实现的目的。。。

看看list的操作方法，append，count，时间复杂度O（1），而对于extend，index，insert，pop，remove，reverse时间复杂度基本都在O（n），sort为O（nlogn）。。。数据结构只是内存的一种表现形式，而这种表现形式则提供了各种操作，这些操作中又反应了各种算法。。。

选用什么数据结构来存储，list适合于有顺序存储的一类数据，用的很多了。。。

list，占用的是连续的内存，从而在生成list的时候，如果一下创建一个很大的列表，那么会有速度上延迟，从而一种改进的方法是使用xrange，生成器，每次只创建一个，从而大大的节省了内存。。。

其实对于基本的数据类型来说，一种类型就规定了一种操作的方法，看看各种list类型，dict类型，操作均是不相同的，从而使用的方法也是不一致的，只有说，在合适的场景使用合适的数据结构。

对于list来说，如果存储各种数据类型的话，那么又能有两种方式（二维数组）。。。

而一种则是如下：

第一种是一体式的存储结构，也就是全部在连续的内存之中，而第二种则是分离的存储结构，在每个元素里面存储一个引用，指向另外一块连续的内存，来存储数据，这个时候，可以保持变量的id不变，而内部的元素发生变化，例如tuple t = （1，【123】），在不变对象中可以使用可变的对象。。。

使用不同的方法，得到相同的目的。。。顺序表也就是数组，其实就是达到随机访问的时间复杂度为O（1）。

风言风语

为啥我上班总感觉我没脑子呢。。。放在家里了？Emmm。。。没有过，也没见过。。。哈哈

为什么不想要的失去之后，还会念念不忘呢？是因为没找到更好的替代？还是因为不是真不想要，而是想要的不够多？贪欲？

最好的也是最差的，其实都是还是带着镣铐跳舞，在各种限制之下做的更好。。。明明知道有很多限制，如果你将所有的关注力都放在限制之中，那么可能就陷入了死循环，永远想改变不可能改变的事。。。更多的应该关注在如何做成，如何能达到自己想要的目标。。。

连续不连续。。。放在连续的内存中，不灵活，就像你写代码的时候，你需要大片的时间来思考，而有一件事打断你，就中断去处理一下，然后。。。这个内存又再次申请，又再次迁移数据，再次释放空间。。。耗费资源。。。像不像CPU切换，但是CPU切换无所谓啊，进程反正要等待IO，切换就切换咯。。。

那么不连续？用链表的方式？。。。嗯，比较灵活，所以就有了碎片的时间，可能干各种事儿，但是不好的地方在于，容易生成内存空洞。。。fire in the hole。。。