Linux C 数据结构---链表（单向链表）教程
线性表就是数据元素都一一对应，除只有唯一的前驱，唯一的后继。
线性表存储结构分为顺序存储、链式存储。
顺序存储的优点：
顺序存储的缺点：
链表就是典型的链式存储，将线性表L = （a0,a1,a2,........an-1）中个元素分布在存储器的不同存储块，成为结点（Node），通过地址或指针建立他们之间的练习，所得到的存储结构为链表结构。表中元素ai的结点形式如下：
其中，结点的data域存放数据元素ai,而next域是一个指针，指向ai的直接后继a(i+1)所在的结点。于是，线性表L=（a0,a1,......an-1）的结构如图：
一、节点类型描述：
<pre class="has">typedef struct node_t
{
data_t data; //节点的数据域
struct node_t *next;//节点的后继指针域
}linknode_t,*linklist_t;
也可这样表示：
```
struct node_t
{
data_t data;
struct node_t *next;
}
typedef struct node_t linknode_t;
typedef struct node_t *linklist_t;
```
若说明
linknode\_t A;
linklist\_t p = &A;
则结构变量A为所描述的节点，而指针变量P为指向此类型节点的指针（p的值为节点的地址）；
这样看来 linknode\_t linklist\_t 的作用是一样的，那为什么我们要定义两个数据类型（同一种）呢？主要为了代码的可读性，我们要求标识符要望文识义，便于理解；
1、linknode\_t \*pnode 指向一个节点；
2、linklist\_t list 指向一个整体
二、头结点 head
我们在前篇提到的顺序存储线性表，如何表达一个空表{ }，是通过list->last = -1来表现的，所谓的空表就是数据域为NULL，而我们的链表有数据域和指针域，我们如何表现空链表呢？这时，就引入了头结点的概念，头结点和其他节点数据类型一样，只是数据域为NULL，head->next = NULL，下面我们看一个创建空链表的函数，如何利用头结点来创建一个空链表：
```
```
linklist_t CreateEmptyLinklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if (NULL != list) {
list->next = NULL;
}
return list;
}
```
只要头结点，链表就还在！
三、链表基本运算的相关算法
链表的运算除了上面的创建空链表，还有数据的插入，删除，查找等函数，链表的运算有各种实现方法，如何写出一个高效的，封装性较好的函数是我们要考虑的，比如数据插入函数，我们就要尽可能考虑所有能出现的结果，比如：1）如果需插入数据的链表是个空表；2）所插入的位置超过了链表的长度；如果我们的函数能包含所有能出现的情况，不仅能大大提高我们的开发效率，也会减少代码的错误率。下面，我们来看看下面的这个链表的插入函数的实现：
```
```
int InsertLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/*第一步、分配空间*/
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new)
{
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL; /*节点如果插入超过链表长度的位置，会接到尾节点后面，这样，node_new成了尾节点，node_new->next = NULL */
/*第二步、定位*/
node_prev = list;//跟随指针，帮助我们更好的定位
node_at = list->next; //遍历指针
pos_at = 0;
while (NULL != node_at)
{
if (pos_at == at)
{
found = 1; //找到正确的位置，跳出循环
break;
}
/* move to the next pos_at */
node_prev = node_at; //跟随指针先跳到遍历指针的位置
node_at = node_at->next;//遍历指针跳到下一个节点的位置
pos_at++;
}
/*第三步、插入*/
if (found)
{
/* found = 1,找到正确的位置，插入 */
node_new->next = node_at;//插入的节点next指向node_at
node_prev->next = node_new;//插入节点的前一个节点
}
else
{
/*若是没找到正确的位置，即所插入位置超越了链表的长度，则接到尾节点的后面，同样，这样适用于{ }即空链表，这样我们可以建立一个空链表，利用这个函数，实现链表的初始化*/
node_prev->next = node_new;
}
```
这个插入函数可利用性就非常高。
下面讲一个完整链表代码贴出：
listlink.h
```
```
#ifndef _LNK_LIST_H_
#define _LNK_LIST_H_
typedef int data_t;
typedef struct node_t {
data_t data;
struct node_t *next;
} linknode_t, *linklist_t;
linklist_t CreateEmptyLinklist();
void DestroyLinklist(linklist_t list);
void ClearLinklist(linklist_t list);
int EmptyLinklist(linklist_t list);
int LengthLinklist(linklist_t list);
int GetLinklist(linklist_t list, int at, data_t *x);
int SetLinklist(linklist_t list, int at, data_t x);
int InsertLinklist(linklist_t list, int at, data_t x);
int DeleteLinklist(linklist_t list, int at);
linklist_t ReverseLinklist(linklist_t list);
#endif /* _LNK_LIST_H_ */
```
linklist.c
```
```
#include
#include
#include "linklist.h"
linklist_t CreateEmptyLinklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if (NULL != list) {
list->next = NULL;
}
return list;
}
void DestroyLinklist(linklist_t list)
{
if (NULL != list) {
ClearLinklist(list);
free(list);
}
}
void ClearLinklist(linklist_t list)
{
linknode_t *node; /* pointer to the node to be removed */
if (NULL == list) return;
while (NULL != list->next) {
node = list->next;
list->next = node->next;
free(node);
}
return;
}
int LengthLinklist(linklist_t list)
{
int len = 0;
linknode_t *node; //iterate pointer
if (NULL == list) return -1;
node = list->next; // node points to the first data node
while (NULL != node) {
len++;
node = node->next;
}
return len;
}
int EmptyLinklist(linklist_t list)
{
if (NULL != list) {
if (NULL == list->next) {
return 1;
} else {
return 0;
}
} else {
return -1;
}
}
int GetLinklist(linklist_t list, int at, data_t *x)
{
linknode_t *node; /* used for iteration */
int pos; /* used for iteration and compare with */
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
if (NULL != x) {
*x = node->data;
}
return 0;
}
/* move to the next */
node = node->next;
pos++;
}
return -1;
}
int SetLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node; /* used for iteration */
int pos;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
found = 1; /* found the position */
node->data = x;
break;
}
/* move to the next */
node = node->next;
pos++;
}
if (1 == found) {
return 0;
} else {
return -1;
}
}
int InsertLinklist(linklist_t list, int at, data_t x)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
* node_new is used to point to the new node to be inserted.
*/
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new) {
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* insert */
node_new->next = node_at;
node_prev->next = node_new;
} else {
/*
* If not found, means the provided "at"
* exceeds the upper limit of the list, just
* append the new node to the end of the list.
*/
node_prev->next = node_new;
}
return 0;
}
int DeleteLinklist(linklist_t list, int at)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
*/
linknode_t *node_prev, *node_at;
int pos_at;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* remove */
node_prev->next = node_at->next;
free(node_at);
return 0;
} else {
return -1;
}
}
linklist_t ReverseLinklist(linklist_t list)
{
linknode_t *node; /* iterator */
linknode_t *node_prev; /* previous node of iterator */
linknode_t *node_next; /* next node of iterator,
* used to backup next of iterator
*/
if (NULL == list) return NULL;
node_prev = NULL;
node = list->next;
while (NULL != node) {
/*
* step1: backup node->next
* due to the next of iterator will be
* modified in step2
*/
node_next = node->next;
/*
* when iterator reaches the last node
* of original list, make the list head
* point to the last node, so the original
* last one becomes the first one.
*/
if (NULL == node_next) {
list->next = node;
}
/*
* step2: reverse the linkage between nodes
* make the node pointer to the previous node,
* not the next node
*/
node->next = node_prev;
/*
* step3: move forward
*/
node_prev = node;
node = node_next;
}
return list;
}
```
main.c
```
```
#include
#include
#include "linklist.h"
int main()
{
int i;
data_t x;
linklist_t p;
p = CreateEmptyLinklist();
data_t a[10] = {1,3,5,7,9,11,13,15,17,19};
for(i = 0;i < 10;i++)
{
InsertLinklist(p,i,a[i]);
}
ReverseLinklist(p);
printf("The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("The NO.4 of this list is:%d\n",x);
SetLinklist(p,4,100);
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
DeleteLinklist(p,4);
printf("After updating!The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
ReverseLinklist(p);
ClearLinklist(p);
if(EmptyLinklist(p))
printf("This list is empty!\n");
DestroyLinklist(p);
printf("This list is destroyed!\n");
return 0;
}
```
执行结果如下：
```
```
book@ubuntu:~/temp/list$ ./Test
The length of the list is:10
The NO.4 of this list is:11
After updating!The No.4 0f this list is:100
After updating!The length of the list is:9
After updating!The No.4 0f this list is:9
This list is empty!
This list is destroyed!
```