数据结构-双链表

双链表其实和单链表区别不大

双链表的定义

双链表其实就是前后都可以走的链表，常规的单链表无法通过后一个节点来找到前面的节点，但双链表的单个节点同时存储了前一个和后一个节点。这便让双链表可以进行双向搜索。双链表通过这种方法降低了搜索的复杂度(在特定情况下)。

双链表的代码实现

#include<iostream> #include<stdio.h> using namespace std; struct Node{ Node* pre; Node* next; int data; }; int main(){ //创建链表并连起来 Node* A = new Node(); Node* B = new Node(); A -> next = B; A -> pre = NULL; B -> next = NULL; B -> pre = A; A -> data = 1; B -> data = 2; //尝试输出 //正向输出 Node* current = A; printf("%d\n" , current -> data); current = current -> next; printf("%d\n\n" , current -> data); //反向输出 current = B; printf("%d\n" , current -> data); current = current -> pre; printf("%d\n" , current -> data); }

便于展示，我就不弄特别麻烦了

你也可以对双链表进行删除操作

#include<iostream> #include<stdio.h> using namespace std; struct Node{ Node* pre; Node* next; int data; }; int main(){ //创建链表并连起来 Node* A = new Node(); Node* B = new Node(); Node* C = new Node(); A -> next = B; A -> pre = NULL; B -> next = C; B -> pre = A; C -> next = NULL; C -> pre = B; A -> data = 1; B -> data = 2; C -> data = 3; int pos; scanf("%d" , &pos); Node* current = A; //把 current 定位到你想删除的位置 for(int i = 0 ; i < pos ; i++){ current = current -> next; if(current == NULL){ printf("Failed\n"); return 0; } } //temp是要删除的前面一个 Node* temp = current -> pre; temp -> next = current -> next; delete current; //输出 current = A; while(current != NULL){ printf("%d " , current -> data); current = current -> next; } }

简单演示了一下

总结

双链表其实就是单链表的PLUS版本，没有什么特别不好理解的地方。