双向链表实现(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"); }

完整代码如下：

#include<stdio.h> #include<stdlib.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); }

运行结果如下：