【链表-双向链表】

链表-双向链表

• 1.链表的分类
• • 1.1 分类依据
  • 1.2 常用类型
  • 2.双向链表的
  • • 2.1 双向链表的结构
    • 2.2 双向链表的操作
    • • 2.2.1 **初始化**
      • 2.2.2 **尾插**
      • 2.2.3 **头插**
      • 2.2.4 **尾删**
      • 2.2.5 **头删**
      • 2.2.6 在pos位置之后插入数据
      • 2.2.7 删除pos节点
      • 2.2.8 查找
      • 2.2.9 销毁

        1.链表的分类

        1.1 分类依据

        单向or双向

        带头or不带头

        （一般会称d1为头节点，但实际上head这个哨兵节点才是头节点）

        循环or不循环

        综上所述，222共有8种链表

        1.2 常用类型

        我们一般最常用的就是单链表和双链表。

        单链表：不带头单向不循环链表

        双向链表：带头双向循环链表

        2.双向链表的

        2.1 双向链表的结构

        双向链表包含三个部分，：

        1.数据

        2.指向下一个节点的指针

        3.指向上一个节点的指针

        struct ListNode
        {int data;
        	struct ListNode* next;
        	struct ListNode* prev;
        }
        

        ps:单链表和双向链表的初始状态？

        单链表为空链表

        双向链表剩下一个头结点（即哨兵位）

        2.2 双向链表的操作

        2.2.1 初始化

        方法一

        void LTInit(LTNode** pphead);
        

        void LTInit(LTNode** pphead)
        {//给双向链表创建一个哨兵位
        	*pphead = LTBuyNode(-1);//哨兵位不存储有效数据
        }
        

        方法二

        LTNode* LTInit();
        

        LTNode* LTInit()
        {LTNode* phead = LTBuyNode(-1);
        	return phead;
        }
        

        打印双向链表

        void LTPrint(LTNode* phead);
        

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

        void LTInit(LTNode** pphead)
        {//给双向链表创建一个哨兵位
        	*pphead = LTBuyNode(-1);//哨兵位不存储有效数据
        }
        

        2.2.2 尾插

        //尾插
        void LTPushBack(LTNode* phead, LTDataType x);
        

        //尾插
        void LTPushBack(LTNode* phead, LTDataType x)
        {assert(phead);//哨兵位空，那就不是一个有效的双向链表
        	LTNode* newnode = LTBuyNode(x);
        	//phead phead->prev newnode
        	newnode->prev = phead->prev;//新节点头指向原链表的尾节点
        	newnode->next = phead;//新节点尾节点指向哨兵位
        	phead->prev->next = newnode;//原本的尾节点phead->prev指向新的尾节点
        	phead->prev = newnode;//哨兵位指向新的尾节点
        }
        

        2.2.3 头插

        void LTPushFront(LTNode* phead, LTDataType x); 

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

        2.2.4 尾删

        void LTPopBack(LTNode* phead);
        

        void LTPopBack(LTNode* phead)
        {//链表必须有效且链表不能为空（只有一个哨兵位）
        	assert(phead && phead->next != phead);
        	LTNode* del = phead->prev;
        	//phead del->prev del
        	del->prev->next = phead;
        	phead->prev = del->prev;
        	//删除del节点
        	free(del);
        	del = NULL;
        }
        

        2.2.5 头删

        void LTPopFront(LTNode* phead);
        

        void LTPopFront(LTNode* phead)
        {assert(phead && phead->next != phead);
        	LTNode* del = phead->next;
        	//phead del del->next
        	phead->next = del->next;
        	del->next->prev = phead;
        	//删除del节点
        	free(del);
        	del = NULL;
        }
        

        2.2.6 在pos位置之后插入数据

        void LTInsert(LTNode* pos, LTDataType x);
        

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

        2.2.7 删除pos节点

        void LTErase(LTNode* pos);
        

        void LTErase(LTNode* pos)
        {//pos理论上来说不能为phead，但是没有参数phead，无法增加校验
        	assert(pos);
        	//pos->prev pos pos->next
        	pos->next->prev = pos->prev;
        	pos->prev->next = pos->next;
        	free(pos);
        	pos = NULL;
        }
        

        PS：LTErase参数理论上要传二级，因为我们需要让形参的改变影响到实参，但是为了保持接口一致性才传的一级。

        2.2.8 查找

        LTNode* LTFind(LTNode* phead, LTDataType x);
        

        LTNode* LTFind(LTNode* phead, LTDataType x)
        {LTNode* pcur = phead->next;
        	while (pcur != phead)
        	{if (pcur->data == x)
        		{return pcur;
        		}
        		pcur = pcur->next;
        	}
        	//没有找到
        	return NULL;
        }
        

        2.2.9 销毁

        void LTDesTroy(LTNode* phead);
        

        void LTDesTroy(LTNode* phead)
        {assert(phead);
        	LTNode* pcur = phead->next;
        	while (pcur != phead)
        	{LTNode* next = pcur->next;
        		free(pcur);
        		pcur = next;
        	}
        	//此时pcur指向phead，而phead还没有被销毁
        	free(phead);
        	phead = NULL;
        } 

        ps:LTDestroy参数理论上要传二级，因为我们需要让形参的改变影响到实参，但是为了保持接口一致性才传的一级。传一级存在的问题是，当形参phead置为NULL后，实参plist不会被修改为NULL,因此解决办法是:调用完方法后手动将实参置为NULL。