链表分类

单向或双向

带头或不带头

循环或非循环

合计有八种

带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。使用代码实现，结构会带来很多优势，实现反而简单了。

创建新节点

LTNode* BuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);	}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

初始化

LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

初始化会修改结构体的内容，所以需要结构体指针，也可以用返回值来解决

1. 通过BuyLTNode创建一个新节点
2. 将phead节点的next指向自己
3. prev指向自己
   

打印链表

void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

通过assert断言，判断phead是否合法

1. 创建一个cur结构体指针，把phead->next赋给cur，也就是cur指向第一个节点
   

2. 把cur->next赋给cur，也就是cur指向cur的下一个节点，循环遍历直到cur等于头节点停止
   

只有头节点就不进入循环

尾插

尾插的时候不需要找尾节点，双向循环链表，头节点的prev指向尾节点，尾节点的next指向头节点
tail的next指向newnode，newnode的prev指向tail，newnode的next指向phead，phead的prev指向newnode

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);newndode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;}

通过assert判断phead指针是否为空

1. 创建tail指针，通过phead的prev指针，找到最后一个节点
   

2. 通过BuyLTNode，malloc一个新的链表节点
   

3. 将newnode节点与tail节点连接，将newnode的prev指向tail，tail的next指向newnode
   

4. 将newnode节点与phead节点连接，将newnode的next指向phead，phead的prev指向newnode
   

只有一个头节点的情况：

1. 创建tail指针，malloc新节点
   

2. tail和phead是同一个节点，直接连接
   

尾删

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;}

通过assert判断phead是否为空，是否只有phead一个节点，是个空链表

1. 创建tail节点，通过phead->prev，找到最后一个节点
   

2. 创建tailPrev节点，通过tail->prev，找到倒数第二个节点
   

3. 释放tial节点
   

4. 连接tailPrev节点和phead
   

头插

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

先将newnode连接到第一个节点，再连接头节点和新节点newnode，不能更改顺序，否则会丢掉后面的链表
头插是在第一个节点的前面插入，不是在哨兵位的前面插入
通过assert判断phead是否为空

1. 创建一个newnode节点
   

2. 将newnode与第一个节点连接
   

3. 将newnode与phead
   

只有一个phead节点的情况
由于phead和phead->prev是同一个节点，所以直接连接phead和newnode节点

1. 创建一个newnode节点
   

2. newnode的next指向phead，phead的prev指向newnode
   

3. phead的next指向newnode，newnode的prev指向phead
   

通过创建一个first节点来代表第一个节点，这样连接就不用在意连接顺序，不怕丢掉后续链表

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

1. 创建newnode和first，将phead->next赋给first，first指向第一个节点
   

2. 再继续连接phead和newnode，newnode和first，同上

头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}

通过assert判断phead是否为空，是否为空链表

1. 创建first和second指针，分别指向第一个和第二个节点
   

2. 释放掉first，连接phead和second
   

返回大小

int LTSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}

1. assert判断phead是否合法
2. 通过cur指针遍历链表
3. 每遍历一个节点，size++，直到cur为phead
4. 最后返回size
   可以在哨兵位节点的data里存放size，插入时data++，删除时data–，求大小时，直接返回phead的data
   但是只有确定链表的data数据类型是int才可以使用，其他数据类型无法实现
   如果真要用size来记录，应该在函数外定义

查找x

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);STNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;	
}

1. 通过assert判断phead是否为空
2. 通过cur指针遍历链表
3. 当cur指向节点的data等于x，返回cur指针
4. 如果没找到，返回NULL

pos之前插入x

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev; newnode->next = pos;pos->prev = newnode;
}

1. assert判断pos指针是否合法

2. 将pos->prev赋给posPrev指针，找到pos前一个节点

3. newnode一个节点
   

4. 连接newnode与posPrev节点
   

5. 连接pos和newnode
   

之前的头插尾插都可以用Insert复用

	LTInsert(phead->next, x);   //头插LTInsert(phead, x);         //尾插

删除pos位置

void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

1. assert判断pos是否为空

2. 创建posPrev和posNext找到pos前一个和后一个节点
   

3. 释放掉pos
   

4. 连接posPrev和posNext
   

	LTErase(phead->next);    //头删LTErase(phead->prev);    //尾删

销毁

void LTDestroy(LTNode* phead)
{assert(phead);STNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

1. assert判断phead是否为空
2. 通过cur指针遍历整个链表
3. 每次循环，创建一个next指针，指向cur节点的下一个，释放掉cur节点，将cur指针指向next，当cur为phead时结束
4. 最后释放掉phead节点
   函数内没有用到二级指针，形参不能改变实参，可以在函数外调用后再phead置空

顺序表和链表的区别

存储器层次结构

声明定义分离实现

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* BuyNode(LTDataType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
int LTSize(LTNode* phead);
//pos之前插入xLTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

include "List.h"LTNode* BuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);	}node->data = x;node->next = NULL;node->prev = NULL;return node;
}LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);newndode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}int LTSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);STNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;	
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev; newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}void LTDestroy(LTNode* phead)
{assert(phead);STNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}