1.前言
这篇文章主要介绍双向链表的表示和实现。
2.双向链表
单链表中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱,则必须从表头指针出发。换句话说,在单链表中,查找直接后继结点的执行时间为 0(1),而查找直接前驱的执行时间为 0(n)。为克服单链表这种单向性的缺点,可利用双向链表(Double Linked List )。
双向链表是一种链表数据结构,每个节点都有两个指针,一个指向前一个节点,一个指向后一个节点。
1.定义
// 定义
typedef struct DNode {int data;struct DNode *prev; //前驱节点struct DNode *next; //后继节点
} DNode, *DoubleLinkList;
2.初始化
// 初始化
void initDoubleLinkList(DoubleLinkList *list) {*list = NULL;
}
3.插入
// 插入
void insertAtEnd(DoubleLinkList *list, int data) {DNode *newNode = (DNode *)malloc(sizeof(DNode));newNode->data = data;newNode->next = NULL;if (*list == NULL) {newNode->prev = NULL;*list = newNode;} else {DNode *current = *list;while (current->next != NULL) {current = current->next;}current->next = newNode;newNode->prev = current;}
}
4.清空
void clearDoubleLinkList(DoubleLinkList & doubleLinkList){DoubleLinkList p = doubleLinkList;p->next = nullptr;p->prior = nullptr;
}
5.返回链表中第一个与element相同的数据元素的下标
释放链表指针,调用free函数。
int locationDoubleLinkListElement(DoubleLinkList doubleLink,int element,int * position){DoubleLinkList p = doubleLink;int j = 1;while (p != NULL) {if (p->data == element) {* position = j;return 1;}p = p->next;j++;}return 0;
}
6.表长
int doubleLinkListLength(DoubleLinkList doubleLinkList){DNode * p = doubleLinkList->next;int length = 1;while (p != NULL) {p = p->next;length ++;}return length;
}
7.前驱节点
int priorDoubleElement(DoubleLinkList doubleLink,int element,int * priorElement){DoubleLinkList p = doubleLink;int j = 1;while (p != NULL) {if (p->data == element) {if (p->prev == NULL) {return 0;}* priorElement = p->prev->data;return 1;}p = p->next;j++;}return 0;
}
8.获取双向链表中的元素
int getDoubleLinkElement(DoubleLinkList doubleLink,int position,int *element){DoubleLinkList current = doubleLink;int j = 1;while (current != NULL && j< position) {current = current->next;j++;}if (!current || j > position) {//第i个元素不存在return 0;}* element = current->data;return 1;
}
9.删除
和单链表算法相同。
bool deleteDoubleLinkList(DoubleLinkList &doubleLinkList, int position){if (position < 1 || position > doubleLinkListLength(doubleLinkList)) {//删除位置非法return false;}DoubleLinkList p = doubleLinkList;int j = 0;while (p->next != nullptr && j < position - 1) {// 找到要删除结点的前一个结点p = p->next;++j;}if (j < position - 1 || p->next == nullptr) {return false; // 删除位置超出范围}DoubleLinkList q = p->next; // 要删除的结点p->next = q->next; // 前一个结点指向后一个结点free(q); // 释放删除结点的内存return true;
}
10.后继节点
int nextDoubleElement(DoubleLinkList doubleLink, int element, int *nextElement){DoubleLinkList p = doubleLink->next; // 从第一个数据节点开始遍历while (p != NULL) {if (p->data == element) {if (p->next == NULL) {return 0; // 没有后继节点}*nextElement = p->next->data; // 将后继节点的数据赋值给nextElementreturn 1; // 找到后继节点,返回1}p = p->next; // 移动到下一个节点}return 0; // 没有找到指定元素
}
11.遍历节点
void traverseDoubleLinkList(DoubleLinkList & doubleLinkList){DoubleLinkList p = doubleLinkList->next;while (p != nullptr) {cout<<p->data<<"\t";p = p->next;}cout<<endl;
}
12.完整代码
#include <stdio.h>
#include <stdlib.h>// 定义
typedef struct DNode {int data;struct DNode *prev; //前驱节点struct DNode *next; //后继节点
} DNode, *DoubleLinkList;// 初始化
void initDoubleLinkList(DoubleLinkList *list) {*list = NULL;
}
// 双向链表是否为空
int doubleLinkListEmpty(DoubleLinkList doubleLinkList){return doubleLinkList == NULL;
}
// 获取第position位置的数据元素
int getDoubleLinkElement(DoubleLinkList doubleLink,int position,int *element){DoubleLinkList current = doubleLink;int j = 1;while (current != NULL && j< position) {current = current->next;j++;}if (!current || j > position) {//第i个元素不存在return 0;}* element = current->data;return 1;
}
// 返回链表中第一个与element相同的数据元素的下标
int locationDoubleLinkListElement(DoubleLinkList doubleLink,int element,int * position){DoubleLinkList p = doubleLink;int j = 1;while (p != NULL) {if (p->data == element) {* position = j;return 1;}p = p->next;j++;}return 0;
}
// 前驱节点
int priorDoubleElement(DoubleLinkList doubleLink,int element,int * priorElement){DoubleLinkList p = doubleLink;int j = 1;while (p != NULL) {if (p->data == element) {if (p->prev == NULL) {return 0;}* priorElement = p->prev->data;return 1;}p = p->next;j++;}return 0;
}
// 后继节点
int nextDoubleElement(DoubleLinkList doubleLink, int element, int *nextElement){DoubleLinkList p = doubleLink->next; // 从第一个数据节点开始遍历while (p != NULL) {if (p->data == element) {if (p->next == NULL) {return 0; // 没有后继节点}*nextElement = p->next->data; // 将后继节点的数据赋值给nextElementreturn 1; // 找到后继节点,返回1}p = p->next; // 移动到下一个节点}return 0; // 没有找到指定元素
}
// 删除双向链表中的指定位置的节点
int deleteDoubleLinkList(DoubleLinkList *doubleLink, int index) {if (*doubleLink == NULL || index < 1) {// 链表为空或者索引无效,无法删除return 0;}DoubleLinkList current = *doubleLink;// 如果要删除的是第一个节点if (index == 1) {*doubleLink = current->next; // 更新头指针if (*doubleLink != NULL) {(*doubleLink)->prev = NULL; // 更新新的第一个节点的前驱指针}free(current); // 释放删除的节点内存return 1; // 返回删除成功}int position = 1;// 查找要删除的节点while (current != NULL && position < index) {current = current->next;position++;}// 如果current为空,说明索引超出范围if (current == NULL) {return 0; // 删除失败}// 处理前驱节点的next指针if (current->prev != NULL) {current->prev->next = current->next;}// 处理后继节点的prev指针if (current->next != NULL) {current->next->prev = current->prev;}// 释放要删除的节点的内存free(current);return 1; // 返回删除成功
}// 插入
void insertAtEnd(DoubleLinkList *list, int data) {DNode *newNode = (DNode *)malloc(sizeof(DNode));newNode->data = data;newNode->next = NULL;if (*list == NULL) {newNode->prev = NULL;*list = newNode;} else {DNode *current = *list;while (current->next != NULL) {current = current->next;}current->next = newNode;newNode->prev = current;}
}// 使用数组生成测试数据
void createDoubleLinkList(DoubleLinkList *linkList, int values[], int size) {initDoubleLinkList(linkList); // Initialize the doubly linked listfor (int i = 0; i < size; i++) {insertAtEnd(linkList, values[i]); // Insert each element into the list}
}
int doubleLinkListLength(DoubleLinkList doubleLinkList){DNode * p = doubleLinkList->next;int length = 1;while (p != NULL) {p = p->next;length ++;}return length;
}
// 打印
void printList(DoubleLinkList list) {printf("**********\t链表数据元素\t**********\n");while (list != NULL) {printf("%d ", list->data);list = list->next;}printf("\n");
}
void traverseDoubleLinkList(DoubleLinkList doubleLinkList){while (doubleLinkList != NULL) {printf("%d ", doubleLinkList->data);doubleLinkList = doubleLinkList->next;}printf("\n");
}
void debugDoubleLinkInformation(char * string){printf("\n********** [测试%s] **********\n",string);
}
int main(int argc, const char *argv[]) {DoubleLinkList list;int element;printf("初始化双向节点\t✅\n");initDoubleLinkList(&list);if (doubleLinkListEmpty(list)) {printf("空链表\t✅\n");}// 使用数据初始化数据int testData[] = {10, 20, 30, 40, 50};int dataSize = sizeof(testData) / sizeof(testData[0]);// 创建双向链表测试数据createDoubleLinkList(&list, testData, dataSize);// 打印双向链表中的元素printList(list);debugDoubleLinkInformation("双向链表表长");if (!doubleLinkListEmpty(list)) {printf("链表不为空,表长:%d\t✅\n",doubleLinkListLength(list));}debugDoubleLinkInformation("双向链表中的数据元素");if (!getDoubleLinkElement(list, 0, &element)) {printf("非法位置\t✅\n");}if (getDoubleLinkElement(list, 1, &element)) {printf("第1个位置的数据元素下标为:%d\t✅\n",element);}if (getDoubleLinkElement(list, 2, &element)) {printf("第2个位置的数据元素下标为:%d\t✅\n",element);}if (getDoubleLinkElement(list, 5, &element)) {printf("第5个位置的数据元素下标为:%d\t✅\n",element);}if (!getDoubleLinkElement(list, 6, &element)) {printf("非法位置\t✅\n");}debugDoubleLinkInformation("双向链表中的下标");int position;if (locationDoubleLinkListElement(list, 10, &position)) {printf("数据元素10的下标为:%d\t✅\n",position);}if (locationDoubleLinkListElement(list, 20, &position)) {printf("数据元素20的下标为:%d\t✅\n",position);}if (locationDoubleLinkListElement(list, 50, &position)) {printf("数据元素50的下标为:%d\t✅\n",position);}if (!locationDoubleLinkListElement(list, 60, &position)) {printf("数据元素50的下标不存在\t✅\n");}debugDoubleLinkInformation("双向链表中的前驱节点");int priorElement;if (!priorDoubleElement(list, 10, &priorElement)) {printf("数据元素10的前驱节点不存在\t✅\n");}if (priorDoubleElement(list, 20, &priorElement)) {printf("数据元素20的前驱节点为:%d\t✅\n",priorElement);}if (priorDoubleElement(list, 30, &priorElement)) {printf("数据元素30的前驱节点为:%d\t✅\n",priorElement);}if (priorDoubleElement(list, 40, &priorElement)) {printf("数据元素40的前驱节点为:%d\t✅\n",priorElement);}if (priorDoubleElement(list, 50, &priorElement)) {printf("数据元素40的前驱节点为:%d\t✅\n",priorElement);}if (!priorDoubleElement(list, 100, &priorElement)) {printf("数据元素100的前驱节点不存在\t✅\n");}debugDoubleLinkInformation("双向链表中的后继节点");int nextElement;if (nextDoubleElement(list, 10, &nextElement)) {printf("数据元素10的后继节点为:%d\t✅\n",nextElement);}if (nextDoubleElement(list, 20, &nextElement)) {printf("数据元素20的后继节点为:%d\t✅\n",nextElement);}if (nextDoubleElement(list, 30, &nextElement)) {printf("数据元素30的后继节点为:%d\t✅\n",nextElement);}if (nextDoubleElement(list, 40, &nextElement)) {printf("数据元素40的后继节点为:%d\t✅\n",nextElement);}if (!nextDoubleElement(list, 50, &nextElement)) {printf("数据元素50的后继节点不存在\t✅\n");}if (!nextDoubleElement(list, 100, &nextElement)) {printf("数据元素100的后继节点不存在\t✅\n");}debugDoubleLinkInformation("双向链表删除功能");printf("删除之前的链表\n");traverseDoubleLinkList(list);if (deleteDoubleLinkList(&list, 5)) {printf("删除之后的链表\n");traverseDoubleLinkList(list);}else{printf("删除失败\n");}return 0;
}