链表的逻辑实现与存储结构

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

链表根据构造方式的不同可以分为：

·单向链表

·单向循环链表

·双向链表

1.单向链表

单链表有带头节点和不带头节点两种结构，其结构如图9-8所示。

图9-8　单向链表的两种结构

在带头节点的单链表中，其第一个节点被称作头节点。第一个存放数据元素的节点称作首元节点，头节点指向首元节点。头节点是为了操作的统一与方便而设立的，其一般不放数据（也可存放链表的长度、用作监视哨等）。此节点不能计入链表长度值。

带头节点的单链表的优点：

·在链表第一个位置上进行的操作（插入、删除）和其他位置上的操作一致，无须进行特殊处理；

·无论链表是否为空，head一定不为空，这使得空表和非空表的处理一致。

由于带头节点的链表更容易操作，这里仅实现带头节点的单链表

带头节点的链表插入与删除示意图（见图9-9）：

图9-9　带头结点的链表插入与删除操作

单链表效率分析：

在单链表上插入和删除数据时，首先需要找出插入或删除元素的位置。对于单链表其查找操作的时间复杂度为O（n），所以(www.xing528.com)

·链表插入和删除操作的时间复杂度均为O（n）

·链表读取操作的时间复杂度为O（n）

单链表优缺点：

·优点：不需要预先给出数据元素的最大个数，单链表插入和删除操作不需要移动数据元素

·缺点：不支持随机读取，读取操作的时间复杂度为O（n）。

2.单向循环链表

将单链表中终端节点的指针指向头节点，使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

对于循环链表，为了使空链表与非空链表处理一致，通常设一个头节点。如图9-10所示：

图9-10　单向循环链表

3.双向链表

双向链表是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。使得两个指针域一个指向其前驱节点，一个指向其后继节点。

对于双向链表，其空和非空结构如图9-11所示：

图9-11　双向链表

双向链表是单链表扩展出来的结构，它可以反向遍历、查找元素，它的很多操作和单链表相同。这些操作只涉及一个方向的指针即可。插入和删除操作时，需要更改两个指针变量。

插入操作：注意操作顺序

双向链表相对于单链表来说占用了更多的空间，但由于其良好的对称性，使得能够方便的访问某个节点的前后节点，提高了算法的时间性能。是用空间换时间的一个典型应用。