下列关于线性表说法中，正确的是（　）。
Ⅰ.顺序存储方式只能用于存储线性结构
Ⅱ.取线性表的第i个元素的时间与i的大小有关
Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素
Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)
Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表

A. Ⅰ、Ⅱ
B. Ⅰ、Ⅲ、Ⅳ、Ⅴ
C. Ⅳ、Ⅴ
D. Ⅲ、Ⅳ、Ⅴ

答案：D

分析：

Ⅱ：当线性表采用顺序存储的时候，取第i个元素的时间与i的大小无关。顺序表的特点是可以随机访问 就是可以直接访问第i个位置。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
优点：随机存取表中元素。
缺点：插入和删除操作需要移动元素。

一、数组

线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构：数组，链表、队列、栈等。

• 什么是数组:

1.  数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
2.  连续的内存空间和相同类型的数据(随机访问的前提)
3. 优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低

• 数组怎么根据下标随机访问的？

通过寻址公式：a[i]_address = base_address + i * data_type_size
其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

 

为何数组插入和删除低效：

插入：
若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。
最好情况时间复杂度 O(1)

如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。

最坏情况复杂度为O(n)

平均负责度为O(n)

2. 低效的插入和删除
1） 插入：从最好O(1) 最坏O(n) 平均O(n)
2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明
3） 删除：从最好O(1) 最坏O(n) 平均O(n)
4） 多次删除集中在一起，提高删除效率
记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。
 

二、链表

 

• 什么是链表

1. 和数组一样，链表也是一种线性表。
2. 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
3. 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

• 链表的特点

1. 插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

• 常用链表

1.单链表

1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

 

2.循环链表

1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2）适用于存储有循环特点的数据，比如约瑟夫问题。

 

3.双向链表

1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3）性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表：

首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

 

选择数组还是链表？

1.插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点
1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。
3.链表缺点
1）内存空间消耗更大，因为需要额外的空间存储指针信息。
2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。
4.如何选择？
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。
如果代码对内存的使用非常苛刻，那数组就更适合。

应用

1.如何分别用链表和数组实现LRU缓冲淘汰策略？
1）什么是缓存？
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
2）为什么使用缓存？即缓存的特点
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。
3）什么是缓存淘汰策略？
指的是当缓存被用满时清理数据的优先顺序。
4）有哪些缓存淘汰策略？
常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。
5）链表实现LRU缓存淘汰策略
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。
6）数组实现LRU缓存淘汰策略
方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）
2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如 上海自来水来自海上）
1）前提：字符串以单个字符的形式存储在单链表中。
2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3）将链表中的字符倒序存储一份在另一个链表中。
4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。
六、设计思想
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

三、队列

• 什么是队列:

队列是一种受限的线性表数据结构,只支持两个操作:

入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

特点:

1 . 队列跟栈一样,也是一种抽象的数据结构。

2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

 

实现:

队列可以用数组来实现,也可以用链表来实现。

用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。

同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

基于数组的队列:

代码代码

实现思路:

实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

 

随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

基于链表的实现: 

需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

循环队列:

我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。

我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:

队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,

就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

解决浪费一个存储空间的思路:定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++

阻塞队列和并发队列(应用比较广泛)

阻塞队列其实就是在队列基础上增加了阻塞操作。

简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

小结:

队列最大的特点就是先进先出,主要的两个操作是入队和出队。

它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。
 

---

1、线性表的定义

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

首先它是一个序列。即，元素之间是有顺序的，如果存在多个元素，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。（通俗点讲就是线性表中有一个元素打头，有一个元素收尾，表中的每一个元素都知道它前一个是谁，后一个是谁，如同有一根线把他们串联起来了。）

然后线性表强调是有限的，表中的元素个数必定是有限的。那种无线的数列只存在于数学的概念中。

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

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

ADT线性表（List）
Data
	线性表的数据对象集合为{a1, a2,......,an}，每个元素的类型均为
	DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，
	出最后一个元素an外，每一个元素有且只有一个直接后继元素。
	数据元素之间的关系是一对一的对应关系。
Operation
	InitList(*L):初始化操作，建立一个空的线性表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的元素个数。
endADT

例：实现两个线性表集合A和集合B的并集操作，即使得A=AUB。
要实现这个操作，我们就需要把存在B中但不存在A中的数据元素插入到A中即可。

/*将所有在线性表B中但不在线性表A中的数据元素插入到A中*/
void unionL(SqList *A, SqList B)
{
	int a_len, b_len, i;  
	ElemType e;  //声明与A和B相同的数据元素e
	a_len = ListLength(*A);  //求线性表长度
	b_len = ListLength(B);
	for(i=1; i<=b_len; i++)
	{
		GetElem(B, i, &e);  //取B中第i个元素赋给e
		if(!LocateElem(*La, e))  //A中不存在和e相同的数据元素
			ListInsert(A, ++a_len, e);  //插入
	}
}

注意一个很容易混淆的地方：
当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。
如果需要被改动，则需要传递指向这个参数的指针。
如果不用被改动，可以直接传递这个参数。

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

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

顺序存储的结构代码

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

可以看出顺序存储结构需要三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
• 线性表最大存储容量：数组长度MAXSIZE。
• 线性表当前长度：length。

注意：“数组的长度”和“线性表的长度”需要区分开来。
数组的长度是存放线性表的存储空间的长度，内存分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的总个数，随着线性表的插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。

3.1、顺序存储结构的元素地址计算方法

线性表的起始为1，可数组却是从0开始第一个下标的，所以线性表的第 i 个元素存储在数组下标为 i-1 的位置。
假设某线性表占用的是 c 个存储单元，那么线性表中第 i +1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系。(LOC表示获得存储位置的函数）
LOC( i )=LOC( i )+c
所以对于第 i 个数据元素的存储位置可以由第一(或第n)个数据元素的存储位置推出。
LOC( 1 )=LOC(1)+( i-1 )*c

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

获得元素操作

//初始条件：线性表L已存在，1<=i<=ListLength(L)
//操作结果：永e返回L中第i个元素的值，注意i是指位置，
//第一个位置的数组元素下标为0.
typedef int Status;
Status GetElem(SqList L,int i,ElemType *e)
{
	if(L.length==0 || i<1 || i>L.length)
		return 0;
	*e = L.data[i-1];
	return 1;
}

注意，这里是把指针 *e 的值修改成L.data[i-1],这就是真正要返回的数据，函数的返回值只不过是函数的处理状态，返回类型是函数的数据类型。

插入操作

插入算法的思路：

• 如果插入位置不合理，抛出异常
• 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量
• 从最后一个元素开始向前遍历到第 i 个位置，分别将他们都向后移动一位
• 将要插入的元素填入位置 i 处
• 表长加1

//操作结果：在L中第 i 个位置插入新的数据元素e，L的长度加1
Status ListInsert(SqList* L, int i, ElemType e)
{
	int k;
	if(L.length>=MAXSIZE)
		return 0;
	if(i<1 || i>L.length+1)
		return ;
	if(i<=L->length)
	{
		for(k=L->length;k>i;k--)
			L->data[k+1]=L->data[k];
	}
	L->data[i-1] = e;
	L->length++;
	return 1;	
}

删除操作

删除算法的思路：

• 如果删除位置不合理，抛出异常
• 取出删除元素
• 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置
• 表长减1

//操作结构：删除L的第i个数据元素，并用e返回其值，L长度减1
Status ListDelete(SqList* L, int i,ElemType *e)
{
	int k;
	if(L->length==0)
		return 0;
	if(i>L->length || i<1)
		return 0;
	*e = L->data[i-1];
	if(i<L->length)
	{
		for(k=i;k<L->length;k++)
			L->data[k-1]=L->data[k];
	}
	L->length--;
	return 0;
}

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

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任意位置的元素

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，无法确定存储空间的容量
• 造成存储空间的“碎片”

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

定义

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

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

我们把这两部分组成数据元素的存储映像，称为结点。
结点中存储数据元素信息的域称为数据域；存储直接后继元素位置的域称为指针域。指针域中存储的信息称为指针或链。

n个结点链接成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

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

线性链表的最后一个结点指针为空（通常用NULL表示）

有时，我们为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。

头节点的数据源可以不存储任何信息，也可以存储如线表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

结点由存放数据元素的数据域和存放后继结点的指针域组成

头指针与头节点的异同

头指针：

• 头指针是指指向链表第一个结点的指针，若链表有头节点，则是指向头节点的指针
• 头指针具有标志作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的比要元素。

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作就与其他结点的操作统一了
• 头结点不一定是链表必需要素

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

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

1号Node和2号Node等同，3号Node与它们均不等同。

单链表的读取

获得链表第 i 个数据的算法思路

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

//操作结果：用 e 返回 L 中第 i 个元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
	int j=1;
	LinkList p;
	p=L->next;
	while(p && j<i)
	{
		p=p->next;
		++j;
	}
	if(!p || j>i)
		return 0;
	*e = p->data;
	return 1;
}

