1.概念

线性表可以看做一种抽象的概念，也可以作为一种抽象数据类型，一个线性表是某类元素的集合，还记录着元素之间的一种顺序关系。相当于一个抽象类，只做定义。

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

2.具体实现

1.顺序表

顺序表的基本实现方式非常简单：表中元素顺序存放在一片足够大的连续储存区间里，首元素存入储存区的开始位置，其余元素依次顺序存放，元素之间的逻辑关系通过元素在储存区里的物理位置表示（隐式表示元素之间的关系）

顺序表在内存中的布局方式：

数据结构与算法——线性表 算法 第1张 数据结构与算法——线性表 算法 第2张

1.顺序表基本操作的实现

 

 

  1. 创建和访问操作

创建空表时，需要分配一块元素储存，记录表的容量，并将元素计数设置为0,复杂度为O(1)

  1. 简单判断操作

 

 

判断表空或表满的操作很容易实现，复杂度都为O(1)

  1. 访问给定下标i的元素

不依赖表中元素个数，因此也是O(1)操作

  1. 遍历操作

要顺序访问表中元素，在遍历过程中记录遍历到达位置，再算出元素位置，即可获取到元素。获取每一个元素的复杂度为O(1)，所以遍历整个表的复杂度为O(n)。

  1. 查找给定元素d的位置

这种操作称为检索或查找，采用遍历的操作，顺序比较，时间复杂度O(n)。

  1. 查找给定元素d在位置k之后第一次出现的位置

同5相同，只不过从位置k以后遍历。

  1. 加入元素

在表的尾端加入和删除都很简单，时间复杂度为O(1)。在其他位置添加和删除就要麻烦些，需要移动操作位置后面的数据，向前移动或向后移动，时间复杂度为O(len-i),i为操作位置。

  1. 删除元素

尾端删除元素操作简单，时间复杂度为O(1)，一般位置删除O(n),基于条件的删除O(n)。

总结：

优点：O(1)时间的按位置访问，元素在表里储存紧凑，除表元素外，只需要O(1)空间存放少量的辅助信息。

缺点：需要连续的储存区存放表中元素，如果表很大，就需要大片的连续内存空间，一旦确定了储存块的大小，不会随着数据的插入和删除操作进行变动，会有大量空闲单元存在，造成浪费。

 

2.顺序表的结构

两种基本实现方式

    1. 一体式结构
    2. 分离式结构

数据结构与算法——线性表 算法 第3张 数据结构与算法——线性表 算法 第4张

 

  1. 一体式分析

实现比较紧凑，有关信息集中在一起，整体性强，易于管理。

创建后储存区大小固定

  1. 分离式分析

表中只保存于整个表有关的信息，实际元素放在另一个独立的元素储存区对象里，通过链接于基本表对相关连，这样的表对象大小统一，但一个表需要两个独立的对象实现，创建和管理工作复杂。分离式实现的最大优点是带来了一种新的可能，可以在标识不变的情况下，为其对象换一块元素储存区，也就是说可以改变表的容量。

      • 另外申请一块更大的存储区
      • 把表中已有元素复制到新存储区
      • 用新的元素存储区替换原来的元素存储区
      • 实际加入新元素

在扩容的时候如果每次只扩大10个元素储存位置，那么在大量数据插入的时候，需要不停的更换存储位置，元素频繁复制迁移。如果每次扩大当前储存量的一倍，当数据较大的时候，会造成大量的存储空间浪费。所以扩容的时候采用的策略也需要权衡利弊。

 

3.python的list

基本实现

    1. 基于下标高效访问和更新
    2. 允许任意加入元素，而且在加入过程中表的id不变

解决方案

    1. 由于需要O(1)时间的元素访问，并能维持元素的顺序，这种表只能采用连续表技术
    2. 要求容纳任意多的元素，就必须能更换元素存储区，所以只能采用分离式技术实现。

实际策略

    1. 在建立空表或很小的表时，系统分配一块能容纳8个元素的存储区，如果满了就换一块4倍大的存储区
    2. 如果表的容量达到50000时，换储存区时容量加倍

 

4.顺序表的简单总结

  1. 最重要的特点是O(1)时间的定位元素访问，更新。很多简单操作的效率也比较高。
  2. 最麻烦的是加入，删除等操作的效率问题
  3. 需要连续的存储空间
  4. 结构不够灵活

 

2.链接表

    1. 单链表
      数据结构与算法——线性表 算法 第5张

在这样的结构中，为了掌握一个表，只需要用一个变量保存着这个表的首节点的引用

    • 一个单链表由一些具体的表节点构成
    • 每个节点是一个对象，有自己的标识，也称为该节点的链接
    • 节点之间通过链接建立起单向的顺序联系
    • 链表的结束只需在最后的节点的链接域设置一个None。
2.1.1. 基本操作
    • 创建空链表:只需要把相应的表头变量设置为空链接。
    • 删除链表：丢弃这个链表里的所有节点，python里只需要将表指正赋值为None，python解释器会自动回收不用的存储。
    • 判断是否为空：将表头变量的值与空链接值比较
    • 判断是否满：一般而言链表不会满，除非程序用完了所有的存储空间
    • 首端插入：
      • 创建一个新节点并存入数据
      • 把原链表首节点的链接存入新节点的链接域next
      • 修改表头变量，使之指向新节点
    • 一般情况下的插入
      • 找到插入位置
      • 执行首端操作的三步
    • 删除表首元素：只需修改表头指针，令其指向第二个节点
    • 一般情况下的删除：找到元素前一节点所在位置，next域改为元素后一节点的链接
    • 扫描、定位和遍历：由于单链表只有一个方向的链接，开始时只有表头的链接在掌握中，所以对表内内容的一切检查都只能从表头开始，沿表中链接逐步进行，过程称为扫描。
      • 按下标定位
      • 按元素定位

 

    • 操作复杂度
      • 创建空表：O(1)
      • 删除表：在python里是O(1)
      • 判断空：O(1)
      • 加入元素或删除：
      • 首端加入：O(1)
      • 尾端加入：O(n)
      • 随意加入：O(n),平均和最坏情况都是
      • 求表的长度：需要扫描整个，得出长度，也可以把长度记录为表的数据成分，O(1)

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