转自：http://blog.csdn.net/oreo_go/article/details/52116214

一、线性表的定义

线性表：零个或多个数据元素的有限序列。

几个关键的地方。
首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都只有一个前驱和后继。

然后，线性表强调是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

如果用数学语言来定义。可如下：
**若将线性表记为(a1，…，ai-1，ai，ai+1，…，an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i = 1，2，…，n-1时，ai有且仅有一个直接后继，当i = 2 , 3 , … , n时，ai有且仅有一个直接前驱。 **

所以线性表元素的个数n(n ≥ 0)定义为线性表长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

举几个例子，来判断是否是线性表。
第一个：一年的星座列表，是不是线性表呢？

答：当然是，星座通常都是白羊座开头，双鱼座收尾，当中的星座都有前驱后继，而且一共才12个，所以完全符合线性表的定义。

第二个：公司的组织交媾，总经理管理几个总监，每个总监管理几个经理，每个经理管理各自的下述和员工。这样的组织架构是不是线性关系呢？

答：不是，为什么不是呢？因为每一个元素，都有不止一个后继，所以它不是线性表。

第三个：班级同学的友谊关系，是不是线性表呢？

答：不是，因为每个人都可以和多个同学建立友谊，不满足线性的定义。

第四个：班级同学的点名册，是不是线性表？是不是点名册？

答：是，这和刚才的友谊关系是完全不同的，因为它是有限序列，也满足类型相同特点，这个点名册中，每个元素除学生的学号外，还可以有同学的姓名、性别、出生年月什么的，这其实就是我们之前将的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

二、线性表的抽象数据类型

线性表的抽象数据类型定义如下：

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中除了，第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation
    InitList(*L):初始化操作，建立一个空的线性表。
    ListEmpty(L):若线性表为空，返回true，否则返回false。
    ClearList(*L):线性表清空。
    GetElem(L,i,*e):将线性表L中第i个位置元素返回给e。
    LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果
        查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
    ListInsert(*L,i,e):在线性表的第i个位置插入元素e。
    ListDelete(*L,i,*e):删除线性表L中的第i个元素，并用e返回其值
    ListLength(L):返回线性表L的元素个数。

对于不同的应用，线性表的操作时不同的，上述操作时最基本的，问题中设计的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

比如，要实现两个线性表集合A和B的并集操作。即要使得集合A = A ∪ B，说白了，就是把存在集合B中但并不存在中的数据元素插到A中即可。

仔细分析一下这个操作，发现我们只要循环集合B中的元素，判断是否存在A中，若不存在，则插到A中即可。思路应该是很容易想到的。

假设我们La表示集合A，Lb表示集合B，则实现代码如下：

//将所有的在线性表Lb中但不在La中的元素插入到La中
void unionL(List *La , List Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(*Lb);
    for(i = 0 ;i ≤ Lb;i++)
    {
        GetElem(Lb,i,*e);//取出Lb中第i个数据元素赋给e
        if(!LocateElem(*La,e))//La中不存在和e元素相同的数据元素
        {
            ListInsert(La,++La_len,e);//插入
        }
    }
}

这里我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem，ListLength等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

三、线性表的顺序存储结构

1.顺序存储定义

说了这么多的线性表，我们来看线性表的物理结构第一种——顺序存储结构。

线性表的顺序存储结构，指定的是用一段地址连续的存储单元一次存储线性表的数据元素。

2.顺序存储方式

线性表的顺序存储方式，说白了，就是在内存中找了一块地方，把一定内存空间占了，然后把相同数据类型的数据元素一次存在在里面。既然线性表的数据元素的类型都相同，所以用C语言的一维数组来实现顺序存储结构，即把第一个数据元素存储到数组下表为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

为了建立一个线性表，要在内存中找一块地，于是这块地的第一个位置就非常关键，它是存储空间的起始位置。

线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是最大存储容量。

我们已经有了起始位置，也有了最大的容量，于是我们可以在里面增加数据了。随着数据的插入，我们线性表的长度开始变大，不过线性表的当前长度不能超过存储容量，即数组的长度。

来看线性表的顺序存储的结构代码。

 #define MAXSIZE 20 //存储空间初始分配量
 typedef int ElemType;//ElemType根据实际情况而定，这里假设为int
 typedef struct
 {
     ElemType data[MAXSIZE];//数组存储数据元素,最大值为MAXSIZE
     int length;//线性表当前长度
 }SqList;

这里我们发现描述顺序存储结构需要三个属性：
①存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

②线性表的最大存储容量：数组长度MaxSize。

③线性表的当前长度：length。

3.数组长度与线性表长度区别

数组长度是存放线性表的存储空间的长度，存储空间分配完一般是不变的。

线性表长度是线性表中元素数据的个数，随着线性表插入和删除操作的进行，这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

4.地址计算方法

线性表的起始是从1开始的，可数组却是从0开始第一个下标的，于是线性表中第i个元素，存储在数组下标为i - 1的位置。

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

由于每个数据元素，不管他是整型、实型还是字符型，它都是需要占用一定的存储空间的。假设占用的是c个存储单元，那么线性表中第i + 1个元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

LOC(ai+1) = LOC(ai) + c

所以对于第i个数据元素ai的存储位置可以由a1推算得出：

LOC(ai) = LOC(ai) + (i - 1) * c

通过这个公式，随时可以算出线性表中任意位置的地址，不管他是第一个还是最后一个，都是相同的事件。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此我们算法中学到的时间复杂度的概念来说，它的存取时间的性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

四、顺序存储结构的插入与删除

1.获得元素操作

对于线性表的顺序存储结构来说，我们要实现GetElem操作，即将线性表L中的第i个位置元素返回，其实是非常简单的。就程序而言，只要第i个元素在下标范围内，就是把数组第i - 1下表值返回即可。
来看代码：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函数的类型，其值是函数结果状态代码，如OK等
//初始条件：顺序线性表L已经存在，1 ≤ i ≤ ListLength(L)
//操作结果：用e返回L中第i个元素的值
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

注意这里返回值类型Status是一个整型，返回OK代表1，ERROR代表0。

2.插入操作

刚才我们也谈到，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListInsert(*L，i，e)，即在线性表L中第i个位置插入新元素e，应该如何操作？

插入算法的思路：

①如果插入位置不合理，抛出异常；

②如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

③从最后一个元素开始向前遍历到第i个元素，分别将它们都向后移一位；

④将要插入元素填入位置i处；

⑤表长加1。
实现代码如下：

//初始条件:顺序线性表L已存在,1 ≤ i ≤ ListLength(L)
//操作结果:在L的第i个位置插入新的数据元素e,L的长度加1
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length == MAXSIZE)//当线性表已满
        return ERROR;
    if(i < 1 || i >L->length + 1)//当i不在范围内时
    {
        return ERROR;
    }
    if(i <= L->length)//若插入数据位置不在表尾
    {
        for(k = L->length-1;k > i-1;k--)
        {
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;//将新元素插入
    L->length++;
    return OK;
}

3.删除操作

删除算法的思路：
①如果删除位置不合理，抛出异常；

②取出删除元素；

③从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置；

④表长减1。

实现代码如下：

//初始条件:顺序线性表L已经存在，1 <= i <= ListLength(L)
//操作结果:删除L的第i个元素,并用e返回其值,L的长度减1
Status ListDelete(SqList *L ,int i , ElemType *e)
{
    int k;
    if(L->length == 0)//线性表为空
        return ERROR;
    if(i < 1 || i > L->length)//删除位置不正确
        return ERROR;
    *e = L->data[I];
    if(i < L->length)
    {
        for(k = i;k < L->length;k++)
            L->data[k - 1] = L->data[k];
    }
    L->length--;
    return OK;
}

现在，我们来分析一下，插入和删除的事件复杂度。
现在我们来看最好的情况，如果一个元素要插入到最后一个位置，或者删除最后一个位置，此时时间复杂度为O(1)，因为不需要移动元素的。

最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度是多少呢？那就意味着所有元素向后或者向前，所以这个时间复杂度为O(n)。

至于平均的情况，由于元素插入到第i个位置，或者删除第i个元素，需要移动n - i个元素，每个位置插入或删除元素的可能性是相同的，也就是位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间那个元素的移动次数相等，为(n - 1)/ 2。

根据时间复杂度的推导，平均时间复杂度还是O(n)。

这说明说明？线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

4线性表顺序存储结构的优缺点

优点
①无须为表中元素之间的逻辑关系而增加额外的存储空间

②可以快速地存取表中任一位置的元素

缺点
①插入和删除需要移动大量元素

②当线性表长度变化较大时，难以确定存储空间的容量

③造成存储空间的“碎片”

五、线性表的链式存储结构

1.线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些元素可以存在内存未被占用的任意位置。

以前在顺序结构中，每个元素数据只需要存储数据元素信息就可以了。现在在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

因此，为了表示每个数据元素ai与其直接后级元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,….,an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

最后一个，当然意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

2.头指针与头结点的异同

头指针与头结点的异同点。
头指针
① 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

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

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

头结点
①头结点是为了操作的统一和方便而设立的，放在第一元素的结点之间，其数据域一般无意义。

②有了头结点，对在第一元素结点前插入结点，其操作与其它结点的操作就统一了。

③头结点不一定是链表必须要素。

3.线性链表式存储结构代码描述

若线性链表为空表，则头结点的指针域为“空”。

单链表中，我们在C语言中可用结构指针来描述。

//线性表的单链表存储结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList

在这个结构定义中，我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。 假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i + 1个元素，即指向ai+1。也就是说p->data = ai，那么p->next->data=ai+1

六、单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置使很容易的。但在单链表中，由于第i个元素到底在哪？没办法一开始就知道，必须从头开始找。因此，对于单链表实现获取第i个元素的操作GetElem，在算法上，相对麻烦一些。

获得链表第i个数据的算法思路：
1. 声明一个指针p指向链表第一个结点，初始化j从1开始。
2. 当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
3. 若链表末尾p为空，则说明第i个结点不存在；
4. 否则查找成功，返回结点p的数据。
实现代码如下：

//初始条件:顺序线性表L已存在,1 ≤ i ≤ ListLength(L)
//操作结果:用e返回L中第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;//声明一指针
    p = L->next;//让p指向链表L的第一个结点
    j = 1;//j为计数器
    while(p && j < i)//p不为空且计数器j还没有等于i时，循环继续
    {
        p = p->next;//让p指向下也结点
        ++j;
    }
    if(p || j > i)
        return ERROR;//第i个结点不存在
    *e = p->data;//取第i个结点的数据
    return OK;
}

