链表

用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

链表中元素的逻辑次序和物理次序不一定相同。

基本概念

数据域

存储数据元素信息

指针域

存储直接后继位置

指针和链

指针域中存储的信息

单链表/线性链表

结点只有一个指针域的链表

双链表

结点有两个指针域的链表

循环链表

首尾相接的链表

头指针

指向链表中第一个结点的指针

首元结点

链表中存储第一个数据元素$a_1$的结点

头结点

链表的首元结点之前附设的一个结点

• 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理。
• 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

头结点是为了操作的统一和方便设立的，放在首元结点之前，其数据域一般无意义，也可以存放链表长度

头指针具有标志作用，所以常用头指针冠以链表的名字

有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了

无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点不一定是链表必需要素

算法分析

1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在屋里上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

这种存取元素的方法被称为顺序存取法。

单向链表

1. 增

给定一个索引i和元素data，生成一个值为data的结点并插入到第i个位置上。

1. 判断插入位置是否合法，如果不合法则抛出异常。
2. 对给定的元素生成一个链表结点。
3. 如果插入位置是0，则直接把生成结点的后继结点设置成当前链表的头结点，并且把生成的结点设置成新的链表头。
4. 如果插入位置不是0，则遍历到插入位置的前一个位置，把生成的结点给插入进来。
5. 更新链表的大小，即对链表的长度执行加一的操作。

2. 删

给定一个索引i，将从链表头开始，数到第i个结点删除。

1. 判断删除位置是否合法，如果不合法则抛出异常。
2. 如果删除的位置是首个结点，直接把链表头更新为他的后继结点。
3. 如果删除的位置非首个结点，则遍历到要删除位置的前一个结点，并且把前一个结点的后继结点设置为他后继的后继。
4. 更新链表的大小，即对链表的长度执行减一的操作。

3. 查

链表中查找指定元素是否存在。如果存在，则返回该结点，否则返回NULL。

1. 遍历整个链表，对链表中的每个元素和指定元素进行比较，如果相等，则返回当前遍历到的结点。
2. 如果遍历完整个链表都没有找到相等的元素，则返回NULL。

4. 元素的索引

给定一个索引值i，从链表头结点开始数，数到第i个结点并返回。

1. 判断给定索引是否合法，不合法就抛出异常。
2. 直接通过索引访问即可获得对应元素。

5. 改

将链表中指定索引的元素更新为新的值。

1. 直接通过索引访问即可获得对应的结点，修改成指定的值。

双向链表