双向链表的介绍
双向链表是一种链表，它的每个节点都有两个链接，一个指向前一个节点，另一个指向下一个节点。相比于单向链表，双向链表在插入和删除操作时更加灵活，因为它们可以从两个方向进行操作。但是，双向链表的实现比单向链表更复杂，因为需要额外的指针来维护前一个和下一个节点的链接。 
尾插
在链表的尾部插入新的结点，要插入新的结点，首先得定义一个新的结点，接这找到链表尾部结点，最后通过改变指针指向进行插入。
先定义一个新的结点（newnode),令他的next指向NULL;
找链表的尾部结点，定义一个移动结点tail，通过next指针进行移动,不难看出tail的next指向NULL就是链表的尾部结点
要将新结点链接到双向链表上，只需要：
将最后一个链表的结点的next指针指向newnode上，
将newnode的prev指针指向双向链表的最后一个指针上。
这样尾插就完成了，下面是代码
// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { //定义新结点 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode) { newnode->_data = x; newnode->_next = NULL; } //找到最后一个结点 ListNode* tail = pHead; while (tail->_next != NULL) { tail = tail->_next; } //改变指针指向 tail->_next = newnode; newnode->_prev=tail; }
尾删
很简单，尾删就是删除最后一个节点将最后一个结点的位置置空：
首先应找到，最后一个结点
接着,最后一个结点的prev指向最后一个结点的前一个结点，
将前一个结点的next指向NULL((将最后一个结点的位置置空）
// 双向链表尾删 void ListPopBack(ListNode* pHead) { //找到最后一个结点 ListNode* tail = pHead; while (tail->_next!=NULL) { tail = tail->_next; } tail->_prev ->_next = NULL; }
头插
头插是在头结点的后边直接插入所以还是定一个新节点（newnode),通过改变头节点的指向，和头节点下一个结点的指向以及new结点的指向来完成头插。
第一步先将newnode连接到链表上
newnode->prev=pHead;
newnode->next=pHead->next;
因为头结点的下一个结点要通过pHead的next指针来访问，所以先不要改pHead的next的指向，否则就访问不到pHead的下一个结点了；
要先将头结点的下一个结点的前驱结点指向newnode（pHead->next->prev=newnode)
接着改pHead->next指针指向newnode(pHead->next=Newnode)
这样头插就完成了
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode) { newnode->_data = x; newnode->_next = pHead->_next; newnode->_prev = pHead; pHead->_next->_prev=newnode; pHead->_next = newnode; } }
头删
头删就是删除头节点的下一个结点，还是同样的原因，因为要通过next指针找下一个结点，所以应该先改蓝色的指针，（pHead->next->next->prev=pHead)
接着pHead->next=pHead->next->next;
// 双向链表头删 void ListPopFront(ListNode* pHead) { pHead->_next->_next->_prev = pHead; pHead->_next = pHead->_next->_next; }
实现：
void test3() { ListNode* Dhead = ListCreate(); ListPushBack(Dhead, 1); ListPushBack(Dhead, 2); ListPushBack(Dhead, 3); ListPushBack(Dhead, 4); printf("1到4尾插："); ListPrint(Dhead); printf("\n"); printf("尾删一次："); ListPopBack(Dhead); ListPrint(Dhead); printf("\n"); printf("尾删两次："); ListPopBack(Dhead); ListPrint(Dhead); printf("\n"); printf("\n"); ListPushFront(Dhead, 7); ListPushFront(Dhead, 8); ListPushFront(Dhead, 9); printf("7到9头插："); ListPrint(Dhead); printf("\n"); printf("头删一次："); ListPopFront(Dhead); ListPrint(Dhead); printf("\n"); printf("头删两次："); ListPopFront(Dhead); ListPrint(Dhead); printf("\n"); } int main() { test3(); return 0; }
运行结果:
