一、概述

线性表在内存中有顺序表和链表两种实现方式。

二、顺序表

用一组地址连续的存储单元依次存储线性表中的数据元素，此时线性表是顺序表，数据元素间的逻辑关系通过元素下标反映出来。

地址计算

$\text{Loc}(ai) = \text{Loc}(a1) + (i - 1) \times k, \text{Loc}(ai+1) = \text{Loc}(ai) + k.$

特点

• 逻辑上相邻的元素在物理位置上也相邻。

优点

• 只需存放数据元素自身的信息，存储密度大，空间利用率高，存取速度快。

缺点

• 需事先分配存储空间，容易造成空间浪费，插入删除操作时效率低。

三、链表

用一组地址任意的存储单元（可以连续，也可以不连续）依次存储线性表中的各个元素，链表可以用指针来实现，也可以用数组来实现。

1. 单向链表

此链表中每个节点由两部分构成：元素自身信息即数据域（用 data 表示），指向直接后继元素位置的信息称为“指针域”（用 link 表示）。整个链表由一个称为外指针/头节点指针 list 指出，以表明链表的首地址，当链表为空时，list 为 null。用线性链表存储线性表时，数据元素间的逻辑关系通过指针反映出来。

实例 1：3 5 7 9

int head, data[202], next[202], idx;

char data[202] = "Hello"; // 下标为 i 的 data 数组元素存放第 i 个节点的数据

next[202] = {1, 2, 3, 4, -1}; // 下标为 i 的 next 数组元素存放第 i 个节点的下一个节点的下标，null 用 -1 表示单链表的最后一个节点。

实例2：3 5 7 9

typedef struct LNode { // 定义单链表结点类型

int data; // 数据域，可以是别的各种数据类型，本文统一用int类型

struct LNode *next; // 指针域

} LNode, *LinkList;

2. 双向链表

双向链表的每个链节点除了数据域 data 外设置两个指针域，一个 llink 指向直接前驱节点，一个 rlink 指向直接后继节点。双向链表有循环线性和非循环线性，也可根据需要在链表前设置头节点 list。

3. 循环链表

链表最后一个链节点的指针指向链表的第一个链节点，整个链表形成一个环。从表中任意节点出发均可找到表中其他节点。

4. 链表操作

链表的常见操作有很多，最基本的操作有链表的创建、插入、删除等，这些操作都是在更改相关节点的后继（双向链表还有前驱）。

图示以单向链表的插入为例：

指针形式：在第 i 个节点前插入一个节点 x，需要将第 i-1 个节点的后继更改为 x，将节点 x 的后继更改为 ai。

代码 1（指针）

• 头文件以及初始化：

• 创建链表：

• 插入：

• 删除：

• 其他：

代码 2（数组）

5. 顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持 O(1)	不支持；O(n)
任意位置插入或者删除	可能需要搬移元素，效率低	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

四、习题

1. NOIP2014 链表不具有的特点是()。

{{ select(1) }}

• 不必事先估计存储空间
• 可随机访问任一元素
• 插入、删除不需要移动元素
• 所需空间与线性表长度成正比

2. NOIP2015 线性表若采用链表存储结构，要求内存中可用存储单元地址()。

{{ select(2) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可

3. NOIP2011 在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是()。

{{ select(3) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

4. NOIP2014 对长度为 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度是()。

{{ select(4) }}

• n/2
• (n+1)/2
• (n-1)/2
• n/4

5. NOIP2014 有以下结构体说明和变量定义，如图所示，指针 p、q、r 分别指向一个链表中的二个连续节点。

struct node {

    int data;

    node* next;

} *p, *q, *r;

现要将 q 和 r 所指节点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是 ()。

{{ select(5) }}

• q->next=r->next; p->next=r; r->next=q;
• p->next=r; q->next=r->next; r->next=q;
• q->next=r->next; r->next=q; p->next=r;
• r->next=q; q->next=r->next; p->next=r;

6. NOIP2010 双向链表中有两个指针域 llink 和 rlink，分别指向该节点的前驱及后继，设 p 指向链表中的一个节点，它的左右节点均非空。现要求删除节点 p，则下面语句序列中错误的是 ()。

{{ select(6) }}

• p->rlink->llink=p->llink; p->llink->rlink=p->rlink; delete p;
• p->llink->rlink=p->rlink; p->rlink->llink=p->llink; delete p;
• p->rlink->llink=p->llink; p->rlink->llink->rlink=p->rlink; delete p;
• p->llink->rlink=p->rlink; p->llink->rlink->llink=p->llink; delete p;