链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立数据元素之间的线性关系，对每个数据元素ai,除了存放数据元素的自身信息ai之外，还需要存放和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个"节点"（如图），存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此，n个元素的线性表通过每个节点的指针域拉成了一条"链子"， 称之为链表。因为每个节点中只有一个指向后继的指针，所以称之为单链表。
链表是由一个个节点构成，节点定义如下：
typedef struct node
{
datatype data;
struct node *next;
}LNode, *LinkList;
定义指针变量： LinkList H;
下图分别是带头节点的单链表空表和非空表的示意图
注：LNode是节点的类型，LinkList是指向LNode类型节点的指针类型。
在操作中需要用到某节点的指针变量时， 做如下声明是等价的。
LNode *p; 等价于 LinkList H;
p = malloc(sizeof(LNode)); 表示申请一块LNode类型的存储单元，并将这块存储空间的地址赋值给变量p. p所指的节点为*p, *p的类型为LNode型，所以该节点的数据域为(*p).data 或 p->data, 指针域为(*p)->next, 或 p->next。
存储空间的分配和释放
1.存储空间分配函数原型： void *malloc(unsigned int size);
作用是在内存中动态获取一个大小为size个字节的连续的存储空间。并返回一个void类型的指针，若分配成功，该指针指向已分配空间的起始地址，否则，该指针将为空（NULL）
2.连续空间分配函数原型： void *calloc(unsigned, n unsigned size);
作用是在内存中动态获取n个大小为size个字节的连续的存储空间。 该函数将返回一个void类型指针，若分配成功，该指针指向已分配空间的首地址，否则返回空（NULL）。用calloc()可以动态获取一个一维数组空间，其中n为数组元素个数，每个数组元素的大小为size个字节。
3.空间释放函数原型：void free(void *addr);
free()的作用是释放由addr指针所指向的空间，即系统回收，使这段空间又可以被其它变量所用。
建立和输出链表
所谓动态建立链表是指在程序执行过程中从无到有地建立链表，将一个个新生成的节点依次链接入已建立起来的链表上。上一个节点的指针域存放下一个节点的起始地址，并给各个节点数据域赋值。
例如，建立一个学生成绩的链表，其节点的结构体定义如下：
struct student
{
long num;
char name[20];
float score;
struct student *next;
};
4步建立链表：
1.定义三个指针变量，head头指针，p1指向新节点，p2指向尾节点
2.产生一个节点， head ， p1和p2都指向它，并输入想要的数据。
3.循环操作，陆续产生新节点，输入数据，链接到表尾
4.最后，尾节点指针域置空，返回头指针。
create()函数创建链表， 返回链表头指针：
struct student *create()
{
struct student *p1, *p2, *head;
int i, n = 2;
head = NULL;
head = p1 = p2 = (struct student *) malloc(sizeof(struct student));
if(!head) return false; //检测内存空间是否申请成功
printf("input num name score
");
scanf("%ld%s%f",&p1->num,&p1->name,&p1->score);
for(int i = 1; i<n; i++)
{
p1= (struct student *)malloc(sizeof(struct student));
if(!p1) return false;
scanf("%ld%s%f",&p1->num,&p1->name,&p1->score);
p2->next = p1;
p2 = p1;
}
p2->next = NULL;
return head;
}
利用print()函数输出链表数据：
void print(struct student *p)
{
while(p != NULL)
{
printf("ID: %ld Name: %10s score:%6.2f
",p->num,p->name,p->score);
p=p->next;
}
}
最后在main函数中完成调用工作：
int main(void)
{
struct student *head;
head = create();
print(head);
fflush(stdin);
getchar();
}
单链表的基本操作
1.插入。
如果要在单链表的两个数据元素之间插入一个数据元素x,已知p为其单链表存储结构中指向节点a的指针（如图(a)），为插入数据元素x,首选要生成一个数据域为x的节点，然后插在单链表中，插入前需要修改节点a中的指针域，令其指向节点x,而节点x中的指针域应指向节点b，从而实现三个元素a,b和x之间逻辑关系的变化。插入单链表如图（b),假设s为指向节点x的指针，则上述过程可表述如下：
s->next = p->next;
p->next = s;
图（a)
图（b）
2.删除
要删除单链表中的元素x，仅需要把x节点的指针域目前保存的它的下一个节点b的地址赋值给a节点的指针域即可。 假设p,q分别是指向a,x节点的指针，则:
p->next = q->next;
free(q);
3.查找
链表查找是指在链表中查找某成员值为给定值的节点。下面定义一个查找函数，它的返回值即为指向查找到的节点的指针。查找方法是先输入要查找的给定值，然后从链表的头指针所指的第一个节点开始，按链接顺序逐一比较：当查找到给定值的节点时，则返回该节点，否则返回空指针。
struct student *find(struct student *p)
{
long num;
printf("Input the std ID :");
scanf("%ld",&num);
while(p != NULL)
{
if(num == p->num) return p;
p = p->next;
}
return NULL;
}
双链表
单链表的节点中只有一个指向其后继节点的指针域next， 因此，若已知某节点的指针为p， 其后继节点的指针则为p->next， 而找其前驱则只能从该链表的头指针开始，顺着各节点的next域进行，也就是说找后继的时间性能是O(1),而找前驱的时间性能是O(n) , 如果希望找前驱的时间性能达到O（1），则只能付出空间代价：每个节点再加一个指向前驱的指针域，节点的结构如图（1），用这种节点组成的链表称为双向链表：
双链表节点的定义如下：
typedef struct dlnode
{
datatype data;
struct dlnode *prior , *next;
}DLNode , *DLinkList;与单链表类似，双向链表通常也是用头指针标识，也可以带头节点和作成循环结构，图2是带头节点的双向链表图。显然通过某节点的指针p即可以直接得到它的后继节点指针p->next和前驱节点p->prior. 假设p是指向双向循环链表中的某一节点的指针，则p->prior->next表示的是*p节点的前驱节点的后继节点的指针，即与p相等。
