C语言实现双向链表

1.版本一

由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 节点类
typedef struct Node {// 数据域int data;// 指针域struct Node* next;struct Node* pre;
}Node;// 别名
// 初始化链表
Node* initList() {Node* list = (Node*)malloc(sizeof(Node));list->data = 0;list->next = NULL;list->pre = NULL;return list;
}
// 头插法
void headInsert(int data, Node* list) {Node* node = (Node*)malloc(sizeof(Node));Node* pre = list;Node* next = list->next;node->data = data;pre->next = node;node->pre = pre;node->next = next;if (list->data != 0) {next->pre = node;}// 更新链表长度list->data++;
}
// 尾插法
void tailInsert(int data, Node* list) {// 为待插入节点分配内存Node* node = (Node*)malloc(sizeof(Node));// 获取待插入节点的前驱节点 前驱节点其实就是原来的尾节点Node* pre = list->next;while (pre->next) {pre = pre->next;}Node* next = pre->next;node->data = data;pre->next = node;node->pre = pre;node->next = next;// 更新链表长度list->data++;
}
// 删除方法
bool delete(int data, Node* list) {// 我们需要做的是删除指定节点值对应的第一个节点Node* cur = list->next;while (cur) {// 如果一旦遇到符合指定节点值的节点的话 那么就执行相关操作if (cur->data == data) {// 需要先考虑头删、尾删和中间删以及删除之后链表为空四种情况 总结之后 我们可以发现尾删和删除之后链表为空同属一种情况 都是只需要设置一条线即可 即前驱指向后继 但是其他情况需要设置两条线 即前驱指向后继 后继指向前驱cur->pre->next = cur->next;if (cur->next) {cur->next->pre = cur->pre;}free(cur);list->data--;return true;}cur = cur->next;}return false;
}
// 打印链表方法
void printList(Node* list) {Node* cur = list->next;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
int main() {Node* list = initList();headInsert(1, list);headInsert(2, list);headInsert(3, list);tailInsert(4, list);tailInsert(5, list);printList(list);// 3 2 1 4 5if (delete(5, list) == true) {printf("删除成功\n");}else {printf("删除失败\n");}printList(list);// 2 1 4 5
}

2.版本二(mj版本的双向链表 带有虚拟头节点)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1
// 我们的设计理念就是引入一个虚拟头节点 但是不引入头节点的标识以及尾节点的标识
// 节点类
typedef struct Node {int data;// 数据域struct Node* pre;struct Node* next;// 指针域
}Node;
// 初始化链表
Node* initList() {Node* list = (Node*)malloc(sizeof(Node));list->data = 0;list->pre = NULL;list->next = NULL;return list;
}
// 索引越界的处理
void outOfBounds(int index) {printf("索引为%d 索引越界了\n", index);
}
// 边界检查
void rangeCheck(int index, Node* list) {if (index < 0 || index >= list->data)outOfBounds(index);
}
// 针对添加方法的边界检查
void rangeCheckForAdd(int index, Node* list) {if (index < 0 || index > list->data)outOfBounds(index);
}
// 根据指定索引获取节点
Node* node(int index, Node* list) {// 对参数索引进行边界检查rangeCheck(index, list);Node* cur = list->next;for (int i = 0; i < index; ++i) {cur = cur->next;}return cur;
}
// 添加方法
void add(int index, int data, Node* list) {// 需要分成三种情况进行分析 一种情况是中间插入 需要设置四条线 一种情况是尾插 需要设置三条线 一种情况是头插 需要设置四条线 一种情况是对空链表进行插入操作 需要设置三条线 所以我们可以分成两种情况 一种是尾插的特殊情况 一中是其他位置插入// 对参数索引进行边界检查rangeCheckForAdd(index, list);// 为待插入节点分配内存Node* cur = (Node*)malloc(sizeof(Node));// 获取待插入节点的前驱节点 如果是头插的话 那么就需要特殊处理了Node* pre = index == 0 ? list : node(index - 1, list);// 获取待插入节点的后继节点Node* next = pre->next;cur->data = data;// 四种情况都要设置三条线 pre->next = cur;cur->pre = pre;cur->next = next;if (next)next->pre = cur;// 无论执行的是哪一种情况 都需要更新链表长度list->data++;
}
// 删除方法
int delete(int index, Node* list) {// 我们需要将问题分成三种情况去讨论 一种情况是中间删除 一种情况是尾删 一种情况是头删 如果是中间删除的话 那么我们需要操作的指针有两条 分别是前驱节点的后继节点还有后继节点的前驱节点 如果是尾删的话 那么就需要操作一条 即前驱节点指向后继节点 如果是头删的话 那么需要操作两条 同中间删除一样 如果是删除之后链表为空的话 那么就归结到尾删的情况中去考虑即可 并且复用尾删的代码Node* cur = node(index, list);// 我们保存一下待删除节点的节点值int delete = cur->data;// 通过待删除节点获取到他的前驱节点以及后继节点Node* pre = cur->pre;Node* next = cur->next;pre->next = next;if (next)next->pre = pre;// 我们还要去释放一下cur的内存 同时也解决了从cur指出的两条指针free(cur);// 更新一下链表的长度list->data--;// 返回待删除节点的节点值return delete;
}
// 定义一个方法 用于获取指定节点值对应的位置
int indexOf(int data, Node* list) {Node* cur = list->next;for (int i = 0; i < list->data; ++i) {if (cur->data == data)return i;cur = cur->next;}// 如果上述循环没有返回值的话 那么说明没有找到指定的节点值对应的节点return ELEMENT_NOT_FOUND;
}
// 获取指定索引处的节点值
int get(int index, Node* list) {return node(index, list)->data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {int data = node(index, list)->data;node(index, list)->data = newData;return data;
}
// 清空方法
void clear(Node* list) {Node* cur = list->next;Node* next;for (int i = 0; i < list->data; ++i) {next = cur->next;free(cur);cur = next;}// 清空链表之后链表长度为0list->data = 0;
}
// 判断链表是否包含指定节点值
bool contains(int data, Node* list) {return indexOf(data, list) != ELEMENT_NOT_FOUND;
}
// 判断链表是否为空
bool isEmpty(Node* list) {return list->data == 0;
}
// 获取链表长度
int size(Node* list) {return list->data;
}
// 打印链表的方法
void printList(Node* list) {Node* cur = list->next;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
// 定义一个主函数
int main() {// 创建一个链表Node* list = initList();// 头部添加 尾部添加add(0, 1, list);// 1add(0, 2, list);// 2 1add(0, 3, list);// 3 2 1add(0, 4, list);// 4 3 2 1add(size(list), 5, list);// 4 3 2 1 5// 打印链表printList(list);// 4 3 2 1 5// 头部删除 尾部删除delete(0, list);// 3 2 1 5delete(size(list) - 1, list);// 3 2 1// 打印链表printList(list);// 3 2 1// 获取头部元素printf("%d\n", get(0, list));// 3// 重置头部元素printf("%d\n", set(0, 4, list));// 3// 打印链表printList(list);// 4 2 1printf("%d\n", contains(4, list));// trueprintf("%d\n", isEmpty(list));// false// 清空链表clear(list);printf("%d\n", size(list));// 0return 0;
}

测试结果显示 这个代码符合预期