说白了，就是从头开始找，直到第i个结点为止。由于这个算法复杂度取决于i的位置，当i = 1时，不需要变量，而当i = n时则遍历n - 1次才可以。因此最坏情况的时间复杂度是O(n)。

由于单链表的结构没有定义表长，所以不知道事先循环多少次，因此也就不方便使用for来控制循环。其主要核心思想是“工作指针后移”，这其实也是很多算法常用技术。

八、单链表的插入与删除

1.单链表的插入

假设存储元素e的结点为s，要实现结点p、p->next和s之间的逻辑关系的变化，只需要将s插到结点p和p->next之间即可。
根本不需要惊动其他结点，只需要让s->next和p->next的指针做一点改变。

//下面两句不可交换顺序
s->next = p->next;
p->next = s;

单链表第i个数据插入结点的算法思路：
1. 声明一指针p指向链表头结点，初始化j从1开始;
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点,j累加1
3. 若到链表末尾p为空，则说明第i个结点不存在;
4. 若查找成功，在系统中生成一个空节点s；
5. 将数据元素e赋给s->data；
6. 单链表的插入标准语句s->next = p->next; p->next = s;
7. 返回成功

实现代码算法如下：

//初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
//操作结果:在L中第i个结点位置之前插入新的数据元素,L的长度加1
Status ListInsert(LinkList *L , int i , ElemType e)
{
    int j = 1;
    LinkList p,s;
    p = *L;
    while( p && j < i) //寻找第I个结点
    {
        p = p->next;
        ++j;
    }
    if( !p || j > 1)
    {
        return ERROR;//第i个结点不存在
    }
    s = (LinkList)malloc(sizeof(Node));//生成新结点
    s->data = e;
    s->next = p->next;//将p的后继结点赋值给s的后继
    p->next = s;//将s赋给p的后继
    return OK;
}

