双向链表实现(c语言)

链表是数据结构中的基础内容其中双向链表Doubly Linked List相比单向链表增加了一个前驱指针因此可以向前和向后遍历删除节点时也更加方便。双向链表的结构如下typedef struct Node { int data; struct Node* pre; struct Node* next; }Node;实现如下逻辑创建节点方式Node* createNode(int value) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-pre NULL; newNode-next NULL; return newNode; }头插法每次把新节点放在链表前面void insertFront(Node** head, int value) { Node* newNode createNode(value); newNode-next *head; if (*head ! NULL) { (*head)-pre newNode; } *head newNode; }我们来看图示创建第一个节点, 在main()函数中有Node* head NULL;(稍后介绍main()函数的内容),newNode从createNode()函数返回接收首地址(用0x1代替0x000 000 000 000 000 1,懒得写太长的十六进制数了)第一轮因为是空链表所以不执行if判断将head解引用赋值为newNode,也就是地址增加新节点的时候如下执行if判断,形成指向即为链表同时head头指针指向新节点尾插法尾插需要先找到最后一个节点void insertEnd(Node** head, int value) { Node* newNode createNode(value); if (*head NULL) { *head newNode; return; } Node* temp *head; //获得地址后解引用next,循环找到next指针区域为NULL即为末尾节点 while(temp-next ! NULL) { temp temp-next; } //temp记录了原来的末尾节点设置temp的next指针区域指向新的末尾节点为newNode temp-next newNode; //新的末尾节点newNode的pre指针区域指向原来的末尾节点 newNode-pre temp; }我们来看图示创建第一个节点的时候执行if判断将head头指针指向第一个节点创建第二个节点的时候用临时指针接收头指针获得地址后解引用next,循环找到next指针区域为NULL即为末尾节点temp记录了原来的末尾节点设置temp的next指针区域指向新的末尾节点为newNode新的末尾节点newNode的pre指针区域指向原来的末尾节点删除节点删除过程只需要修改前后两个节点的指针即可void deleteNode(Node** head, int value) { Node* temp *head; while (temp ! NULL temp-data ! value) { temp temp-next; } if (temp NULL) { return; } //跳跃 if (temp-pre ! NULL) { temp-pre-next temp-next; } //如果删除的是第一个节点将头指针设置为第二个节点 else { *head temp-next; } if (temp-next ! NULL) { temp-next-pre temp-pre; } free(temp); }最后free(temp);最后释放内存空间void destory(Node* head) { while(head ! NULL) { Node* temp head; head head-next; free(temp); } }正向遍历和反向遍历方法void printForward(Node* head) { while(head ! NULL) { printf(%d , head-data); head head-next; } printf(\n); } void printBackWard(Node* head) { if (head NULL) return; while (head-next ! NULL) { head head-next; } while (head ! NULL) { printf(%d , head-data); head head-pre; } printf(\n); }完整代码如下#includestdio.h #includestdlib.h typedef struct Node { int data; struct Node* pre; struct Node* next; }Node; Node* createNode(int value) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-pre NULL; newNode-next NULL; return newNode; } void insertFront(Node** head, int value) { Node* newNode createNode(value); newNode-next *head; if (*head ! NULL) { (*head)-pre newNode; } *head newNode; } void insertEnd(Node** head, int value) { Node* newNode createNode(value); if (*head NULL) { *head newNode; return; } Node* temp *head; //获得地址后解引用next,循环找到next指针区域为NULL即为末尾节点 while(temp-next ! NULL) { temp temp-next; } //temp记录了原来的末尾节点设置temp的next指针区域指向新的末尾节点为newNode temp-next newNode; //新的末尾节点newNode的pre指针区域指向原来的末尾节点 newNode-pre temp; } void deleteNode(Node** head, int value) { Node* temp *head; while (temp ! NULL temp-data ! value) { temp temp-next; } if (temp NULL) { return; } //跳跃 if (temp-pre ! NULL) { temp-pre-next temp-next; } //如果删除的是第一个节点将头指针设置为第二个节点 else { *head temp-next; } if (temp-next ! NULL) { temp-next-pre temp-pre; } free(temp); } void printForward(Node* head) { while(head ! NULL) { printf(%d , head-data); head head-next; } printf(\n); } void printBackWard(Node* head) { if (head NULL) return; while (head-next ! NULL) { head head-next; } while (head ! NULL) { printf(%d , head-data); head head-pre; } printf(\n); } void destory(Node* head) { while(head ! NULL) { Node* temp head; head head-next; free(temp); } } int main() { Node* head NULL; insertFront(head, 10); insertFront(head, 20); insertFront(head, 30); insertFront(head, 40); printForward(head); printBackWard(head); deleteNode(head, 30); printForward(head); printBackWard(head); destory(head); }运行结果如下