这里p为结构指针，同时也是结点。

单链表的插入和删除

单链表第 i 个位置插入结点的算法思路：

1. 声明一指针 p 指向链表头结点，初始化 j 从1开始
2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加1
3. 若到链表末尾 p 为空，则说明第 i 个结点不存在
4. 否则查找成功，在系统中生成一个空结点 s
5. 将数据元素 e 赋值给 s->data

//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加 1
Status ListInsert(LinkList *L,int i,ElemType e)
{
	int j=1;
	LinkList p,s;
	P = *L;		//p指向链表头结点
	while(p && j<i)		//寻找第 i-1 个结点
	{
		++j;
		p=p->next;
	}
	if(!p || j>i)		//第i个元素不存在
		return 0;
	s = (LinkList)malloc(sizeof(Node));  //生成新节点
	s->data = e;
	s->next = p->next;	//将P的后继结点赋值给s的后继
	p->next = s;		//将s赋值给p的后继
	return 1;
}

下面两行是插入的精髓，注意顺序不可错乱。

//把新的数据元素插入到第 i 个位置
s->next = p->next;
p->next = s;

单链表的删除

单链表第 i 个位置删除结点的算法思路：

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

//操作结果：删除L第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j=1;
	LinkList p,q;
	p=*L;
	while(p->next || j<i)	//寻找第 i 个元素
	{
		p=p->next;
		j++;
	}
	if(!(p->next) || j>i)	//第 i 个元素不存在
		return 0;
	q = p->next;	//p->next为第i个元素
	p->next = q->next;
	*e = q->data;
	free(q);
	return 1;
}

//将第i个元素的后继赋值为第i-1个元素
q = p->next;	//p->next为第i个元素
p->next = q->next;

单链表的整表创建

单链表的整表创建的算法思路：

1. 声明一指针p和计数器变量
2. 初始化一空链表L
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
4. 循环
   （1）生成一新结点赋值给p
   （2）随机生成一数字赋值给p的数据域p->data
   （3）将p插入到头结点与前一结点之间

//头插法
//随机产生n个元素的值，建立带头结点的单链线性表L
void CreatListHead(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=(LimkList)malloc(sizeof(Node)); //生成新结点
		p->data = rand()%100+1;	//随机生成100以内的数字
		p->next = (*L)->next;
		(*L)->next = p;		//插入到表头
	}
}

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

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

单链表的整表删除

单链表的整表删除算法思路如下：

1. 声明一指针p和q
2. 将第一个结点赋值给p
3. 循环
   （1）将下一结点赋值给q；
   （2）释放p；
   （3）将q赋值给p；

Status ClearList(LinkList *L)
{
	LinkList p,q;
	p=(*L)->next;	//p指向第一个结点
	while(p)	//没到表尾
	{
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL;	//头结点指针域为空
	return 0;
}

或许有的人认为 q 变量没有存在的必要，在循环体内直接写
free(p）；
p->next;
即可。
要知道p指向一个结点，它除了有数据域，还有指针域。在进行free(p）；时，其实是在对它整个结点进行删除和内存释放的工作。变量q使得下一个结点是谁得到记录，以便等当前结点释放后，把下一结点拿回来补充。

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

存储分配方式

• 顺序存储结构用一段连续存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

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

空间性能

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

通过上面的对比，我们可以得出以下结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构，若需要频繁查找和删除时，宜采用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好采用单链表结构。

5、静态链表

用数组来代替指针来描述单链表。
这种用数组描述的链表叫静态链表

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

#define MAXSIZE 1000 //存储空间初始分配量

/线性表的静态链表存储结构
typedef Struct
{
	ElemType data;
	int cur;
}Component,StaticLinkList[MAXSIZE];

另外我们对数组第一个元素和最后一个元素作为特殊元素处理，不存数据；数组中最后一个有值元素的cur设置为0；我们通常把未被使用的数组元素称为备用链表。而数组的第一个元素，即下表为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的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;	//目前静态链表为空，最后一个元素的cur为0
	return 1;
}

假设我们已经将数据存入静态链表，比如分别存放着"A" “B” “C” "D"等数据，此时"A"这里就存有下一个元素"B"的游标2，"B"则存有下一元素"C"的游标3。而"D"是最后一个有值元素，所以它的cur设置为0。而最后一个元素的cur则因为"A"是第一个有值元素而存有它的下标1。而第一个元素则因为空闲空间的第一个元素下标为5，所以它的cur为5。

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。即自己实现malloc()和free()两个函数。

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

那么既然下标为5的分量准备要使用了，就得有接替者，所以就把分量5的cur值赋值给头元素，也就是把6给space[0].cur，之后就可以继续分配新的空闲分量，实现类似malloc()函数的作用。

int Malloc_SSL(StatusLinkLint space)
{
	int i = space[0].cur;	//当前数组第一个元素cur存的值就是要返回第一个备用空闲的下标
	if(space[0].cur)
		space[0].cur = space[i].cur;	//由于要拿出一个空闲分量来使用了，所以我们就得把它的下一个分量用来做备用。
	return i;
}

若新元素"E"想要插队到"B" "C"中间，那么就需要让"E"先在最后一排第5个游标的位置待着，然后把"B"的cur改为5，再把"E"的cur改为3。这样下来，就实现了插队。

/*  在L中第i个元素之前插入新的数据元素e   */
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
		L[j].data = e;   /* 将数据赋值给此分量的data */
		for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
		   k = L[k].cur;           
		L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
		L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
		return 1;   
    }   
    return 0;   
}

