目录

• 单向链表
• 双向链表

链表中的节点和火车的车厢一样，是一个连着一个的，通常将当前节点的前一个或上一个节点称为它的前驱节点，将后一个或者下一个节点称之为它的后继节点。链表中的第一个节点被称为头节点，最后一个节点被称为尾节点。在链表中，头节点是没有前驱的节点，尾节点是没有后继的节点，其它的所有节点都称为中间节点，中间节点都会拥有一个前驱节点和一个后继节点。

单向链表

所谓单向链表，就是每个节点的指针域中只含有一个指向其后续节点指针的链表

在单向链表中，只能从头节点开始，不断地通过指向后续节点的指针，来逐个地向后访问遍历其它链表节点，最后一个节点的指针域为一个空指针，表示其没有后继节点了

为了使用单向链表必须定义相应的节点类型，由于节点具有数据域和指针域两个部分，因此，应该选用结构体来进行定义

struct node{int data;struct node *next;}

定义了结构体node，它有两个成员：int类型的成员data和struct node*类型的成员next
在struct node和next之间有个星号，表示所定义出的成员next是struct node类型的指针。这是允许的
因为指针的大小是固定的，并不会随着指针的类型不同而改变。反之，如果在struct node和next之间没有这个星号就是错误的，C语言中，不允许在结构体的定义中，出现和结构体相同类型的成员，因为要想得知结构体的大小，就得知道其所有成员的大小，而成员的类型又和结构体类型相同，那么若想知道成员的大小，就必须得先知道结构体的大小。这就出现了死锁现象，变成了无限的递归定义，就好像遇见了世界上是先有鸡还是先有蛋的亘古难题

可以将结构体node看成是一个链表的节点类型，数据域部分是成员data，而指针域部分是成员next。为了方便，定义一个创建节点的函数createNode

