链表是一种线性表，但是并不是顺序存储，而是每个结点存储着下一个结点的地址，把存储数据元素的数据串联起来。
单链表演示图
常见的接口如下：
#define _CRT_SECURE_NO_DEPRECATE #ifndef __SLIST_H__ #define __SLIST_H__ #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; typedef struct Node { DataType data; struct Node* next; }Node, *pNode, *pList; void InitList(pList* pplist); void PushBack(pList* pplist,DataType d); void PopBack(pList* pplist); void PushFront(pList* pplist, DataType d); void PopFront(pList* pplist); void PrintList(pList plist); pNode Find(pList plist, DataType d); void Remove(pList* pplist, DataType d); void RemoveALL(pList* pplist, DataType d); void InsertBackNode(pList* pplist, pNode pos, DataType d); void Erase(pList* pplist, pNode pos); int GetListLength(plist); void DestoryList(pList* pplist); void EraseNotTail(pNode pos); void Reverselist(pList* pplist); void BubbleSort(pList* pplist); void InsertFrontNode(pNode pos, DataType d); #endif
具体实现如下：
#define _CRT_SECURE_NO_DEPRECATE #include "SList.h" void InitList(pList* pplist) { assert(pplist != NULL); *pplist = NULL; } pNode BuyNode(DataType d) //申请一个新的结点 { pNode pnode = (pNode)malloc(sizeof(Node)); if (pnode == NULL) { perror("malloc"); return NULL; } pnode->data = d; pnode->next = NULL; return pnode; } void PushBack(pList* pplist, DataType d) //尾插法 { assert(pplist); pNode pNewNode = BuyNode(d); if (*pplist == NULL) { *pplist = pNewNode; printf("插入成功！\n"); } else { pNode cur = *pplist; while (cur->next != NULL) { cur = cur->next; } cur->next = pNewNode; printf("插入成功！\n"); } } void PopBack(pList* pplist) //从尾部删除 { assert(pplist); pNode cur = *pplist; if (cur == NULL) { printf("当前列表为空\n"); return; } if (cur->next == NULL) { free(cur); *pplist = NULL; printf("删除成功\n"); return; } while (cur->next->next != NULL) { cur = cur->next; } free(cur->next); cur->next = NULL; printf("删除成功\n"); } void PushFront(pList* pplist, DataType d)//头插法 { assert(pplist); pNode NewNode = BuyNode(d); if (*pplist == NULL) { *pplist = NewNode; printf("插入成功\n"); } else { NewNode->next = *pplist; *pplist = NewNode; printf("插入成功\n"); } } void PopFront(pList* pplist)//从头部删除 { assert(pplist); pNode cur = *pplist; if (*pplist == NULL) { printf("当前列表为空\n"); return; } else if (cur->next == NULL) { free(cur); *pplist = NULL; printf("删除成功\n"); return; } else { pNode del = *pplist; *pplist = del->next; free(del); printf("删除成功\n"); } } void PrintList(pList plist) //打印单链表 { if (plist == NULL) { printf("当前列表为空\n"); return; } pNode cur = plist; printf("List->"); while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } pNode Find(pList plist, DataType d) { pNode cur = plist; while (cur) { if (cur->data == d) return cur; else cur = cur->next; } return NULL; } void Remove(pList* pplist, DataType d)//移除一个指定的结点 { assert(pplist); pNode cur = *pplist; pNode prev = NULL; pNode del = NULL; while (cur) { if (cur->data == d) { if (cur == *pplist) //删除第一个结点 { del = *pplist; *pplist = cur->next; } else { prev->next = cur->next; free(cur); } cur = cur->next; free(del); printf("删除成功\n"); return; } else { prev = cur; cur = cur->next; } } printf("当前列表中无该元素\n"); } void RemoveALL(pList* pplist, DataType d) //移除所有与指定结点相同的结点 { assert(pplist); pNode cur = *pplist; pNode prev = NULL; pNode del = NULL; if (cur == NULL) { printf("当前列表中无元素\n"); } pNode pret = Find(cur, d); if (pret == NULL) printf("当前列表中无该元素\n"); else { while (cur) { if (cur->data == d) { if (cur == *pplist) //删除第一个结点 { del = *pplist; *pplist = cur->next; cur = cur->next; free(del); } else { del = cur; prev->next = cur->next; cur = cur->next; free(del); } } else { prev = cur; cur = cur->next; } } printf("删除成功\n"); } } void InsertBackNode(pList *pplist,pNode pos, DataType d)//在当前结点后插入一个数据d { assert(pplist); if(NULL == pos) return; else { pNode pNewNode = BuyNode(d); pNewNode->next = pos->next; pos->next = pNewNode; printf("插入成功\n"); } } void Erase(pList* pplist,pNode pos)//删除当前结点 { assert(pplist); pNode del = NULL; if (pos->next==NULL) { PopBack(pplist); return; } else { del = pos->next; pos->data = pos->next->data; pos->next = pos->next->next; free(del); printf("删除成功\n"); } } int GetListLength(pList plist) //计算结点的个数 { pNode cur = plist; int count = 0; while (cur) { count++; cur = cur->next; } return count; } void DestoryList(pList* pplist) //销毁列表 { assert(pplist); if (*pplist == NULL) { printf("列表为空！\n"); return; } pNode cur = *pplist; while (cur->next) { pNode del = cur; cur = cur->next; free(del); } *pplist = NULL; printf("列表已清空\n"); } void EraseNotTail(pNode pos) //删除无头的非尾结点，数据替换删除法 { assert((pos->next) != NULL); pNode del = pos->next; pos->data = pos->next->data; pos->next = pos->next->next; free(del); printf("删除成功\n"); } void Reverselist(pList* pplist) { assert(pplist); if ((*pplist == NULL) || ((*pplist)->next) == NULL) { return; } pList newlist = NULL; pNode cur = *pplist; while (cur) { pNode tmp = cur; cur = cur->next; tmp->next = newlist; newlist = tmp; } *pplist = newlist; printf("逆序成功\n"); } void BubbleSort(pList* pplist) //冒泡排序 { assert(pplist); pNode tail = NULL; pNode cur = *pplist; if ((cur == NULL) || (cur->next) == NULL) { return; } while (cur->next != tail) { while (cur->next != tail) { if (cur->data > cur->next->data) { DataType tmp = cur->data; cur->data = cur->next->data; cur->next->data = tmp; } cur = cur->next; } tail = cur; cur = *pplist; } printf("排序成功\n"); } void InsertFrontNode(pNode pos, DataType d) //在当前结点之前插入一个结点 { pNode newnode = BuyNode(d); DataType tmp = 0; newnode->next = pos->next; //先在其后插入，在交换其内容 pos->next = newnode; tmp=pos->data; pos->data = pos->next->data; pos->next->data = tmp; printf
测试文件：
#define _CRT_SECURE_NO_DEPRECATE #include "SList.h" void menu() { printf("\n"); printf("********** 单链表 **********\n"); printf(" 1.PushBack 2.PopBack \n"); printf(" 3.PushFrount 4.PopFront \n"); printf(" 5.PrintList 6.Find \n"); printf(" 7.Remove 8.RemoveAll \n"); printf(" 9.InsertBackNode 10.Erase \n"); printf(" 11.GetListLength 12.DestoryList \n"); printf(" 13.EraseNotTail 14.Reverselist \n"); printf(" 15.BubbleSort 16.InsertFrontNode\n"); printf(" 0.Exit \n"); printf("*****************************************\n"); } void text() { pList plist; int input = 0; InitList(&plist); do { DataType data = 0; pNode pret = 0; int ret = 0; pNode cur = NULL; menu(); printf("请选择："); scanf("%d", &input); switch (input) { case 0: break; case 1: printf("请输入要插入的数："); scanf("%d", &data); PushBack(&plist, data); break; case 2: PopBack(&plist); break; case 3: printf("请输入要插入的数："); scanf("%d", &data); PushFront(&plist, data); break; case 4: PopFront(&plist); break; case 5: PrintList(plist); break; case 6: printf("请输入要查找的数:"); scanf("%d", &data); pret = Find(plist, data); if (pret==NULL) printf("当前列表中无该元素\n"); else printf("%d", pret->data); break; case 7: printf("请输入要删除的数："); scanf("%d", &data); Remove(&plist, data); break; case 8: printf("请输入要删除的数："); scanf("%d", &data); RemoveALL(&plist, data); break; case 9: printf("请输入要插入的位置："); scanf("%d", &data); pret = Find(plist, data); if (pret == NULL) printf("当前列表中无该元素\n"); else { printf("请输入要插入的数："); scanf("%d", &data); InsertBackNode(&plist,pret, data); } break; case 10: printf("请输入要删除的结点:"); scanf("%d", &data); pret = Find(plist, data); if (pret == NULL) printf("当前列表中无该元素\n"); else Erase(&plist,pret); break; case 11: ret = GetListLength(plist); printf("结点个数为%d\n", ret); break; case 12: DestoryList(&plist); break; case 13: printf("请输入要删除的结点:"); scanf("%d", &data); pret = Find(plist, data); if (pret == NULL) printf("当前列表中无该元素\n"); else EraseNotTail(pret); break; case 14: Reverselist(&plist); break; case 15: BubbleSort(&plist); break; case 16: printf("请输入要插入结点的位置:"); scanf("%d", &data); pret = Find(plist, data); if (pret == NULL) printf("当前列表中无该元素\n"); else { printf("请输入要插入的数:"); scanf("%d", &data); InsertFrontNode(pret, data); } break; default: break; } } while (input); } int main() { text(); return 0; }
比较：单链表和顺序表
1.顺序表支持随机访问，单链表不支持。
2.顺序表插入删除效率很低，时间复杂度为O（N），单链表则效率高，时间复杂度为O（1）。
3.顺序表的CPU高速缓冲效率更高，单链表高速缓冲效率则低。
