信息学奥赛一本通·初赛真题解析

第6节链表

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

一、顺序表

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

1. 地址计算：$Loc(a_{i}) = Loc(a_{1}) + (i - 1) * k$ ，$Loc(a_{i + 1}) = Loc(a_{i}) + k$ 。
2. 特点：逻辑上相邻的元素在物理位置上也相邻。
3. 优点：只需存放数据元素自身的信息，存储密度大，空间利用率高，存取速度快。
4. 缺点：需事先分配存储空间，容易造成空间浪费，插入删除操作时效率低。

二、链表

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

1. 单向链表/线性链表：此链表中每个结点由两部分构成：元素自身信息即数据域（用data表示），指向直接后继元素位置的信息称为“指针域”（用link表示）。整个链表由一个称为外指针/头结点指针list指出，以表明链表的首地址，当链表为空时，list为null。用线性链表存储线性表时，数据元素间的逻辑关系通过指针反映出来。
2. 双向链表：双向链表的每个链结点除了数据域data外设置两个指针域，一个llink指向直接前驱结点，一个rlink指向直接后继结点。双向链表有循环线性和非循环线性，也可根据需要在链表前设置头结点list。
3. 循环链表：链表最后一个链结点的指针指向链表的第1个链结点，整个链表形成一个环，从表中任意结点出发均可找到表中其他结点。