/*作者：是北豼不太皮吖时间：2022年3月22日10:54:45函数功能：创建节点参数：int val返回值：struct node*成功：pnode失败：NULL说明：createNode函数只有一个int类型的参数val，用于表示新创建节点数据域部分的值，函数返回值为指向新创建节点的指针。在函数体中，首先通过malloc函数在堆中申请分配一块节点大小的内存空间，并让指针pnode指向这块内存。然后通过if语句判断申请分配内存是否成功，若成功则将这块内存作为新创建节点的存储区域，并通过指针pnode来给节点的数据域和指针域部分赋值，即将参数val赋值给成员data，由于此时所创建的是一个单独的节点，并不知道是否会有后续节点，因此，将成员next的值赋为NULL。最后，通过return语句返回指向堆中所创建的节点的指针*/struct node *createNode(int val){struct node *pnode = (struct node*)mslloc(sizeof(struct node));if(pnode != NULL)//判断内存分配是否成功{pnode -> data = val;pnode -> next = NULL;}return pnode;}

下面定义将节点加到链表的函数addNode

/*作者：是北豼不太皮吖时间：2022年3月22日10:55:09函数功能：将节点加到链表参数：struct node **pheadptr,int val返回值：int成功：1失败：0说明：addNode函数有两个参数，其中参数pheadptr是一个二级指针，表示指向链表头节点指针的指针，使用二级指针的目的是为了能在函数中修改实参，而这个实参应为指向链表头节点的指针。另一个参数val是所添加节点的值，即节点的数据域部分。函数的返回值为int类型，值为1表示添加节点成功，值为0表示添加节点失败*/int addNode(struct node **pheadptr,int val){struct node *p = createNode(val);if(p == NULL)//如果创建节点失败return 0;if(*pheadptr == NULL)*pheadptr = p;else{struct node *ptmp  = *pheadptr;while(ptmp->next)ptmp = ptmp->next;ptmp->next = p;}return 1;}

在函数体中，首先以val作为参数，调用createNode函数在堆中创建新节点，并由指针p指向该节点，然后，通过if语句检查新节点是否创建成功，若指针p为空指针，则表示节点创建失败，通过return语句返回0，表示向链表添加节点失败，接着，再通过if…else语句判断指向头节点的指针是否为空指针，由于pheadptr是一个二级指针，因此，对它进行解引用即可访问到实参指针（即指向链表头节点的指针，简称头指针）。若实参指针是空指针，则表示此时的链表是一个空链表，就会将指针p赋值给实参指针，即将新节点作为链表的头节点，并让实参指针指针指向这个新节点，若实参指针不是空指针，即将新节点作为链表并非空链表，就会执行else部分，定义一个临时指针ptmp，并让它指向链表头节点，然后通过while循环语句找到链表的尾节点（即成员next的值为NULL的节点），再将尾节点的成员next赋值为指针p，即表示将原来尾节点作为新创建节点的前驱节点，而新创建节点则成为链表的尾节点了。需要注意的是，在while循环的条件判断处，是通过检查指针ptmp所指向节点的成员next的值是否为空来决定是否执行循环体的，如果指针ptmp所指向节点的成员next的值为空，则表示指针ptmp已经指向了链表的尾节点，此时会终止while循环。如果指针ptmp所指向节点的成员next的值不为空，则会将其成员next的值重新赋值给指针ptmp，即让指针ptmp指向原先节点的后续节点（即下一个节点），并再次执行下轮循环，直到指针ptmp所指向节点的成员next的值为空时止。由于指针ptmp是一个临时指针，因此，在while循环中，对指针ptmp的修改是不会影响到实参指针的，所以要注意它和if部分的指针使用方式的区别；最后，函数通过return语句返回1，表示向链表添加节点成功。由此可见，每次调用addNode函数，都是将新创建的节点添加到链表的尾部

下面定义一个统计链表节点数量的countOfNodes函数

/*作者：是北豼不太皮吖时间：2022年3月22日14:39:04函数功能：统计链表节点数量参数：struct node *headptr返回值：unsigned说明：countOfNodes函数中的形式参数heaptr只是一个普通指针，因此，在while循环体中，对指针headptr的修改不会影响到实参指针*/unsigned countOfNodes(struct node *headptr){unsigned c = 0;while(headptr){++c;headptr = headptr->next;}return c;}

知道了如何统计节点数量，那么想要遍历并打印链表节点就很容易了，可以定义专门用于遍历打印链表节点的函数printAllNodes

/*作者：是北豼不太皮吖时间：2022年3月22日15:32:46函数功能：遍历并打印链表节点参数：struct node *headptr返回值：void说明：和countOfNodes函数的不同之处在于while循环中将变量自增换成了printf函数调用，将指针headptr所指向节点的数据域部分打印输出，并在所有节点打印完毕之后，进行一个执行的操作*/void printAllNodes(struct node *headptr){while(headptr){printf("%d",headptr->data);headptr = headptr->next;}printf("\n");}

对于节点的删除，算是链表中最为复杂的操作之一了。因为链表的节点可能是分散存储于内存的不同地方，靠着节点的指针域来进行节点间的联系，就可能会使链表的整体或部分断裂，造成数据的丢失和内存的泄露。因此，在删除链表节点的同时，要精心维护好节点间的关系

（1）头节点的删除

由于头指针是指向链表头节点的，因此，要想删除头节点，应该先用一个临时指针指向头节点，然后将头指针修改为指向链表第二个节点，最后再通过临时指针将原头节点所占用的内存空间释放回收即可

删除1号节点步骤：
1.用临时指针指向1号节点
2.使头指针指向2号节点
3.通过临时指针释放回收1号节点的内存空间

（2）非头节点的删除

对于非头节点的删除，首先要找到欲删除节点的前驱节点，将其成员next的指针指向欲删除节点的后续节点，然后再将节点删除并释放回收内存空间

删除2号节点步骤：
1.用临时指针指向2号节点
2.使1号节点的next指针指向3号节点
3.通过临时指针释放回收2号节点内存空间

删除链表节点的函数deleteNode

/*作者：是北豼不太皮吖时间：2022年3月22日15:50:52函数功能：删除链表节点（非头节点）参数：struct node **pheadptr,unsigned loc返回值：int成功：1失败：0说明：deleteNode函数有两个参数，由于在头节点的删除中需要修改头指针，因此，参数pheadptr被定义为二级指针，即一个指向头指针的指针，参数loc是unsigned类型的变量，它用来表示欲删除节点的位置，即删除链表中的哪一个节点。函数返回值为int类型，如果节点删除成功返回1，节点删除失败返回0*/int deleteNode(struct node **pheadptr,unsigned loc){unsigned c = countOfNodes(*pheadptr);if(c < loc)return 0;struct node *p = *pheadptr;if(loc == 1){//头节点的删除*pheadptr = (*pheadptr)->next;free(p);}else{//非头节点的删除for(int i = 2;i < loc;++i)p = p->next;struct node *pdel = p->next;p->next  = pdel->next;free(pdel);}return 1;}

在函数体中，首先调用countOfNode函数获取当前链表中的节点数量，并将节点数量保存至变量c中，然后通过if语句检查参数loc的值是否合法，如果loc的值大于链表节点数量，则直接通过return语句返回0，表示删除节点失败；接着定义一个指针p并让其指向链表头节点；再通过if语句检查要删除的节点是否是头节点，若loc的值等于1，则表示对链表头节点的删除，执行if部分，即让头指针指向头节点的后续节点，并调用free函数对原头节点的内存进行回收。若loc的值不等于1，则表示对链表非头节点的删除，会执行else部分，即通过for循环让指针p指向欲删除节点的前驱节点，其中循环变量i是从2开始循环的，例如想删除链表中第2个节点，则该循环的循环体不会被执行，指针p还是指向链表头节点的，而第2个节点的前驱节点就是头节点。接下来再定义一个指针的后续节点，即将欲删除的节点从链表中脱离，并让其前驱节点和后续节点建立联系；最后再调用free函数，释放、回收被删除节点的空间；函数体的最后，通过return语句返回1，表示删除节点成功

有了删除某一位置节点的deleteNode函数后，就可以通过它来实现链表所有节点的删除

/*作者：是北豼不太皮吖时间：2022年3月22日15:53:39函数功能：删除链表所有节点参数：struct node **pheadptr返回值：void说明：deleteAllNode函数没有返回值，只有一个参数pheadptr，由于需要修改头指针，因此，也被定义为一个二级指针。在函数体中只有一个while循环，并将调用countOfNode函数的结果作为循环的条件，即链表中的头节点数量不为0时执行循环体，为0时终止循环。在循环体中通过调用deleteNode函数，并将整数1作为其第2个参数，这表示将链表中的头节点删除。该函数会依次将链表中的头节点删除，直至成为空链表*/void deleteAllNode(struct node **pheadptr){while(countOfNodes(*pheadptr))deleteNode(pheadptr,1);}

最后在主函数中测试这些函数，检查链表节点的创建、添加、统计和删除是否正确

int main(){//定义链表头指针，并将其初始化为空指针struct node *headPtr = NULL;//向链表添加5个节点for(int i = 1;i <= 5;++i)addNode(&headPtr,i * 10);//打印链表节点数量和各节点的值printf("The number of linked list nodes is :%u\n",countOfNodes(headPtr));printAllNode(headPtr);//删除链表中第2个节点printf("Delete the node at location 2.\n");deleteNode(&headPtr,2);//再次打印链表节点数量和各节点的值printf("The number of linked list nodes is:%u\n",countOfNodes(headPtr));printAllNodes(&headPtr);//删除链表所有节点deleteAllNode(&headPtr)return 0;}

结果如下

The number of linked list nodes is :510 20 30 40 50Delete the node at location 2.The number of linked list nodes is:410 30 40 50

双向链表

链表节点的指针域中既含有指向前驱节点的指针，也含有指向后继节点的指针

在双向链表中，可以非常方便地通过一个节点来访问它的前驱节点与后继节点，其中头节点指向前驱节点的指针为空，尾节点指向后继节点的指针为空。我们既可以从头节点开始，一顺序方式遍历链表所有节点，也可以从尾节点开始，以逆序方式遍历链表所有节点

下面用一个程序案例来展示双向链表的使用

#include #include /*定义双向链表的节点类型*/typedef struct node{//数据域int data;//指针域struct node *prev;//指向前驱节点的指针struct node *next;//指向后续节点的指针}NODE,*PNODE;/*定义双向链表类型*/typedef struct dblLinklist{PNODE head;//链表的头指针PNODE tail;//链表的尾指针unsigned count;//链表节点数量}DLinkList,*PDLinkList;/*初始化双向链表*/void InitDLinkList(PDLinkList pdll){pdll->head = pdlll->tail = NULL;//将头指针与尾指针设置为空指针pdll->count = 0;//链表节点数量为0}/*在堆中创建双向链表节点，并返回该节点的指针*/PNODE createDLLNode(int val){//在堆中为新节点申请分配内存空间PNODE p = (PNODE)malloc(sizeof(NODE));if(p){//内存分配堆内存成功，对节点各成员赋值p->data = val;p->prev = p->next = NULL;//将指向前驱与后续的指针设置为空指针}return p;}/*将节点添加到双向链表的首端，成功返回1，失败返回0*/int addNodeToHead(PDLinkList pdll,PNODE pnode){if(pnode == NULL)//若新节点为空，则添加节点失败，返回0return 0;if(pdll->head)//若之前有头节点，则让其成为新节点的后续节点，新节点变为链表头节点{pdll->head->prev = pnode;//让原头节点的前驱为新节点pnode->next = pdll->head;//让新节点的后续为原头节点pdll->head = pnode;//让新节点成为链表的头节点}else//若之前没有头节点，则链表为空链表，让新节点成为链表的头节点和尾节点pdll->head = pdll->tail = pnode;++pdll->count;//自增链表节点数量return 1;//添加节点成功，返回1}/*将节点添加到双向链表的尾端，成功返回1，失败返回0*/int addNodeToTail(PDLinkList pdll,PNODE pnode){if(pnode == NULL)return 0;if(pdll->tail)//若之前有尾节点，则让其成为新节点的前驱节点，新节点变为链表尾节点{pdll->tail->next = pnode;//让原尾节点的后续为新节点pnode->prev = pdll->tail;//让新节点的前驱为原尾节点pdll->tail = pnode;//让新节点成为链表尾节点}elsepdll->head = pdll->tail = pnode;//若之前没有尾节点，则链表为空链表，让新节点成为链表的头节点和尾节点++pdll->count;//自增链表节点数量return 1;}/*获取双向链表节点数量*/unsigned countOfDLinkList(PDLinkList pdll){return pdll->count;}/*顺序打印输出链表所有节点*/void printDLinkList(PDLinkList pdll){PNODE p = pdll->head;//指针p指向头节点while(p)//指针p不为空，则执行循环体{printf("%d ",p->data);//打印节点数据p = p->next;//修改指针p，让其指向后继节点}printf("\n");}/*逆序打印输出链表所有节点*/void printDLinkListByReverse(PDLinkList pdll){PNODE p = pdll->head;//指针p指向尾指针while(p)//指针p不为空，则执行循环体{printf("%d ",p->data);//打印节点数据p = p->next;//修改指针p，让其指向前驱节点}printf("\n");}/*删除指定位置处的节点，成功返回1，失败返回0*/int deldteNodeByPosition(PDLinkList pdll,unsigned loc){if(pdll->count < loc)return 0;PNODE p;if(loc == 1){//删除头节点p = pdll->head;pdll->head = pdll->head->next;if(pdll->head)pdll->head->prev = NULL;}else if(loc == pdll->count){//删除尾节点p = pdll->tail;pdll->tail = pall->tail->prev;if(pdll->tail)pdll->tail->next = NULL;}else{//删除中间节点p = pdll->head;for(int i = 1;i < loc;++i)p = p->next;p->prev->next = p->next;p->next->prev = p->prev;}free(p);--pdll->count;return 1;}/*清空链表，即删除双向链表所有节点*/void EmptyDLinkList(PDLinkList pdll){while(pdll->count)deleteNodeByPosition(pdll,1);InitDLinkList(pdll);}int main(){//定义双向链表DLinkList list;//初始化双向链表InotDLinkList(&list);int i;//以首行添加方式，向双向链表添加3个节点for(i = 1;i <= 3;++i)addNodeToHead(&list,createDLLNode(i));//以尾端添加方式，向双向链表添加3个节点for(i = 4;i <= 6;++i)addNodeToHead(&list,createDLLNode(i*10));//以顺序方式打印链表printf("Print all nodes of the linked list sequentially:\n");printf(&list);//以逆序方式打印链表printf("Print all nodes in the linked list in reverse order:\n");printf(&list);//删除链表第3个节点printf("Delete the node at position 3:\n");deleteNodeByPosition(&list,3);//以顺序方式打印链表printf("Print all nodes of the linked list sequentially:\n");printf(&list);//清空链表EmptyDLinkList(&list);return 0;}

大家可以比较一下双向链表与单链表在使用上的细微差别，尤其在删除链表节点时，要充分考虑到除了释放节点本身，还要喔维护好它的前驱节点与后继节点之间的关系，以及在建立节点关系时，对各指针进行修改的先后顺序

运行结果

Print all nodes of the linked list sequentially:3 2 1 40 50 60Print all nodes in the linked list in reverse order:60 50 40 1 2 3Delete the node at position 3:Print all nodes of the linked list sequentially:3 2 40 50 60