(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹)
目录
初识双向链表:
如图所示,双向链表的指针域有两个,一个指向后面的结点,一个指向前面的结点
优点就是便于访问结点的前后结点,提高效率
typedef struct { int id; char* name; }ElementType; /** 双向链表的结点,包含一个数据域,两个指针域 */ typedef struct DoublyNode { ElementType data; struct DoublyNode* prev; //指向前缀结点 struct DoublyNode* next; //指向后继结点 }DoublyNode; /** 双向链表 */ typedef struct DoublyLinkList { int length; DoublyNode* next; }DoublyLinkList;
双向链表的插入:
插入第一个位置的结点:
将ax插入第一个结点时,只需要将ax的next指向a1,ax的prev设为NULL,a1的prev和头指针都指向ax即可完成插入
//创建空结点 DoublyNode* node = (DoublyNode*)malloc(sizeof(DoublyNode)); node->data = element; node->prev = NULL; node->next = NULL; //在第一个位置插入结点 if (pos == 1) { //需要判断插入第一个位置并且插入时链表的长度为0 if (dlList->length == 0) { dlList->next = node; dlList->length++; return; } node->next = dlList->next; dlList->next = node; node->next->prev = node; dlList->length++; return; }
插入其他位置的结点:
和单链表一样,先通过循环找到要插入位置的前一个位置的结点,如图所示,要在a3处插入ax,需要先找到a2,然后将a2的next和a3的prev指向ax,然后ax的prev指向a2,ax的next指向a3
//在其他位置插入结点 DoublyNode* currNode = dlList->next; //通过循环找到该位置的前一个结点 for (int i = 1; currNode && i < pos - 1; i++) { currNode = currNode->next; } //判断该结点是否为空 if (currNode) { node->prev = currNode; if (currNode->next) { //如果前缀结点非空(因为空就表示没有后继结点了) //将插入位置处的前缀结点指向新结点 currNode->next->prev = node; } node->next = currNode->next; currNode->next = node; dlList->length++; }
双向链表的删除:
删除第一个结点:
如图所示,如果要删除第一个结点a1,只需要将头指针指向a2,然后将a2的prev指向NULL,最后释放掉a1即可
ElementType element; element.id = -999; //删除第一个结点 if (pos == 1) { DoublyNode* node = dlList->next; //判断结点是否为空 if (node) { element = node->data; dlList->next = node->next; //判断下一个结点是否为空 if (node->next) { //如果有第二个结点,那么设置第二个节点的前缀结点为null node->next->prev = NULL; } free(node); dlList->length--; } return element; }
删除其他位置的结点:
如图所示,删除a3,只需要将a3的前置结点a2的next指向a4,将a4的prev指向a2,最后释放掉a3即可
//删除其他位置结点 DoublyNode* node = dlList->next; //通过循环找到该结点 for (int i = 1; node && i < pos; i++) { node = node->next; } //判断该结点是否存在 if (node) { element = node->data; //判断该结点的下一个结点是否存在 if (node->next) { node->next->prev = node->prev; } node->prev->next = node->next; free(node); dlList->length--; } return element;