一、单链表和双向链表基本介绍
（1）什么是单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据 ————百度百科
单链表的访问都是由指针进行访问，不需要扩容，对于数据操作比较快速。
（2）什么是双链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表————百度百科
双链表的访问就比单链表有优势，当数据量比较大时，想要对末尾的节点进行操作需要有个变量把前面节点全都遍历，但是双向链表只需要头节点的前驱就索引到目标了。
二、链表与顺序表比较
顺序表的优点是数据存储是连续的，所以访问数据比较快速，但是要对顺序表元素进行操作，有时候会进行大量数据移动操作，是比较浪费时间的，而且扩容时有风险。
链表的优点是利用碎片化空间，对于数据操作比较快，但是要进行遍历等操作时，速度是比较慢的，当释放内存操作失误很容易内存泄漏。
三、单链表基本操作
（1）单链表结构定义：
typedef int LTDataType; typedef struct ListNode { struct ListNode* next;//后继指针指向下一个节点 LTDataType data;//数据域存放数据 }LTNode;
（2）单链表初始化：
LTNode* InitNewNode(LTDataType n) { LTNode* p = (LTNode*)malloc(sizeof(LTNode));//开辟新节点 if (p == NULL)//检查节点是否开辟失败 { perror("malloc"); exit(-1); } p->next = NULL;//指针域置空 p->data = n;//数据域赋值 return p;//返回新节点 }
（3）单链表头插：
LTNode* LTPushFront(LTNode *head, LTDataType x) { if (head == NULL) return NULL; LTNode* node = InitNewNode(x);//插入新节点 node->next = head;//头插 return node;//返回新的头节点 }
（4）单链表头删：
LTNode* LTPopFront(LTNode* head) { if (head == NULL) return NULL; if (head->next)//链表节点>1的时候 { LTNode* newhead = head->next; free(head);//头删 return newhead;//返回新头节点 } else//只有头节点的时候 { free(head); return NULL; } }
（5）单链表尾插：
LTNode* LTPushBack(LTNode *head, LTDataType x) { if (head == NULL)//为空返回空 return NULL; LTNode* node = InitNewNode(x);//尾插的新节点 LTNode* p = head; while (p -> next)//遍历到最后一个节点 p = p->next; p->next = node;//尾插 node->next = NULL; return head;//返回头节点 }
（6）单链表尾删：
LTNode* LTPopBack(LTNode *head) { if (head == NULL) return NULL; if (head->next == NULL)//只有头节点直接删除 { free(head); return NULL; } LTNode* p = head; while (p->next->next)//遍历到最后一个节点的前一个节点 { p = p->next; } LTNode* tmp = p->next;//最后一个节点保存 p->next = tmp->next;//尾删 free(tmp); return head;//返回链表头节点 }
（7）单链表pos位置插入：
LTNode* LTPush(LTNode* head, int pos, LTDataType val) { if (pos == 0)//插入位置在0为头插 { LTNode* node = InitNewNode(val); node->next = head; return node; } LTNode* node = InitNewNode(val); LTNode* p = head; for (int i = 0; i < pos - 1; i++) p = p->next; node->next = p->next;//进行插入 p->next = node; return head; }
（8）销毁单链表：
void LTDestroy(LTNode* head) { if (head == NULL) return; for (LTNode* p = head, *q; p; p = q) { q = p->next;//保存p的下一个节点 free(p);//销毁当前节点 } return; }
（9）单链表随机插入：
int main() { srand((unsigned int)time(0));//产生伪随机 LTNode* head = InitNewNode(rand() % 100 + 1); for (int i = 0; i < MAX_OP; i++)//MAX_OP为7，表示七次插入 { int pos = rand() % (i + 2), val = rand() % 100;//插入位置与值随机 printf("Insert %d at %d to Linklist \n", val, pos); head = LTPush(head, pos, val); output(head);//每次插入都打印 } LTDestroy(head); return 0; }
（10）单链表打印：
void output(LTNode* head)//我觉得这样会更美观一些 { int n = 0; for (LTNode* p = head; p; p = p->next) n++; for (int i = 0; i < n; i++) { printf("%3d", i); printf(" "); } printf("\n"); for (int i = 0; i < n; i++) { printf("-----"); } printf("\n"); for (LTNode* p = head; p; p = p->next) { printf("%3d", p->data); printf("->"); } printf("\n"); printf("\n"); printf("\n"); return; }
打印效果：
（11）单链表操作测试：
void Test(LTNode *head) { printf("PushBack:\n"); head = LTPushBack(head, 1); head = LTPushBack(head, 2); head = LTPushBack(head, 3); output(head); printf("PopBcak:\n"); head = LTPopBack(head); head = LTPopBack(head); head = LTPopBack(head); output(head); printf("PushFront:\n"); head = LTPushFront(head, 3); head = LTPushFront(head, 2); head = LTPushFront(head, 1); output(head); printf("PopFront:\n"); head = LTPopFront(head); head = LTPopFront(head); head = LTPopFront(head); output(head); return; }
打印结果：
四、双向链表基本操作
（1）双向链表结构定义：
typedef int LTDataType; typedef struct ListNode { struct ListNode* next;//后继指针 struct ListNode* pre;//前驱指针 LTDataType data; }LTNode;
（2）双链表初始化：
LTNode* BuyLTNode(LTDataType n) { LTNode* p = (LTNode*)malloc(sizeof(LTNode));//开辟新节点 p->pre = p;//前后指针都指向自己 p->next = p; p->data = n; return p;//返回新节点 }
（3）双链表头插：
void LTPushFront(LTNode* phead, LTDataType n) { assert(phead);//断言不为空指针 LTNode* tail = phead->pre;//找到尾节点 LTNode* node = BuyLTNode(n); node->next = phead;//新节点指向头指针 phead->pre = node;//头指针前驱指向新节点 tail->next = node;//尾节点指向新节点 node->pre = tail;//新节点前驱指向尾节点 return; }
（4）双链表尾插：
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead);//断言是否为空指针 LTNode* tail = phead->pre;//找到尾指针 LTNode* newnode = BuyLTNode(x); tail->next = newnode;//尾指针指向新节点 newnode->next = phead;//新节点指向头指针 newnode->pre = tail;//新节点前驱指向尾指针 phead->pre = newnode;//头节点前驱指向新节点 }
（5）双链表头删：
void LTPopFront(LTNode* phead) { assert(phead); LTNode* tail = phead->pre;//保存尾节点 tail->next = phead->next;//尾节点指向头节点下一个节点 phead->next->pre = tail;//头节点下一个节点前驱指向尾节点 free(phead); tail->next = phead;//尾节点指向新的头节点 return; }
（6）双链表尾删：
void LTPopBack(LTNode* phead) { assert(phead); LTNode* tail = phead->pre;//找到尾节点 tail->pre->next = phead;//尾节点前驱节点指向头节点 phead->pre = tail->pre;//头节点前驱指向尾节点前驱 free(tail); return; }
（7）双链表pos位置插入：
void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->pre;//保存pos位置前一个节点 LTNode* node = BuyLTNode(x); node->next = pos;//新节点指向pos pos->pre = node;//pos前驱指向新节点 node->pre = prev;//新节点前驱指向pos前节点 prev->next = node;//pos前节点指向新节点 return; }
（8）双链表删除节点：
void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->pre;//保存要删除位置前一个节点 prev->next = pos->next;//前一个结点指向pos的下一个节点 pos->next->pre = prev;//pos的下一个节点的前驱指向前一个节点 return; }
（9）双链表销毁：
void ListDestory(LTNode* phead) { assert(phead); LTNode* p = phead->next;//保存头节点下一个节点 while (p) { free(phead); if (p->next) { phead = p; p = p->next; } } return; }
（10）双链表打印：
void ListPrint(LTNode* phead)//打印双链表 { assert(phead); LTNode* p = phead; do { printf("%d ", p->data); if (p->next != phead) { printf("<->"); } p = p->next; } while (p != phead); printf("\n\n\n"); return; }
如果这篇文章对您有帮助的话，还望三连支持一下作者啦~~