在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中开辟了一段空间，用了存放数据e的s结点。

2.单链表的删除

现在我们再来看单链表的删除。设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向他的后继结点即可。

我们所要做的，实际上就是一步，p->next = p->next->next;，用q来取代p->next即是：

q = p->next;
p->next = q->next;

也就是说把p的后继结点改成p的后继的后继结点。

单链表第i个数据删除结点的算法思路：
1. 声明一指针p指向链表头指针，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1；
3. 若到链表末尾p为空，则说明第i个结点不存在；
4. 否则查找成功，将欲删除的结点p->next 赋给q；
5. 单链表的删除标准与p->next = q->next；
6. 将q结点中的数据赋给e，作为返回;
7. 释放q结点
8. 返回成功

实现代码算法如下：

//初始条件:顺序线性表L已存在,1≤ i ≤ListLength(L)
//操作结果:删除L的i个结点,并用e返回其值,L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    Link p,q;
    p = *L;
    j = 1;
    while(p->next && j < i)//遍历寻找第i - 1个结点
    {
        p = p->next;
        ++j;
    }
    if( !(p->next) || j > i)
        return ERROR;//第i个结点不存在
    q = p->next;
    p->next = q->next;//将q的后继赋给p的后继
    *e = q->data;//将q结点中的数据给e
    free(q);//让系统回收此结点，释放内存
    return OK;
}

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成：第一部分就是遍历查找第i个结点；第二部分就是插入和删除结点。

