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) {							/* 索引超出范