三、几种链表的实现

1、静态链表

单链表的劣势：
单链表的实现严重依赖指针！
数据元素中必须包含一个额外的指针域！
没有指针的程序设计语言无法实现！
由于单链表存在以上的劣势，因此可以对顺序表加以改进，从而通过索引查找下一个元素，达到链表相同的效果，这就是静态链表。
静态链表的定义：
顺序表数组中的元素由两个数据域组成：data和next
data域用于存储数据
next域用于存储下一个元素在数组中的下标

静态链表的逻辑结构
静态链表是在顺序表的基础上利用数组实现的单链表！

静态链表相关定义

创新互联建站是一家专注于网站制作、成都网站设计和成都服务器托管的网络公司，有着丰富的建站经验和案例。

/*结点结构体定义*/
typedef struct _tag_StaticListNode{
    unsigned int data;
    int next;
}TStaticListNode;

/* 静态链表结构体定义 */
typedef struct _tag_StaticList{
    int capatity;
    TStaticListNode header;
    TStaticListNode node[];
}TStaticList; 

获取第pos个元素操作
判断线性表是否合法
判断位置是否合法
由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标

slist->node[0] = slist->header;                   
for(i=0; inode[current].next;
}
obj = slist->node[current].next;

插入元素到位置pos的算法
判断线性表是否合法
判断插入位置是否合法
在数组中查找空闲位置index
由表头开始通过next域移动pos次后，当前元素的next域为要插入的位置
将新元素插入
线性表长度加1

for(i=0; (inode[current].next != 0); i++)   
{
    current = slist->node[current].next;
}
slist->node[index].next = slist->node[current].next;    
slist->node[current].next = index;

删除第pos个元素的算法
判断线性表是否合法
判断插入位置是否合法
获取第pos个元素
将第pos个元素从链表中删除
线性表长度减1

obj = slist->node[current].next;          
slist->node[current].next = slist->node[obj].next;

静态链表的总结
静态链表其实是单链表的另一种实现方式
静态链表的实现“媒介”不是指针而是数组
静态链表主要用于不支持指针的程序设计语言中
静态链表的实现是一种内存管理的简易方法
其完整实现代码在附件中03_StaticList文件夹

2、循环链表

单链表的局限
单链表可以用于表示任意的线性关系
有些线性关系是循环的，即没有队尾元素
对单项链表进行改进即可得到循环链表，其定义为：将单链表中最后一个数据元素的next指针指向第一个元素

循环链表拥有单链表的所有操作
创建链表
销毁链表
获取链表长度
清空链表
获取第pos个元素操作
插入元素到位置pos
删除位置pos处的元素
并且在循环链表中可以定义一个游标：
在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。

循环链表的新操作
获取当前游标指向的数据元素
将游标重置指向链表中的第一个数据元素
将游标移动指向到链表中的下一个数据元素
直接指定删除链表中的某个数据元素
添加游标后的循环链表，就可以解决更为复杂的问题，同比如约瑟夫问题。
n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去，求出列顺序。

循环链表小结：
循环链表只是在单链表的基础上做了一个加强
循环链表可以完全取代单链表的使用
循环链表的Next和Current操作可以高效的遍历链表中的所有元素
循环链表的实现代码在附件中04_CircleList文件夹

3、双向链表

单链表的局限
单链表的结点都只有一个指向下一个结点的指针
单链表的数据元素无法直接访问其前驱元素
逆序访问单链表中的元素是极其耗时的操作
因此对单项链表，加以改进可以得到双向链表：在单链表的结点中增加一个指向其前驱的pre指针

双向链表拥有单链表的所有操作
创建链表
销毁链表
获取链表长度
清空链表
获取第pos个元素操作
插入元素到位置pos
删除位置pos处的元素
双向链表的插入操作

current->next = node;
node->next = next;
next->pre = node;
node->pre = current;

双向链表的删除操作

current->next = next;
next->pre = current;

双向链表的新操作
获取当前游标指向的数据元素
将游标重置指向链表中的第一个数据元素
将游标移动指向到链表中的下一个数据元素
将游标移动指向到链表中的上一个数据元素
直接指定删除链表中的某个数据元素
双向链表小结
双向链表在单链表的基础上增加了指向前驱的指针
功能上双向链表可以完全取代单链表的使用
双向链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素
双向表的实现代码在附件中05_DLinkList文件夹
静态链表和双向链表的改进
静态链表的改进：将数组中的空闲结点链接成空闲链表,实现代码在附件中06_StaticList_imp文件夹

双向链表的改进:双向循环链表,实现代码在附件中07_DCircleLinkList文件夹

所有链表的完整实现：附件