带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”。哨兵位存在的意义：避免链表出现死循环。
双向链表的结构：数据+指向下一个节点的指针+指向前一个节点的指针
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct Listnode* prev; struct Listnode* next; }LTNode;
双向链表为空，只有一个头结点。
首先我们进行初始化：
void LTInit(LTNode**pphead);//双向链表的初始化 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; return node; } void LTPushBack(//插入链表之前，链表必须初始化到只有一个头节点的情况 { //给链表创建一个哨兵位 *pphead=LTBuyNode(-1); }
插入数据
首先我们要申请一个新的节点，再改变指针的指向。
void LTPushBack(LTNode* pphead,LTDataType x)//不改变头结点的位置，只用传一级指针就可以 { assert(phead);//首先头指针不能为空 //先把newnode插入链表，再改变原链表前驱节点和后继节点指针的指向 newnode->prev=phead->prev; newnode->next=phead; phead->prev->next=newnode;//先改变原头节点的前驱节点的后继节点 phead->prev=newnode; }
这个函数对空链表的情况也满足。
打印链表
void LTPrint(LTNode*phead) { LTNode*pcur=phead->next; while(pcur!=phead) { printf("%d->",pcur->data); pcur=pcur->next; } printf("\n"); }
头插
往头结点的后面插入
void LTPushFront(LTNode* phead,LTDataType x) { assert(phead); LTNode* newnode=BuyNode(x); newnode->next=phead->next; newnode->prev=head; phead->next->prev=newnode; phead->next=newnode; }
尾删
void LTPopBack(LTNode* phead) { //链表必须有效且链表不能为空 assert(phead&&phead->next!=phead); LTNode*del=phead->prev;//把头结点的上一个节点储存起来 del->prev->next=phead; phead->prev=del->prev; free(del); del=NULL: }
头删
void LTPopFront(LTNode* phead) { assert(phead&&phead->next!=phead); LTNode* del=phead->next; phead->next=del->next; del->next->prev=phead; free(del); del=NULL; }
在pos位置之后插入数据
void LTFind(LTNode* phead,LTDataType x) { LTNode*pcur=phead->next; while(pcur!=phead) { if(pcur->data==x) { return pcur; } pcur=pcur->next; } return NULL; }
void LTInsert(LTNode* pos,LTDataType x) { assert(pos); LTNode*newnode=LTBuyNode(x); newnode->next=pos->next; newnodeprev=pos; pos->next->prev=newnode; pos->next=newnode; }
LTInsert方法包含了头插
删除pos节点
void LTErase(LTNode* pos) { assert(pos); pos->next->prev=pos->prev; pos->prev->next=pos->next; free(pos); pos=NULL; }
销毁链表
void LTDestory(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; }
