C语言实现双向链表

 1、概念

        单向链表的构成使得节点的访问要按照链表的方向进行，某一单元的后继单元可以直接通过链指针（next指针）找到，但是想要找到其前驱单元，必须从链头重新开始查找。如果在节点中增加一个指针域指向其前驱节点，可以在牺牲空间代价的前提下，减少操作时间的代价。在单向链表基础上增加指向前驱单元指针（previous指针）的链表叫做双向链表。

        上图仅是个人理解，结合下面的代码所做的理解图，如有错误，请指正，在此先谢过。个人有自己的图示理解更好，便于理解后续的双向链表的相关操作的实现。

 2、代码实现

2.1、双向链表结构定义

/* 定义双向链表节点结构体 */
typedef struct DListNode {
	int data;				/* 数据域 */
	struct DListNode* prev;	/* 前驱指针 */
	struct DListNode* next;	/* 后继指针 */
} DListNode;

/* 定义双向链表 */
typedef struct {
	DListNode* head;		/* 头指针 */
	DListNode* tail;		/* 尾指针(可选，非必须) */
} DLinkedList;

2.2、基本操作实现

2.2.1、创建新节点

/**
 * @brief 创建双向链表新节点
 * @param val -- 新节点的数据
 * @return -- 创建的新节点
 */
DListNode* CreateNode(int val)
{
	DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
	if (newNode == NULL) {
		printf("内存分配失败！\n");
		exit(1);
	}
	newNode->data = val;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
}

2.2.2、插入操作

2.2.2.1、头部插入

/**
 * @brief 头部插入
 * @param list -- 已有的链表
 * @param val -- 头部插入节点的数据
 */
void InsertAtHead(DLinkedList* list, int val)
{
	DListNode* newNode = CreateNode(val);
	if (list->head == NULL) {					/* 空链表 */
		list->head = newNode;
		list->tail = newNode;					/* 若维护尾指针 */
	} else {
		newNode->next = list->head;				/* 新节点的后继指向原头节点 */
		list->head->prev = newNode;				/* 原头节点的前驱指向新节点 */
		list->head = newNode;					/* 更新头指针 */
	}
}

2.2.2.2、尾部插入

/**
 * @brief 尾部插入
 * @param list -- 已有的链表
 * @param val -- 尾部插入节点的数据
 */
void InsertAtTail(DLinkedList* list, int val)
{
	DListNode* newNode = CreateNode(val);
	if (list->head == NULL) {					/* 空链表 */
		list->head = newNode;
		list->tail = newNode;
	} else {
		DListNode* cur = list->head;
		while (cur->next != NULL) {				/* 找到尾节点 */
			cur = cur->next;
		}
		cur->next = newNode;					/* 原尾节点的后继指向新节点 */
		newNode->prev = cur;					/* 新节点的前驱指向原尾节点 */
		list->tail = newNode;					/* 更新尾指针 */
	}
}

2.2.2.3、指定位置插入

/**
 * @brief 指定位置插入
 * @param list -- 已存在的链表
 * @param index -- 插入位置
 * @param val -- 新插入节点的数据
 */
void InsertAtIndex(DLinkedList* list, int index, int val)
{
	if (index < 0) return;
	if (index == 0) {							/* 头部插入 */
		InsertAtHead(list, val);
		return;
	}

	DListNode* newNode = CreateNode(val);
	DListNode* cur = list->head;
	for (int i = 0; cur != NULL && i < index - 1; i++) {
		/* 移动到目标位置前一个节点 */
		cur = cur->next;
	}
	if (cur == NULL) {							/* 索引超出范