就链表而言，其不仅仅有单链表，相反其拥有更多种类，此文讲述一些特殊的链表。

静态链表

链表一定要用指针的方式来实现吗？脱离了指针之后，链表就没法实现吗？答案当然是否定的，链表还可以用数组代替指针来实现

定义： 用数组描述的链表叫做动态链表

首先要知道的肯定是如何实现，以及怎样实现了，如下：

代码：

1
2
3
4
5
#define MAXSIZE 1000
typedef  struct{
      Element data ;
      int  cur ;  // 游标 为0时无指向
} Component，StaticLinkList[MAXSIZE] ;

首先设计一个结构体，分为两个数据 —— data（用来存储链表节点的数据） cur（用来存储下一个结点在数组中的下标） 之后定义两个结构变量 —— Component （单个结点）StaticLinkList[MAXSIZE] （静态链表）

既然已经实现，就可以了解相关操作的实现方法了

此后所有描述均为在线性表中的操作

由于数组的空间是一次性申请的，因此我们可以将其简单地理解为数组包含着两个链表，一个为存有数据的链表，另一个为不存有数据的链表，我们称之为备用链表。

同时，为了更加方便地使用静态链表，我们将以下几个位置进行特殊处理。

首位：也就是下标为0的位置，使其 cur 值来存放备用链表第一个结点的下标

数组末位：也就是数组的最后一个元素的 cur 值来存放第一个有数值元素的下标，相当于头节点的作用。

链表末位：也就是存有数据的链表的末位，将其 cur 值指向数组首位，即将值设为0

初始化链表

初始化的方式，初始化之后的链表，其 cur 变得更加有秩序，每一个结点的 cur 值都是下一个结点的下标。如：1结点的 cur 值是2 2结点的 cur 值是3......

代码：

1
2
3
4
5
6
7
8
// 初始化静态链表
status InitList (StaticLinkList space){
      int  i ;
      for (i = 0 ; i<MAXSIZE - 1 ; i++)
            space[i].cur = i+1 ;	// 依次赋值 进行初始化
      space[MAXSIZE-1].cur = 0 ;	// 初始化之后仍为空表 所以最后一个元素cur为0
      return OK ;
}

静态链表的插入

首先，找到有空余位置的地址，即所有未使用过的以及被删除的分量用游标链成一个备用的链表。而我们下标为0的结点的 cur 值刚好指向备用链表首结点下标。

之后，将元素插入并重新设置 cur 值

代码：

1
2
3
4
5
6
7
8
9
int Malloc_SLL (StaticLinkList space){
      int i  = space[0].cur;	// 用变量i临时存储备用链表的首结点下标

      if (space[0].cur)
            space[0].cur = space[i].cur ;	
    		// 链表不为空 使0结点指向下标为i的结点的下一个结点

      return i ;
}

找到插入数据的位置之后，就可以进行插入了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status  ListInsert (StaticLinkList L , int i , ElemType e){
      int j , k , l ;
      k = MAXSIZE - 1 ;
      if ( i < 1 || i > ListLength(L) + 1)	// 判断插入结点的位置是否合理
            return ERROR;
      j = Malloc_SSL(L) ;	// 获得空闲分量的下标
      if ( j ){	
            L[j].date = e ;	// 直接将数据放入数组下标为j的位置
            for (l = 1 ; l <= i-1 ; l++)
                  k = L[k].cur ;	// 找到要插入结点的前一结点
            L[j].cur = L[k].cur ;	 
            L[k].cur = j ;	// 插入节点
            return OK ;
      }
      return ERROR ;
}

理解上述代码，首先要清楚一个概念： 静态链表的结点位置与其在数组上的下标无关，是两个独立的概念。在线性表的静态链表表示时，数据的存储是在数组中是一个接一个紧密排列的，而线性表的排列则是通过 cur 值链成一条。

所以，插入时最主要的两步就是： - 找出空余位置，将数据存储进数组 - 找到结点位置，在线性表中将结点插入

静态链表的删除

此条为根据链表位置进行删除。同样，首先应该想到删除之后的处理方法，也就是将删除结点的位置重新放入备用链表之中

代码：

1
2
3
4
void Fre_SSL(StaticLinkList space, int k ){
      space[k].cur = space[0].cur ;	// 将第一个元素的 cur值赋给要删除的分量
      space[0].cur = k ;  // 将要删除分量的线标赋值给第一个元素的 cur
}

如上代码所示，并入备用链表时，首先将删除结点并入备用链表头部，然后将第一个元素的 cur 值为删除结点的下标。

删除操作如下所示：

代码：

1

注： 删除节点的关键步骤同样可分为两步：

  • 从链表中删除结点，也就是将删除结点的前后节点连接起来（ListDelete函数中操作）
  • 将删除后的结点并入备用链表之中（Fre_SSL函数进行操作）

循环链表

定义：将单链表中终端节点的指针端由空指针指向头节点，就使整个单链表形成一个环，这种头尾相接的链表就被称为单循环链表，简称循环链表

我们一般的单链表为了操作简单，往往给链表增加一个头结点，循环链表也可如此，以使空链表与非空链表处理一致。

我们如此设立循环链表（加头结点的方式），那么寻访第一个结点的时间复杂度为O(1) ，访问尾节点的时间复杂度为O(n)。为了提高寻访尾结点的效率，我们可以舍弃头结点，在链表尾部添加尾节点，尾指针指向链表尾结点，这也是一般设计循环链表的模式。

循环链表的相关操作实现与单链表并无不同，所以不再赘述

双向链表

定义： 双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

首先需要知道双向链表实现的结构

代码： 

1

双向链表的一些操作实现与单链表相同，如：获取长度，查找元素数据，获取元素位置等，所以不进行讨论，直接来学习与单链表有差异的操作，也就是插入与删除。

插入与删除的实现实际本质并无差别，只是多了一个反向指针的连接，注意顺序即可：

插入顺序：

  1. 新结点 prior 指针指向插入位置的前一个结点
  2. 新结点的 next 指针指向插入位置的后一个结点
  3. 将后一个结点的 prior 指针指向新结点
  4. 将前一个节点的 next 指针指向新结点

代码：依照上述顺序，3 4步的顺序不可改变

1
2
3
4
5
// s为新节点 p为从头节点开始找到的插入位置的之前的一个结点
s->prior = p ; 
s->next = p->next ;
p->next->prior = s ;
p->next = s ;

删除顺序

不讲究顺序，简单操作即可

代码：

1
2
3
4
// p为要删除的结点
p->prior->next = p->next ;	// p结点前一个结点的 next 指针指向 p 结点后一个指针的地址
p->next->prior = p->prior ; 	// p结点后一个结点的 prior 指针指向 p 结点的前一个结点地址
free(p) ;