线性表

线性表分为两种模型:顺序表和链接表。

顺序表:表中的元素顺序的放在一大块连续的存储区里。

链表:将表中的元素通过链接构造起来的一系列存储块。


顺序表:

    对顺序表的各种访问操作中,如果执行中不需要扫描表内容的全部或者一部分,其时间复杂度都是O(1),需要扫描表内容的操作时间复杂度是O(n),如保序定向插入删除。

顺序表的两种实现方式:一体式结构和分离式结构。

Python中list采用的是分离式结构的动态顺序表,实现策略如下:在建立空表时,系统分配一块能容纳8个元素的存储区;在执行插入操作(insert或者append等)时,如果元素区满就换一块4倍大的存储区。但如果当时表已经很大(目前值是5000),系统将改变策略,换存储区时容量加倍。引入后的策略是避免出现过多空闲的存储位置。通过这套技术实现的list平均时间复杂度是O(1)。

如果一个表的使用中需要经常修改结构,用顺序表去实现就不太方便,反复操作的代价可能很高。如果程序里需要巨大的线性表,采用顺序表实现就需要巨大的块的连续存储空间,这也可能造成存储管理方面的困难。


链接表:

采用链接表的基本思想如下:

1、把表中的元素分别存储在一批独立的存储块(称为表的结点)里。
2、通过表中的任一个结点可以找到与其相关的下一个结点。
3、在前一个结点中显式的记录与下一个结点的关联。



总结:普通单链表可以实现表头插入删除操作o(1)时间,但表尾操作o(n)

加入尾部指针可以实现实现表头插入删除,表位插入操作o(1)时间,但表删除o(n)

双链表可以实现表头表位操作满足o(1)时间

以上中间操作皆为o(n)时间。

双链表比单链表多了一个引用域,提高了操作的的灵活性,但是损失了存储。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 大学的时候不好好学习,老师在讲台上讲课,自己在以为老师看不到的座位看小说,现在用到了老师讲的知识,只能自己看书查资...
    和珏猫阅读 1,488评论 1 3
  • 1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,124评论 6 15
  • 3.2 线性表的定义 线性表,从名字上你就能感觉到,是具有像线一样的性质的表。 零个或多个数据元素的有限序列。 这...
    努力生活的西鱼阅读 959评论 0 1
  • 转载请注明出处:http://www.jianshu.com/p/ac8d278cf469 上一篇《数据结构与算法...
    Alent阅读 2,226评论 3 22
  • 在上一篇文章中我们简单说了数据结构的概念和数据结构与算法的一些关系,这一篇文章的内容是关于线性表的东西,主要有线性...
    硅谷小虾米阅读 1,305评论 1 3