因为顺序表的不足而产生了链表，链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作简单。
#include "ListNode.h" void Compatibo(ListNode** ppList)// 增容 { *ppList = (ListNode *)malloc(sizeof(ListNode)); } void PrintList(ListNode* pList)//打印链表 { if(pList == NULL)； else if(pList->next == NULL) printf("%d->",pList->data); else { while(pList) { printf("%d->",pList->data); pList = pList->next; } } printf("NULL\n"); } void PushBack(ListNode** ppList, DataType x)//链表尾插 { assert(ppList); ListNode *pavi = *ppList; //用于遍历链表，若用*ppList遍历后改变*ppList的值 ListNode *tail = NULL; Compatibo(&tail); tail->data = x; tail->next = NULL; if(*ppList == NULL) { *ppList = tail; } else { while(pavi->next) { pavi = pavi->next; } pavi->next = tail; } } void PopBack(ListNode** ppList) //链表尾删 { assert(ppList); ListNode *tail = *ppList;// 用tail = null 不会改变*ppList的值 ListNode *pavi = NULL;//用 paci->next = null 帮助置空最后地址 if(tail == NULL) return ; else if(tail->next == NULL) { free(tail); *ppList = NULL; } else { while(tail->next) { pavi = tail; tail = tail->next; } free(tail); pavi->next = NULL; //tail=pavi->next ,但tail是函数内部指针，不会改变实际链表， //而pavi->next是对内部指针的*引用,改变的是链表的值 } } void PushFront(ListNode** ppList, DataType x) //t头插 { assert(ppList); ListNode *pavi = NULL; Compatibo(&pavi); pavi->data = x; if(*ppList == NULL) { *ppList = pavi; pavi->next = NULL; } else { pavi->next = *ppList; *ppList = pavi; } } void PopFront(ListNode** ppList) //头删 { assert(ppList); ListNode *pavi = NULL; if(*ppList == NULL) return ; else if((*ppList)->next == NULL) { free(*ppList); *ppList = NULL; } else { pavi = (*ppList)->next;//先将原链表的第二个节点的地址保存 free(*ppList); //释放第一个节点 *ppList = pavi; //把保存的节点地址再次赋给链表的头 } } ListNode* Find(ListNode* pList, DataType x) //查找第一个为x的节点 { while((pList != NULL)&&(pList->data != x))//若没这个数 { pList = pList->next; } return pList; } //pos节点的前面插入 void Insert(ListNode** ppList, ListNode* pos, DataType x) { assert(ppList && pos); ListNode *tail = *ppList; ListNode *tmp = NULL; Compatibo(&tmp); tmp->data = x; if(*ppList == pos) PushFront(ppList,x); else { while((tail != NULL)&&(tail->next != pos)) { tail = tail->next; } if(tail == NULL)//没有找到节点 return ; tmp->next = pos; tail->next = tmp; } } void Erase(ListNode** ppList, ListNode* pos)//删除节点 { assert(ppList); ListNode *tail = *ppList;// 用tail = null 不会改变*ppList的值 if(tail == pos) { *ppList = pos->next; free(pos); } else { while((tail != NULL)&&(tail->next != pos)) { tail = tail->next; } if(tail == NULL) return ; tail->next = pos->next; free(pos); } }