从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。
如果我们不知道第i个结点的指针位置，单链表数据结构在插入和删除操作上，与线下顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个结点，对于顺序结构意味着，每次都要移动n - i个结点，每次都是O(n)。而单链表，我们只需在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，事件复杂度为O(1)。
显然，对于插入和删除数据越频繁的操作，单链表的优势就越明显。

八、单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么几种，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置使不需要预先分配划定的，可以根据系统的情况和实际的需求即可生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，一次建立各元素结点，并逐个插入链表。
单链表整表创建的思路算法：

1. 声明一指针p和计数器变量1；

2. 初始化一空链表；

3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

4. 循环：

   生成一新结点赋值给p;
   随机生成一数字赋给p的数据域p->data;
   将p插到头结点与前一个新节点之间的位置。

实现代码如下：

//随机产生n个元素的值，建立带表头结点的单链表线性表L(头插法)
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int I;
    srand(time(0));//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;//先建立一个带头结点的单链表
    for(i = 0;i < n;i++)
    {
        p = (LinkList)malloc(sizoef(Node));//生成新的结点
        p->data = rand() % 100 + 1;//随机生成100以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}

这段代码里，我们始终让新结点在第一的位置上，我们把这种算法简称为头插法。

可事实上，我们还可以把新结点放在最后。这才是排队时的正常思维。我们每次新结点都插在终端结点的后面，这种算法称之为尾插。

实现代码算法如下：

//随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int I;
    srand(time(0));//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));//为整个线性表
    r = *L;//r为指向尾部的结点
    for(i = 0;i < n;i++)
    {
        p = (Node *)malloc(sizeof(Node));//生成新结点
        p->data = rand() % 100 + 1;//随机生成100以内的数字
        r->next = p;//将表尾终端结点的指针指向新结点
        r = p; //就那个当前新结点定义为表尾终端结点
    }
    r->next = NULL;//表示当前链表结束
}

注意L与r的关系，L指整个单链表，而r指向尾节点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

这里需要解释一下，r->next = p的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p。

九、单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下：
1. 声明一结点p和q；
2. 将第一个结点赋值给p；
3. 循环
将下一结点赋值给q;
释放p;
将q赋值给p。

实现代码算法如下:

//初始条件:顺序线性表L已经存在，操作结果：将L重置为空表
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;//p指向第一个结点
    while(p)//没到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;//头结点指针域为空
    return OK;
}

十、单链表结构与顺序存储结构优缺点

简单地对单链表结构和顺序存储结构作对比。
1、存储分配方式：
顺序存储结构有一段连续的存储单元依然存储线性表的数据元素。
单链表采用链式存储结构，用一组任意的存储单元存放线性表的玩意。

2、时间性能：
查找：

• 顺序存储结构O(1)
• 单链表O(n)

插入与删除

• 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
• 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

3、空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

通过上面的对比，我们可以得出一些经验性的结论：

①
若线性表需要频繁查找，很少进入插入和删除操作时，宜采用顺序存储结构。
若需要频繁插入和删除时，宜采用单链表结构。
比如游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况下都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家游戏过程中，可能随时增加或删除，此时应该用单链表比较合适。当然，这只是简单地类比。现实生活中的软件开发，要考虑的问题会复杂得多。

②当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不用考虑存储空间大小问题。
而如果事先知道线性表的大致长度，比如一年12个月，这种用顺序存储结构效率会高很多。

总之，线性表的顺序存储结构和单链表结构各有其优点，不是简单地说哪个不好，需要根据实际情况，来综合平衡采用哪种数据更能满足和达到需求和性能。

十一、静态链表

C语言具有指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加方便灵活。
后来的面向对象语言，如Java、C#等，虽不使用指针，但因为启用了对象引用机制，从某种角度上也间接实现了指针的某些作用。但对于一些语言，如Basic、Fortran等早期的编程高级语言，由于没有指针，链表结构就没办法实现。

