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 5
	if (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;
	}
	// 清空链表之后链表长度为0
	list->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);// 1
	add(0, 2, list);// 2 1
	add(0, 3, list);// 3 2 1
	add(0, 4, list);// 4 3 2 1
	add(size(list), 5, list);// 4 3 2 1 5
	// 打印链表
	printList(list);// 4 3 2 1 5
	// 头部删除 尾部删除
	delete(0, list);// 3 2 1 5
	delete(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 1
	printf("%d\n", contains(4, list));// true
	printf("%d\n", isEmpty(list));// false
	// 清空链表
	clear(list);
	printf("%d\n", size(list));// 0
	return 0;
}

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