头删头删与尾删的方法类似

• 尾删
• 头删

设置新结点的指针以插入到尾部。实际中更多是作为其他数据结构的子结构，如哈希桶、

链表打印

双链表销毁

1. 定义pcur指向头结点的下一个结点，并遍历双链表。
2. 释放尾结点del。删除结点

   指定位置插入结点

   1. 指向结点是否有效，若无效则断言。
      
      
      在众多链表结构中，实际中最常用的有这两种结构：单链表和双向带头循环链表(即双链表)。
   2. 定义结点del保存尾结点，让尾结点的前一个结点的next指向头结点。头插
   3. • 尾插
      • 头插
   4. 尾删、

      更新原链表尾节点的指针，使其next指针指向新节点newnode，这样新节点就被正确地链接到链表的末尾。
      需要注意的是：删除指定结点后，由于形参不能改变实参，因此需要我们手动置指定结点为NULL。
      
      

   指定位置删除结点

   删除指定结点，想要形参的改变影响到实参，那么传二级指针不是更好吗？
   事实的确如此，那么我们为什么在这里是传一级指针呢？
   目的是为了保证接口一致性。
   

   尾插、
   

   查找结点

   和单链表一样，我们只需要遍历原链表查找结点，若没找到则返回NULL。
   

   申请结点

   

   创建头节点

   根据概念创建一个头结点起到"放哨"的作用，这个结点可随意给值。
   

双链表实现

#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintLTDataType;//定义双向链表节点的结构typedefstructListNode{LTDataType data;structListNode*next;structListNode*prev;}LTNode;//声明双向链表中提供的方法//初始化//void LTInit(LTNode** phead);LTNode*LTInit();//打印双链表voidLTPrint(LTNode*phead);//哨兵位节点不能被删除，节点的地址也不能发生改变，因此传一级最合适//尾插voidLTPushBack(LTNode*phead,LTDataType x);//插入数据之前，，链表必须初始化到只有一个头结点的情况//头插voidLTPushFront(LTNode*phead,LTDataType x);//尾删voidLTPopBack(LTNode*phead);//头删voidLTPopFront(LTNode*phead);//在pos位置之后插入数据voidLTInsert(LTNode*pos,LTDataType x);//删除pos节点voidLTErase(LTNode*pos);//查找节点LTNode*LTFind(LTNode*phead,LTDataType x);//销毁节点voidLTDesTroy(LTNode*phead);

#define_CRT_SECURE_NO_WARNINGS1#include"List.h"//申请节点LTNode*LTBuyNode(LTDataType x){LTNode*node =(LTNode*)malloc(sizeof(LTNode));if(node ==NULL){perror("malloc fail!");exit(1);}//申请成功node->data =x;node->next =node->prev =node;returnnode;}//初始化LTNode*LTInit(){//创建头结点//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//phead->data = -1;//phead->next = phead->prev = phead;//给双向链表创建一个哨兵位LTNode *phead =LTBuyNode(-1);}//打印双链表voidLTPrint(LTNode*phead){assert(phead);LTNode*pcur =phead->next;while(pcur !=phead){printf("%d->",pcur->data);pcur =pcur->next;}printf("\n");}//尾插voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnode =LTBuyNode(x);//phead  newnode  phead->prevnewnode->prev =phead->prev;newnode->next =phead;phead->prev->next =newnode;phead->prev =newnode;}//头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnode =LTBuyNode(x);//phead  newnode  prev->nextnewnode->prev =phead;newnode->next =phead->next;phead->next->prev =newnode;phead->next =newnode;}//尾删voidLTPopBack(LTNode*phead){//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead &&phead->next !=phead);//phead  phead->prev->prev  phead->prev//phead  del->prev  del  让del=phead->prevLTNode*del =phead->prev;del->prev->next =phead;phead->prev =del->prev;//释放del节点free(del);del =NULL;}//头删voidLTPopFront(LTNode*phead){assert(phead &&phead->next !=phead);//phead phead->next phead->next->next//phead del del->next  让del=phead->nextLTNode*del =phead->next;phead->next =del->next;del->next->prev =phead;//释放del节点free(del);del =NULL;}//在pos位置之后插入数据voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnode =LTBuyNode(x);//pos  newnode  pos->nextnewnode->next =pos->next;newnode->prev =pos;pos->next->prev =newnode;pos->next =newnode;}//删除pos节点voidLTErase(LTNode*pos)//二级指针更好{assert(pos);//pos->prev  pos pos->nextpos->next->prev =pos->prev;pos->prev->next =pos->next;free(pos);pos =NULL;}//查找节点LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*pcur =phead->next;while(pcur !=phead){if(pcur->data ==x){returnpcur;}pcur =pcur->next;}//没有找到returnNULL;}//销毁节点voidLTDesTroy(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;}

#define_CRT_SECURE_NO_WARNINGS1#include"List.h"voidListTest(){//LTNode* plist = NULL;//LTInit(&plist);LTNode*plist =LTInit();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushFront(plist,4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTNode*find =LTFind(plist,1);//if (find == NULL)//{//	printf("没有找到n");//}//else {//	printf("找到了n");//}LTInsert(find,4);LTPrint(plist);LTErase(find);//不传二级(保持接口一致性)find =NULL;LTPrint(plist);LTDesTroy(plist);plist =NULL;}intmain(){ListTest();return0;}