有人想出用数组来代替指针，来描述链表。

首先我们用数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下表都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素后继在数组中的下表，我们把cur叫做游标。

我们把这种用数组描述的链表叫静态链表，这种描述方法还有起名叫做游标实现法。

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以方便插入不至于溢出。

//线性表的静态链表存储结构
#define MAXSIZE 1000//假设链表的最大长度1000
typedef struct
{
    ElemType data;
    int cur;//游标(Cursor),为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

另外我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下表;而数组的最后一个元素的cur则存放第一个有数值的元素的下表，相当于单链表中的头结点作用，当整个链表为空时，则为0²。

//将一维数组space中个分量链成一备用链表
//space[0].cur为头指针，"0"表示空指针
Status InitList(StaticLinkList space)
{
    int I;
    for(i = 0;i < MAXSIZE - 1;i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;//目前静态链表为空
    return OK;
}

1.静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，不需要时释放。

我们前面说过，在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表一样的申请和释放问题，所以我们需要自己实现这两个函数。

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的以及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可从备用链表上取得第一个结点作为待插入的新结点。

//若备用空间链表为空，则返回分配的结点下表，否则返回0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//当前数组的第一个元素的Cur存的值
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//由于要拿出一个分量来使用
                        //所以我们,就得把它的下一个分量用作备用
    }
    return I;
}

插入元素

//在L中第i个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L, int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;//注意k首先是最后一个元素的下表
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(L);//获得空闲分量的下标
    if(j)
    {
        L(j).data = e;//将数据赋值给此分量的下表
        for(l = 1;l <= i - 1;l++)//相当于循环链表，找到第i-1位
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;//新的第i个元素元素指向原本第i个元素
        L[k].cur = j;//第i - 1个元素指向新的第i个元素
        return OK;
    }
    return ERROR;
}

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作。

2.静态链表的删除操作

和前面一样，删除元素时，原来是需要释放结点的函数free()。我们也要自己实现它。

//删除在L中第i个数据元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j , k;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for(j = 1;j < = i - 1;j++)//相当于遍历链表
    {
        k = L[k].cur;
    }
    j = L[k].cur;//把要删除的数组下标赋值给j
    Free_SLL(L,j);//调用删除函数
    return OK;
}

//将下表为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space,int k)
{
   space[k] = space[0].cur;//把原来第一位指向的下标赋给新第一位
   space[0].cur = k;//要删除的分量赋给第一个元素cur
}

静态链表也就是相应其他操作的相关实现。比如ListLength

//初始条件:静态链表L已存在。操作结果:返回L中数据元素个数
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

3.静态链表优缺点

优点：在插入和删除操作时，只要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：
①没有解决连续存储分配带来表长难以确定的问题
②失去了顺序存储结构随机存储的特性

十二、循环链表

对于单个链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样当中某一结点就无法找到它的前驱结点了。

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

循环链表解决了一个很麻烦的问题，如何从当中一个结点出发，访问到链表的全部结点。

循环链表和单链表的主要差异就是在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

十三、双向链表

在单链表中，有了next指针，这就使得我们要查找下一结点的事件复杂度为O(1)。可是如果我们要查找的是上一节点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历寻找。

为了克服单向性这一缺点，设计出了双向链表。双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，一个指向直接前驱。

//线性表的双向链表存储结构
typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;//直接前驱指针
    struct DuLNode *next;//直接后继指针
}DulNode,*DuLinkList;

既然单链表可以有循环，那么双向链表当然可以是循环表。

由于是双向链表，对于链表中某一结点p，它的后继的前驱是它自己。它的前驱的后继自然也是它自己。即：

p->next->prior = p = p->prior->next

插入操作时，其实并不复杂，但是顺序很重要。
假设存储元素e的结点为s，要实现将结点s插入到p和p->next之间需要下面几部。

s->prior = p;//把p赋给s的前驱
s->next = p->next;//把p->next赋给s的后继
p->next->prior = s;//把s赋给p->next的前驱
p->next = s;//把s赋给p的后继

如要删除结点p，只要下面两步骤。

p->prior->next = p->next;//把p->next赋给p->prior的后继
p->next->prior = p->prior;//把p->proir赋给p->next的前驱
free(p);//释放p的空间

双向链表对于单链表来说，要更复杂一些，对于插入和删除时，需要小心。
另外由于它每个结点需要几轮两份指针，所以在空间上是要占用略多一些的。不过由于良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。

说白了，也就是空间换时间。