目录
1. 链表的种类
2. 最实用的两种链表类型
3. 实现双向带头循环链表
3.1 创建头节点
3.2 实现双向循环功能—返回头指针
3.3 尾插
3.4 头插
3.5 尾删
3.6 头删
4. 实现两个重要接口函数
4.1 随机插入
4.2 随机删除
5. 顺序表和链表总结
1. 链表的种类
由上面的组合可以知道链表由2^3种类型
2. 最实用的两种链表类型
2.1 单向不带头不循环链表—（之前博客实现了）
2.2 双向带头循环链表
3. 实现双向带头循环链表
3.1 创建头节点
LTNode* BuyListNode(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;
}3.2 实现双向循环功能—返回头指针
LTNode* ListInit()
{
LTNode* phead = BuyListNode(-1);//给头的data随便给个初始值
phead->next = phead;
phead->prev = phead;
return phead;
}3.3 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//ListInsert(phead, x);
}3.4 头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* next = phead->next;
phead newnode next
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
//ListInsert(phead->next, x);
}3.5 尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
//assert(!ListEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
//ListErase(phead->prev);
}3.6 头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListErase(phead->next);
}4 实现两个重要接口函数
随机插入接口函数（ListInsert）可以实现头插、尾插，直接复用
随机删除接口函数（ListErase）可以实现头删、尾删，直接复用 文章来源：https://www.toymoban.com/news/detail-422976.html
4.1 随机插入
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
// prve newnode pos
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}4.2 随机删除
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}5 顺序表和链表总结
文章来源地址https://www.toymoban.com/news/detail-422976.html
到了这里，关于数据结构—双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
