山东省建设局网站监理员考试,网站制作邯郸,深圳响应式网站设计,服装定制软件视频讲解
哈希 双向链表
为什么要用双向链表#xff1f;
快速删除节点#xff08;O(1#xff09;#xff09;
如果是单链表的话#xff0c;删除一个节点时#xff0c;需要从头遍历#xff0c;找到前驱节点#xff0c;才能修改 prev-next#xff0c;导致 O(n)…视频讲解
哈希 双向链表
为什么要用双向链表
快速删除节点O(1
如果是单链表的话删除一个节点时需要从头遍历找到前驱节点才能修改 prev-next导致 O(n) 的时间复杂度。
双向链表存储了两个指针一个指针指向下一个节点另一个指针指向上一个节点前驱指针。所以我们可以根据前驱指针快速找到上一个节点然后移除掉当前节点。 demo
class LRUCache {
public:struct Node{int key,val;Node *prev,*next;Node(int k,int v) : key(k) , val(v) , prev(nullptr) , next(nullptr){}};mapint,Node*mp;Node *L,*R; //双哨兵int n; //LRU的总数//创建操作LRUCache(int capacity) {n capacity;L new Node(-1,-1);R new Node(-1,-1);L-next R;R-prev L;}//获取值操作 (获得值的时候需要注意如果有值存在哈希表中的话那么就要将这个值放在最新的地方)//比如 L | 2 1 4 | R //我们查询1这个数那么查完后需要变成 L | 2 4 1 | R int get(int key) {if(mp.count(key)){Node* node mp[key];remove(node); //在链表中移除该节点 通过双向指针移除insert(node-key,node-val); // 在链表中插入该节点return node-val;}else{return -1;}}//插入操作void put(int key, int value) {if(mp.count(key)){Node* node mp[key];remove(node);insert(key,value); //这里需要用给的key和value而不是node-key和node-val因为可能插入的是新的值}else{if(mp.size() n){Node* node L-next; //满了需要移除的节点remove(node);insert(key,value);}else{insert(key,value);}}}//以下为自定义新增函数 remove是移除节点的函数 insert是插入节点的函数//同时在链表和哈希表中删除nodevoid remove(Node* node){Node* pre node-prev;Node* nxt node-next;pre-next nxt;nxt-prev pre;mp.erase(node-key);}//同样要同时操作链表和哈希表void insert(int key,int val){Node* node new Node(key,val);Node* pre R-prev;//这里是最后一个插入的数//向右pre-next node;node-next R;//向左node-prev pre;R-prev node;mp[key] node;}};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj new LRUCache(capacity);* int param_1 obj-get(key);* obj-put(key,value);*/
