1. 链表的定义
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存在内存中未被占用的任意位置。
（比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址(指针)。也就是说除了存储其本身的信息外,还需存储一个指示其直接后继的存储位置的信息。）
我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像,称为结点 (Node) 。
n 个结点链接成一个链表,即为线性表 (a1, a2,a3, ..., an) 的链式存储结构。因为此链表的每个结点中只包含一个指针域,所以叫做单链表。见如下图：
2. 头指针和头结点
2.1 头指针：
1）头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。
2）头指针具有标识作用,所以常用头指针冠以链表的名字(指针变量的名字)。
3）无论链表是否为空,头指针均不为空。
4）头指针是链表的必要元素。
2.2 头结点
1）头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(但也可以用来存放链表的长度)。
2）有了头结点,对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
3）头结点不一定是链表的必须要素。
3. 单链表的存储结构
3.1我们在 C 语言中可以用结构指针来描述单链表。见例1.
//例1
typedef struct Node
{
ElemType data; // 数据域
struct Node* Next; // 指针域
} Node;
typedef struct Node* LinkList;
（注：我们看到结点由存放数据元素的数据域和存放后继结点地址的指针域组成。）
假设 p 是指向线性表第 i 个元素的指针,则该结点 ai 的数据域我们可以用 p->data 的值是一个数据元素,结点 ai 的指针域可以用 p->next 来表示, p->next 的值是一个指针。那么 p->next 指向 ai+1 的指针。
4. 单链表的读取
获得链表第 i 个数据的算法思路:
1）声明一个结点 p 指向链表第一个结点,初始化 j 从1 开始;
2）当 j<i 时,就遍历链表,让 p 的指针向后移动,不断指向一下结点, j+1 ;
3）若到链表末尾 p 为空,则说明第 i 个元素不存在;
4）否则查找成功,返回结点 p 的数据。
（注：由于这个算法的时间复杂度取决于 i 的位置,当i=1 时,则不需要遍历,而 i=n 时则遍历 n-1 次才可以。因此最坏情况的时间复杂度为 O(n) 。见例2）
//例2.
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) /
/ 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem( LinkList L, int i, ElemType *e )
{
int j;
LinkList p;
p = L->next;
j = 1;
while( p && j<i )
{
p = p->next;
++j;
}
if( !p || j>i )
{
return ERROR;
}
*e = p->data;
return OK;
}
5. 单链表的插入
单链表第 i 个数据插入结点的算法思路:（见例3.）
1）声明一结点 p 指向链表头结点,初始化 j 从 1 开始;
2）当 j<1 时,就遍历链表,让 p 的指针向后移动,不断指向下一结点, j 累加 1 ;
3）若到链表末尾 p 为空,则说明第 i 个元素不存在;
4）否则查找成功,在系统中生成一个空结点 s ;
5）将数据元素 e 赋值给 s->data ;
6）单链表的插入刚才两个标准语句;
7）返回成功。
//例3.
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) /
/ 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 /
Status ListInsert(LinkList * L, int i, ElemType e) /注：这里的LinkList表示的是“ struct Node* LinkList”*/
{
int j;
LinkList p, s;
p = *L;
j = 1;
while( p && j<i ) // 用于寻找第i个结点
{
p = p->next;
j++;
}
if( !p || j>i )
{
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
（注意：必须先“s->next = p->next;”， 再“p->next = s;”。 因为如果先执行“ p->next = s”的话“ p->next ”会先被覆盖为 “s” 的地址,那么” s->next = p->next “其实就等于 “s->next = s” 了。）
6. 单链表的删除
单链表第 i 个数据删除结点的算法思路:（见例4）
1）声明结点 p 指向链表第一个结点,初始化 j=1 ;
2）当 j<1 时,就遍历链表，让 P 的指针向后移动，不断指向下一个结点, j 累加1 ;
3）若到链表末尾 p 为空，则说明第 i 个元素不存在;
4）否则查找成功，将欲删除结点 p->next 赋值给 q ;
5）单链表的删除标准语句 p->next = q->next ;
6）将 q 结点中的数据赋值给 e ，作为返回;
7）释放 q 结点。
//例4
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) /
/ 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while( p->next && j<i )
{
p = p->next;
++j;
}
if( !(p->next) || j>i )
{
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
7. 单链表的整表创建
7.1 概念：链表的各个元素分布在在内存各个角落的,他的增长也是动态的。对于链表来说,它所占用空间的大小和位置是不需要预先分配划定的,可以根据系统的情况和实际的需求即时生成。
创建单链表的过程是一个动态生成链表的过程,从“空表”的初始状态起，依次建立各元素结点并逐个插入链表。所以单链表整表创建的算法思路如下:
1）声明一结点 p 和计数器变量 i ;
2）初始化一空链表 L ;
3）让 L 的头结点的指针指向 NULL ,即建立一个带头结点的单链表;
4）循环实现后继结点的赋值和插入。
7.2 单链表创建
单链表整表创建有两种方式：1）头插法；2）尾插法
1）头插法
头插法从一个空表开始,生成新结点,读取数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。简单来说,就是把新加进的元素放在表头后的第一个位置:（见例5）
（1）先让新节点的 next 指向头节点的next;(例5还提供一个版本是没有头结点，即第一个节点即为数据节点)
（2）然后让头节点的 next 指向新节点。（没有头结点的话，头指针直接指向最后一个插入的数据节点。）
//例5
/#include<stdio.h>
/#include<stdlib.h>
typedef void Status;
typedef int Elemtype;
typedef struct node
{
Elemtype data;
struct node *next;
}Node;
Status Visit(Node *node)
{
if(node)
{
printf("%d", node->data);
}
}
Status Traversal(Node **node)
{
Node *target;
target = *node;
while(target)
{
Visit(target);
target = target->next;
}
}
Status InitLinkList(Node * * node)
{
*node = (Node )malloc(sizeof(Node));
( * node)->next = NULL;
}
Status CreateLinkList(Node * * node, int i) //有头结点版本
{
Node * temp;
int j;
( * node)->data = i; //头结点存储链表长度
for(j = 1; j <= i; j++)
{
(temp) = (Node * )malloc(sizeof(Node));
(temp)->data = j;
(temp)->next = (node)->next;
( * node)->next = (temp);
}
}
Status CreateLinkList2(Node **node, int i) //无头结点版本
{
Node temp;
int j;
if(i >= 1)
{
( * node)->data = 1;
for(j = 2; j <= i; j++)
{
temp = (Node * )malloc(sizeof(Node));
temp->data = j;
temp->next = (node);
( * node) = temp;
}
}
else
{
printf("The LinkList is empty!");
}
}
Status Clear(Node *node)
{
Node * target, temp;
target = ( * node)->next;
while(target)
{
//temp = target->next;
//free(target);
//target = temp; //上下两种都可以
temp = target;
target = target->next;
free(temp);
}
( * node)->next = NULL; //保留头结点
}
void main()
{
Node * node;
InitLinkList(&node);
CreateLinkList(&node, 10);
Traversal(&node);
printf("\n");
//InitLinkList(&node); //可以采用初始化链表方式重新创建链表node
Clear(&node); //也可以采用清空原链表方式
CreateLinkList2(&node, 11); /无头结点版本即将头结点数据域直接覆盖为首节点的数据。/
Traversal(&node);
}
//输出：
10 10 9 8 7 6 5 4 3 2 1 //有头结点
11 10 9 8 7 6 5 4 3 2 1 //无头结点
(注意：空链表必须有头结点，因为有节点才为链表；而非空链表可以有头结点，也可以没有头结点。)
2）尾插法
尾插法就是将新元素按照先来后到的顺序依次插入链表的尾部，见例6.
//例6
/#include<stdio.h>
/#include<stdlib.h>
typedef void Status;
typedef int Elemtype;
typedef struct node
{
Elemtype data;
struct node *next;
}Node;
Status Visit(Node *node)
{
if(node)
{
printf("%d ", node->data);
}
}
Status Traversal(Node **node)
{
Node *target;
target = *node;
while(target)
{
Visit(target);
target = target->next;
}
}
Status InitLinkList(Node **node)
{
*node = (Node *)malloc(sizeof(Node));
( * node)->next = NULL;
}
Status CreateLinklist(Node **node, int i) //有头结点
{
Node *target, *temp;
int j;
target = *node;
target->data = i;
for(j = 1; j <= i; j++)
{
temp = (Node *)malloc(sizeof(Node));
temp->data = j;
target->next = temp;
target = target->next;
}
}
Status CreateLinklist2(Node **node, int i) //无头结点
{
Node *target, *temp;
int j;
target = *node;
for(j = 1; j <= i; j++)
{
if(j == 1)
{
target->data = j; //头结点直接被覆盖为首节点
}
else
{
temp = (Node *)malloc(sizeof(Node));
temp->data = j;
target->next = temp;
target = target->next;
}
}
}
void main()
{
Node *node;
InitLinkList(&node);
CreateLinklist(&node, 10);
Traversal(&node);
printf("\n");
InitLinkList(&node);
CreateLinklist2(&node, 11);
Traversal(&node);
}
//输出：
10 1 2 3 4 5 6 7 8 9 10 //有头结点
1 2 3 4 5 6 7 8 9 10 11 //无头结点
7. 单链表的整表删除
单链表整表删除的算法思路如下:（见例7.）
1）声明结点 p 和 q ;
2）将第一个结点赋值给 p ,下一结点赋值给 q ;
3）循环执行释放 p 和将 q 赋值给 p 的操作。
//例7
Status Clear(Node **node)
{
Node * p, * q;
p = ( * node)->next;
while(p)
{
q= p->next;
free(p);
p = q;
}
( * node)->next = NULL; //保留头结点
}
(可见实例5中的Clear函数)
8. 单链表结构与顺序存储结构优缺点
分别从存储分配方式、时间性能、空间性能三方面来做对比。
8.1 存储分配方式:
1）顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
)2）单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。
8.2 时间性能:
1）查找
• 顺序存储结构 O(1)
• 单链表 O(n)
2）插入和删除
• 顺序存储结构需要平均移动表长一半的元素,时间复杂度为 O(n)
• 单链表在计算出某位置的指针后,插入和删除时间仅为 O(1)
8.3 空间性能:
1）顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出。
2）单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。
8.4 综上所述对比,我们得出一些经验性的结论:
1）若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。
2）若需要频繁插入和删除时,宜采用单链表结构。
