133 lines
2.7 KiB
C++
133 lines
2.7 KiB
C++
#ifndef LINKEDLIST_H
|
|
#define LINKEDLIST_H
|
|
|
|
#include <functional>
|
|
#include <unordered_map>
|
|
|
|
template<class Key, class Value>
|
|
class ListNode {
|
|
public:
|
|
Key key;
|
|
Value value;
|
|
|
|
ListNode* prev;
|
|
ListNode* next;
|
|
|
|
ListNode(Key k, Value v)
|
|
: key(k), value(v), prev(nullptr), next(nullptr) {}
|
|
};
|
|
|
|
template<class Key, class Value>
|
|
class LinkedList {
|
|
private:
|
|
ListNode<Key, Value>* head;
|
|
ListNode<Key, Value>* tail;
|
|
|
|
std::unordered_map<Key, ListNode<Key, Value>*> mp;
|
|
|
|
size_t sz;
|
|
|
|
public:
|
|
LinkedList() : sz(0) {
|
|
head = new ListNode<Key, Value>(Key(), Value());
|
|
tail = new ListNode<Key, Value>(Key(), Value());
|
|
head->next = tail;
|
|
tail->prev = head;
|
|
}
|
|
|
|
~LinkedList() {
|
|
auto cur = head;
|
|
while (cur) {
|
|
auto next = cur->next;
|
|
delete cur;
|
|
cur = next;
|
|
}
|
|
}
|
|
|
|
void insert_front(Key key, Value value) {
|
|
if (mp.count(key)) return;
|
|
|
|
auto node = new ListNode<Key, Value>(key, value);
|
|
|
|
node->next = head->next;
|
|
node->prev = head;
|
|
|
|
head->next->prev = node;
|
|
head->next = node;
|
|
|
|
mp[key] = node;
|
|
|
|
++sz;
|
|
}
|
|
|
|
void remove(Key key) {
|
|
if (!mp.count(key)) return;
|
|
|
|
auto node = mp[key];
|
|
|
|
node->prev->next = node->next;
|
|
node->next->prev = node->prev;
|
|
|
|
mp.erase(key);
|
|
delete node;
|
|
|
|
--sz;
|
|
}
|
|
|
|
ListNode<Key, Value>* find(Key key) {
|
|
if (!mp.count(key)) return nullptr;
|
|
return mp[key];
|
|
}
|
|
|
|
const ListNode<Key, Value>* find(Key key) const {
|
|
typename std::unordered_map<Key, ListNode<Key, Value>*>::const_iterator it = mp.find(key);
|
|
if (it == mp.end()) return nullptr;
|
|
return it->second;
|
|
}
|
|
|
|
void move_to_front(Key key) {
|
|
if (!mp.count(key)) return;
|
|
|
|
auto node = mp[key];
|
|
|
|
// 先摘掉
|
|
node->prev->next = node->next;
|
|
node->next->prev = node->prev;
|
|
|
|
// 再插到头
|
|
node->next = head->next;
|
|
node->prev = head;
|
|
|
|
head->next->prev = node;
|
|
head->next = node;
|
|
}
|
|
|
|
void remove_tail() {
|
|
if (tail->prev == head) return;
|
|
|
|
auto node = tail->prev;
|
|
|
|
node->prev->next = tail;
|
|
tail->prev = node->prev;
|
|
|
|
mp.erase(node->key);
|
|
delete node;
|
|
|
|
--sz;
|
|
}
|
|
|
|
size_t size() const {
|
|
return sz;
|
|
}
|
|
|
|
// Iterate from head -> tail (excluding sentinels)
|
|
void for_each(const std::function<void(const Key&, const Value&)>& visitor) const {
|
|
auto cur = head->next;
|
|
while (cur != tail) {
|
|
visitor(cur->key, cur->value);
|
|
cur = cur->next;
|
|
}
|
|
}
|
|
};
|
|
|
|
#endif |