前一小节介绍使用数组实现了线性表，这一小节使用指针来实现：
先看那12个函数：
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode
{
//存放的数据
ElemType data;
//指向下个节点的指针
LNode *next;
}LNode,*LinkList;
//初始化链表
bool initList(LinkList *lst)
{
*lst = (LinkList)malloc(sizeof(LNode));
if(NULL == lst)
return false;
(*lst)->next = NULL;
return true;
}
//删除链表
void deleteList(LinkList *lst)
{
LinkList p = (*lst)->next;
LinkList q;
while(p)
{
q = p->next;
free(p);
p = q;
}
free(*lst);
*lst = NULL;
}
//清空链表
void clearList(LinkList *lst)
{
LinkList p = (*lst)->next;
LinkList q;
while(p)
{
q = p->next;
free(p);
p = q;
}
(*lst)->next = NULL;
}
//判断链表是否为空
bool is_empty(LinkList *lst)
{
if(NULL == (*lst)->next)
{
printf("the list is empty! \n");
return true;
}
else
{
printf("the list is not empty! \n");
return false;
}
}
//遍历链表并打印
void printList(LinkList *lst)
{
printf("list elements are: ");
LinkList p = (*lst)->next;
while(p)
{
printf("%d",p->data);
p = p->next;
}
printf("\n");
}
//计算链表中的元素个数
int listLength(LinkList *lst)
{
int cnt = 0;
LinkList p = (*lst)->next;
while(p)
{
++cnt;
p = p->next;
}
return cnt;
}
//在指定位置插入元素
bool insertElem(LinkList *lst,int index,ElemType *e)
{
int cnt = 0;
LinkList p = (*lst);
LinkList q = (LinkList)malloc(sizeof(LNode));
while(p)
{
if(index == cnt)
{
//新插入节点的指针指向当前节点的指针指向的元素
q->next = p->next;
//当前节点的指针指向新插入的节点
p->next = q;
//存入数据
q->data = *e;
return true;
}
++cnt;
p = p->next;
}
return false;
}
//删除某个位置的元素
bool deleteElem(LinkList *lst,int index,ElemType *e)
{
int cnt = 0;
LinkList p = (*lst)->next;
//存储当前节点的前一个节点
LinkList q = *lst;
while(p)
{
if(index == cnt)
{
//获取即将删除的节点的元素
*e = p->data;
//当前节点的前一个节点指向当前节点的后一个节点
q->next = p->next;
//释放当前节点
free(p);
break;
}
p = p->next;
q = q->next;
++cnt;
}
return false;
}
//获取某个元素的位置
int locateElem(LinkList *lst,ElemType e)
{
int index = 0;
LinkList p = (*lst)->next;
while(p)
{
if(e == p->data)
return index;
++index;
p = p->next;
}
return -1;
}
//获取某个位置的元素
bool getElem(LinkList *lst,int index,ElemType *e)
{
int cnt = 0;
LinkList p = (*lst)->next;
while(p)
{
if(index == cnt)
{
*e = p->data;
return true;
}
++cnt;
p = p->next;
}
return false;
}
//获取下一个元素
bool nextElem(LinkList *lst,ElemType curr,ElemType *nxt)
{
LinkList p = (*lst)->next;
while(p)
{
if(curr == p->data)
{
*nxt = p->next->data;
return true;
}
p = p->next;
}
return false;
}
//获取前一个元素
bool priorElem(LinkList *lst,ElemType curr,ElemType *pre)
{
LinkList p = (*lst)->next;
LinkList q = (*lst);
while(p)
{
if(curr == p->data)
{
*pre = q->data;
return true;
}
q = q->next;
p = p->next;
}
return false;
}
void inputList(LinkList *lst,int n,int* arr)
{
for(int i = n-1; i >= 0; --i)
{
LinkList pnew = (LinkList)malloc(sizeof(LNode));
pnew->data = arr[i];
pnew->next = (*lst)->next;
(*lst)->next = pnew;
}
}
其中最后一个并不是必须的，只为了输入的时候方便。
对指针不太熟悉的朋友可能有点不明白参数是怎么传递的，这里通过一个具体的例子来说明一下。
void reset(int *x)
{
*x = 0;
}
在主函数中：
int a = 1;
printf("before reset: %d\n",a);
reset(&a);
printf("after reset: %d\n",a);
这个程序相信大家都见过，但是我还是要仔细地说明一下编译器是怎么对待函数调用的：它会将实参复制一份给形参，然后对形参进行操作。所以，形参的改变是不会影响实参的，如果想改变主调函数中某个实参的值，必须将它的地址传递给被调函数—虽然这里还是会发生实参复制给形参的情况，但是由于复制的是地址，所以被掉函数中，只要对地址进行解引，就能操作主调主调函数中的值了。
再来看我们的程序：
typedef struct LNode
{
ElemType data;
LNode *next;
}LNode,*LinkList;
定义了指向结构体的指针，当我们的操作并不需要修改指针本身时，我们大可以传递指针本身：
//判断链表是否为空
bool is_empty(LinkList lst)
{
if(NULL == (lst)->next)
{
printf("the list is empty! \n");
return true;
}
else
{
printf("the list is not empty! \n");
return false;
}
}
但是如果我们的操作需要修改这个指针时，那么我们只能给函数传递这个指针的地址，然后在函数中通过解引操作“*”来或得指针本身，然后在进行内存分配、插入、删除等操作。所以我们的很多函数的型参都有LinkList *lst。而在主函数中，将这个指针的地址传递给函数，比如initList(&myList);
与“值”传递相比，传递指针看上去很麻烦，但是它有一个明显的效率优势：当直接传递值时，会复制一个值，如果复制的是一个复杂的结构体，那么代价是非常大的；但如果复制的仅仅是一个指针，那么只需要4个字节（因为我们的电脑是32位的，所以地址也是32位，就是4个字节）。
相比之下，如果使用C++中的“引用”概念就要方便的多：直接将实参与形参关联起来，通过形参的改变，就能改变实参，而且并没有任何“复制”发生。
与数组实现的线性表相比，链表的优势在于可以方便的插入、删除元素；但是对于随机访问某个元素，却非常缓慢，必须要通过从头开始遍历整个链表开始，所以程序中总是出现
LinkList p = l->next;
while(p)
{
//具体操作
p = p->next;
}
的结构。总体上来说，二者各有利弊，如果的数据需要频繁的插入、删除，那么选择链表；如果需要频繁的随机范文，那么选择顺序表。
其实链表还有另外几种复杂的结构，比如：循环链表、双向链表、双向循环链表等等，由于基本的原理是相同的，这里只对他们进行简要的介绍。
循环链表很简单，就是最后一个节点的指针next重新指向链表头。它的好处在于不论你现在处于链表的什么位置，总能遍历到链表的所有元素。程序部分的改动也比较小，主要是在初始化时，将next指向链表头，在遍历链表的过程中，循环的停止条件变为：while(p != (*lst))。
双向链表是在基本链表的基础上，增加一个指向前一个节点的指针prior，在插入、删除操作时，指针的指向需要仔细：
#include <stdio.h>
#include <malloc.h>
#define ElemType int
typedef struct DNode
{
ElemType data;
DNode *next;
DNode *prior;
}DNode,*DLinkList;
bool initDList(DLinkList* dlst)
{
*dlst = (DLinkList)malloc(sizeof(DNode));
if(*dlst == NULL)
return false;
(*dlst)->next = NULL;
(*dlst)->prior = NULL;
return true;
}
void deleteDList(DLinkList* dlst)
{
DLinkList p = (*dlst)->next;
DLinkList q;
while(p)
{
q = p->next;
free(p);
p = q;
}
free(*dlst);
*dlst = NULL;
}
bool insertElem(DLinkList* dlst,int index,ElemType e)
{
int cnt = 0;
DLinkList p = *dlst;
while(p)
{
if(index == cnt)
{
DLinkList pnew = (DLinkList)malloc(sizeof(DNode));
pnew->data = e;
pnew->next = p->next;
pnew->prior = p;
p->next = pnew;
//注意：当第一次插入元素或者在最后一个位置插入元素时，p->next是空的，并没有节点
if(pnew->next!=NULL)
pnew->next->prior = pnew;
return true;
}
p = p->next;
++cnt;
}
return false;
}
void deleteElem(DLinkList* dlst,int index,ElemType *e)
{
int cnt = 0;
DLinkList p = (*dlst)->next;
while(p)
{
if(index == cnt)
{
*e = p->data;
p->prior->next = p->next;
//如果删除的是链表末尾的元素，则不需要这个步骤
if(p->next != NULL)
p->next->prior = p->prior;
free(p);
break;
}
++cnt;
p = p->next;
}
}
void printList(DLinkList* dlst)
{
printf("elements are: ");
DLinkList p = (*dlst)->next;
while(p)
{
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
这里给出了比较详细的代码。尤其需要注意，当你第一次向链表中插入元素，或者插入元素的位置在链表的末尾，或者删除链表的最后一个元素时，此时p->是为NULL的，所以不能取p->next->prior 。