【Linux 完整测试代码】数据结构之双向链表
别摸鱼啦，说的就是你，学习编程从入门到放弃。掌握编程思维方式，远胜于死记硬背编程语法，不能再迷路了。
双向链表
图一 双向链表结构示意图
图二 双向链表创建流程示意图
为了清晰的理解双向链表的创建操作，请参考链表创建流程示意图。以下为双向链表创建步骤解析
/* 1. 当前节点的nextNode指向newNode 2. newNode的previoueNode指向currentNode3. newNode的nextNode指向nullptr防止出现野指针4. currentNode指向新创建的节点(newNode)
*/
currentNode->nextNode = staffInfo;
newNode->previousNode = currentNode;
newNode->nextNode = nullptr;
currentNode = newNode;双向链表的操作比较常见，肯定难不倒机智的小伙伴，咱们就直接进阶到双向循环链表一探究竟啦
双向循环链表
图三双向链表结构示意图
双向循环链表创建操作
双向循环链表的核心思想是双向、循环，也就是说要能够双向操作并且形成闭环，图文详解双向循环链表创建过程：
1. 新建节点
2. 头节点的 指向
3. 和互相指向
4. 的指向头节点
第五步 指向, 至此双向、循环完成闭环
/* 1. 头节点previousNode指向newNode 2. 当前节点的nextNode指向newNode 3. newNode的previoueNode指向currentNode3. newNode的nextNode指向头节点4. currentNode指向新创建的节点(newNode)
*/headerNode->previousNode = newNode;
currentNode->nextNode = newNode;
newNode->previousNode = currentNode;
newNode->nextNode = headerNode;
currentNode = newNode;
双向循环链表创建核心代码
为防止出现野指针需要将尾部node的指向
myData* headerNode, *currentNode;void DoubleLinkedList::createLinkedList()
{myData* newNode = new myData{0};if (!headerNode && !currentNode) {headerNode = currentNode = newNode;} else {headerNode->previousNode = newNode;currentNode->nextNode = newNode;newNode->previousNode = currentNode;newNode->nextNode = headerNode;currentNode = newNode;}
}
双向链表的插入操作也是个技术活，下面开始图文并茂， 注意有细节哦
1.找到要插入的节点位置
2. 注意点来了，划重点要考的
3. 最后一步的指向
双向循环链表的插入操作
图四 双向链表插入流程示意图
myData *newNode = new myData;
newNode->nextNode = myNode->nextNode;
myNode_1 = myNode->nexNode;
myNode_1->previousNode = newNode;
myNode->nextNode = newNode;
双向循环链表的遍历操作
双向循环链表可以从正 反两个方向进行数据遍历，咱们就直接开始双向遍历了哈
主要是先找到, 每次遍历需要先判断是不是尾部节点（的 是不是 指向了头节点）如果不是尾部节点，直接将指向的下一个节点，如果是尾部节点，就开始反向遍历
bool isBackwardsEcho = false;/* 是否遍历到了尾部节点 */
if (currentNode->nextNode == headerNode &&headerNode->previousNode == currentNode)isBackwardsEcho = true;/* 反向遍历 */
if (isBackwardsEcho) {/* 是否反向遍历到了头部节点 */(currentNode == headerNode) ?(currentNode = nullptr) :(currentNode = currentNode->previousNode);
} else /* 正向遍历 */currentNode = currentNode->nextNode;双向循环链表的删除操作
双向循环链表的删除操作，也有细节点需要注意，可以参考下面的代码逻辑
myData::~myData() {
/* 析构函数 进行一些内存释放等操作 */
}myData * p = headerNode;
this->currentNode = headerNode;while (currentNode) {/* 是否只有一个节点 */if (currentNode->nextNode == nullptr) { delete currentNode;currentNode = headerNode = nullptr;/* 不是尾部节点*/} else if (currentNode->nextNode != p) {currentNode = currentNode->nextNode;delete headerNode;headerNode = currentNode;/* 是尾部节点 */} else if (currentNode->nextNode == p) {delete currentNode;currentNode = headerNode = nullptr;}
}
呈上双向链表的完整示例代码，供给小伙伴学习交流，赶紧 ctrl-c ctrl-v 测试一下吧
/********************************************************
* Description: simply C++ linked demo
* Author: jiangxiaoyu
* Data: Fir Apr 28 2023
*********************************************************/#include
#include
#include
#include
#include typedef struct StaffInfo {int ages;int salary;int seniority;std::string name;std::string post;std::string education;void * previousNode;void * nextNode;~StaffInfo();
} StaffInfomation;StaffInfo::~StaffInfo() {ages = salary = seniority = 0;name = post = education = "";previousNode = nextNode = nullptr;
}class DoubleLinkedList {
public:DoubleLinkedList();void helper();bool isRegexInput(std::string str);std::string regexDigit(std::string str, std::string msg);void createLinkedList();void collectStaffInfomation(StaffInfomation *);void printStaffInfomation();void destoryStaffInfomation();void exitSystem();
private:StaffInfomation* headerNode,* currentNode;
};/* initialize member */
DoubleLinkedList::DoubleLinkedList():headerNode(nullptr),currentNode(nullptr) {
}void DoubleLinkedList::helper()
{std::cout << "\n\n" << std::endl;std::cout << "Simply staff information manager syatem" << std::endl;std::cout << "1) Create New Staff Information" << std::endl;std::cout << "2) Printf All Staff Information" << std::endl;std::cout << "3) Destory All Staff Information" << std::endl;std::cout << "4) Helper Manual" << std::endl;std::cout << "5) Exit" << std::endl;
}void DoubleLinkedList::collectStaffInfomation(StaffInfomation * staffInfo)
{std::cout << "-------------------------------" << std::endl;std::cout << "staff information system" << std::endl;std::cout << "\nstaff name:"; std::cin >> staffInfo->name;std::cout << "\nstaff ages:"; std::cin >> staffInfo->ages;std::cout << "\nstaff education:"; std::cin >> staffInfo->education;std::cout << "\nstaff post:"; std::cin >> staffInfo->post;std::cout << "\nstaff seniority:"; std::cin >> staffInfo->seniority;std::cout << "\nstaff salary:"; std::cin >> staffInfo->salary;
}void DoubleLinkedList::printStaffInfomation()
{StaffInfomation * LinkedHeader = headerNode;bool isBackwardsEcho = false;while (LinkedHeader) {std::cout << "-------------------------------" << std::endl;std::cout << "\tstaff information system" << std::endl;printf("\tstaff name:%s\n", LinkedHeader->name.data());printf("\tstaff ages:%d\n", LinkedHeader->ages);printf("\tstaff education:%s\n", LinkedHeader->education.data());printf("\tstaff post:%s\n", LinkedHeader->post.data());printf("\tstaff seniority:%d\n", LinkedHeader->seniority);printf("\tstaff salary:%d\n", LinkedHeader->salary);std::cout << "-------------------------------" << std::endl;if (LinkedHeader->nextNode == headerNode && headerNode->previousNode == LinkedHeader) {isBackwardsEcho = true;std::cout << "=========== already traverse list =============" << std::endl;}/* backwards traverse */if (isBackwardsEcho) {/* backwards traverse all list or not */(LinkedHeader == headerNode) ?(LinkedHeader = nullptr) :(LinkedHeader = (StaffInfomation*)LinkedHeader->previousNode);} else LinkedHeader = (StaffInfomation *)LinkedHeader->nextNode;}
}void DoubleLinkedList::createLinkedList()
{StaffInfomation * staffInfo = new StaffInfomation{0};if (!headerNode && !currentNode) {headerNode = currentNode = staffInfo;} else {headerNode->previousNode = staffInfo;currentNode->nextNode = staffInfo;staffInfo->previousNode = currentNode;staffInfo->nextNode = headerNode;currentNode = staffInfo;}collectStaffInfomation(staffInfo);
}void DoubleLinkedList::destoryStaffInfomation()
{StaffInfomation * p = headerNode;this->currentNode = headerNode;while (currentNode) {if (currentNode->nextNode == nullptr) { /* if only one node */delete currentNode;currentNode = headerNode = nullptr;} else if (currentNode->nextNode != (StaffInfomation*)p) {currentNode = (StaffInfomation*)currentNode->nextNode;delete headerNode;headerNode = currentNode;} else if ((StaffInfomation*)currentNode->nextNode == (StaffInfomation*)p) { /* if travse */delete currentNode;currentNode = headerNode = nullptr;}}
}int main(int argc, char ** argv)
{DoubleLinkedList test;do {test.helper();int cmd = 0; std::cout << "please input flag:"; std::cin >> cmd;switch (cmd) {case 1: test.createLinkedList(); break;case 2: test.printStaffInfomation(); break;case 3: test.destoryStaffInfomation(); break;case 4: test.helper(); break;default: std::cout << "input invalid!" << std::endl;}} while(true);return 0;
}
创作不易，动动发财的小手点个关注再走呗