静态链表的删除操作

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

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

/*  删除在L中第i个数据元素   */
Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   //最后一个元素下标
    for (j = 1; j <= i - 1; j++)   //获得第i-1个元素下标
        k = L[k].cur;   
    j = L[k].cur;   //j为第i个元素下标
    L[k].cur = L[j].cur;   //第i个元素被删除了，将它的cur赋值给第i-1个元素的cur
    Free_SSL(L, j);   
    return 1;   
} 

求L中数据元素个数的算法：

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

线性表的优缺点

优点
在插入和删除操作时只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。
缺点
没有解决连续存储分配带来的表长难以确定的问题；失去了链式存储结构随机存储的特性。

6、循环链表

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

为了使空链表与非空链表处理一致， 我们通常设个头结点， 当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如下图所示。

对于非空的循环链表就如下图所示。

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断
p->next是否为空，现在则是p-> next不等于头结点，则循环未结束。
在单链表中，我们有了头结点时，我们可以用0(1)的时间访问第一个结点， 但对于要访问到最后一个结点， 却需要0(n)时间，因为我们需要将单链表全部扫描一遍。
有没有可能用0(1)的时间由链表指针访问到最后一个结点呢? 当然可以。
不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表(如下图所示)，此时查找开始结点和终端结点都很方便了。

从上图中可以看到，终端结点用尾指针rear指示，则查找终端结点的时间复杂度是0(1),而开始结点，其实就是rear->next->next, 其时间复杂也为0(1)。
举个程序的例子，要将两个循环链表合并成一一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB,如下图所示。

要想把它们合并，只需要如下的操作即可。

p = rearA->next;	//保存A表的头结点，即上图 1
rearA->next = rearB->next;	//将原本是指向B表的第一个结点（不是头结点），赋值给rearA->next,即上图 2
q = rearB->next;
rearB->next = p;	//将原A表的头结点赋值给rearB->next,即上图 3
free(q);

7、双向链表

我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为0(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

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateElem等，这些操作都只要涉及-一个方向的指针即可，另指针多了也不能提供什么帮助。
就像人生一样，想享乐就得先努力，欲收获就得付代价。双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价: 在插入和删除时，需要更改两个指针变量。
插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。
我们现在假设存储元素e的结点为s,要实现将结点s插入到结点p和p -> next之间需要下面几步，如下图所示。

s->prior = p;	//把p赋值给s的前驱，如上图 1
s->next = p->next;	//把p->next赋值给s的后继，如上图 2
p->next->prior = s;		//把s赋值给p->next的前驱，如图中 3 
p->next = s;	//把s赋值给p的后继，如图中4

关键在于它们的顺序，由于第②步和第③步都用到了p->next。如果第④步先执行，则会使得p >next提前变成了s，使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础_上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。
如果插入操作理解了，那么删除操作，就比较简单了。
若要删除结点p，只需要下面两个步骤，如下图所示。

p->prior->next = p->next;	//把p的后继指针赋值给p->prior的后继，上图 1
p->next->prior = p->prior;	//把p的前驱指针赋值给p->next的前驱，上图 2
free(p);