加索引的链表

摘要: 加索引的链表

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$0 背景

有些数据结构可以根据 key 快速找到其所在节点，例如哈希表、平衡树、Trie，跳表。这些可以看成是一种自带索引的数据结构(索引结构)。即将数据项(key)插入进去之后，可以随时根据给定的 key，可以快速查到它所在节点的位置。

作为对比，数组，链表就没有这种根据 key 快速找到其所在节点的特性，数据项(key)插入进去之后，如果想给定 key 找到对应的节点，只能线性扫描去找。(栈，队列，堆这三种数据结构，节点的组织方式依然是数组或链表，本质不变)。

对于数组或链表，如果想在插入数据之后通过 key 找到节点，可以通过借助索引结构给节点建立索引的方式实现。

建立索引时候，用于建立索引的字段(key)，以及使用的索引结构需要根据需求设计。

$1 索引链表

对于链表，可以手动建一层索引，使得通过 key 可以快速定位到对应的节点。链表同时又天然地支持快速插入删除节点，于是加索引的链表就可以形成支持快速插入，删除，查找的结构。

借助索引通过 key 快速找到节点之后，可以删除，在两侧插入，或者调度节点的位置，具体怎么做看需求。

维护索引只需要注意当节点删除后，索引也要删掉，当节点被调度到链表其它位置时，索引不用做修改。

索引结构需要根据需求设计，常见的方式是哈希索引(key 作为 HashMap 的键，链表节点作为值)和树形索引(key 作为 TreeMap 的键，链表节点作为值)

(1) 哈希索引

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

代码 (C++)

class MyLinkedList {
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        dummy = new ListNode(0); // dummy_node 存表长
        mapping = vector<ListNode*>();
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        int n = mapping.size();
        if(index < n && index >= 0)
            return mapping[index] -> val;
        else
            return -1;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        addAtIndex(mapping.size(), val);
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if(index < 0) index = 0;
        int n = mapping.size();
        if(index > n) index = n;
        ListNode *prev;
        if(index == 0)
            prev = dummy;
        else
            prev = mapping[index - 1];
        ListNode *cur = new ListNode(val);
        cur -> next = prev -> next;
        prev -> next = cur;
        mapping.push_back(nullptr);
        for(int i = n; i > index; --i)
            mapping[i] = mapping[i - 1];
        mapping[index] = cur;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        int n = mapping.size();
        if(index < n && index >= 0)
        {
            ListNode *prev;
            if(index == 0)
                prev = dummy;
            else
                prev = mapping[index - 1];
            prev -> next = prev -> next -> next;
            delete mapping[index];
            for(int i = index; i < n - 1; ++i)
                mapping[i] = mapping[i + 1];
            mapping.pop_back();
        }
    }

private:
    vector<ListNode*> mapping;
    ListNode *dummy;
};

146. LRU缓存机制

参考文章：力扣146-LRU,内存淘汰算法

460. LFU缓存

参考文章：力扣460-LFU

1429. 第一个唯一数字

给定一系列整数，插入一个队列中，找出队列中第一个唯一整数。

实现 FirstUnique 类：

FirstUnique(int[] nums) 用数组里的数字初始化队列。
int showFirstUnique() 返回队列中的 第一个唯一 整数的值。如果没有唯一整数，返回 -1。（译者注：此方法不移除队列中的任何元素）
void add(int value) 将 value 插入队列中。

算法：链表 + 哈希表

数据结构设计:

unordered_set<int> cnt2;
unordered_map<int,list<int>::iterator> cnt1;
list<int> l;

• 用链表维护所有的当前出现次数刚好一次的 key，始终从尾部插入，这使得链表有了插入顺序的信息，表头就是第一个出现一次的 key
• 用一个哈希集合维护出现次数达到 2 次的 key。
• 用一个哈希映射对链表做索引key -> 链表节点，当插入新节点时，先查这个哈希映射，如果能找到链表节点，需要将其删除，然后放到哈希集合，否则直接在链表上尾插。

代码 (C++)

class FirstUnique {
public:
    FirstUnique(vector<int>& nums) {
        for(int i: nums)
            add(i);
    }

    int showFirstUnique() {
        if(l.empty())
            return -1;
        return l.front();
    }

    void add(int value) {
        if(cnt2.count(value) > 0)
            return;
        if(cnt1.count(value) == 0)
        {
            l.push_back(value);
            cnt1[value] = --l.end();
        }
        else
        {
            cnt2.insert(value);
            l.erase(cnt1[value]);
            cnt1.erase(value);
        }
    }

private:
    unordered_set<int> cnt2;
    unordered_map<int,list<int>::iterator> cnt1;
    list<int> l;
};

432. 全 O(1) 的数据结构

请你实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串”” 。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串””。

算法：哈希表 + 双向链表

数据结构设计：

list<Bucket> buckets;
unordered_map<string, Index> mapping;

struct Bucket
{
    int val;
    list<string> keys;
    Bucket(int val):val(val)
    {
        keys = list<string>();
    }
};

struct Index
{
    list<Bucket>::iterator bucket_it;
    list<string>::iterator key_it;
    Index(list<Bucket>::iterator bucket_it, list<string>::iterator key_it):bucket_it(bucket_it),key_it(key_it){}
    Index(){}
};

• 用链表维护表示频数的桶，从表头到表尾频数依次增大
• 桶内用链表维护一个 key 的集合，表示出现次数为桶代表的频数的那些 key
• 用哈希表对桶节点以及保存 key 的数据节点做索引：key -> 桶节点，数据节点

代码

参考文章：力扣432-全O(1)的数据结构

---

(2) 树形索引

716. 最大栈

设计一个最大栈，支持 push、pop、top、peekMax 和 popMax 操作。

push(x) — 将元素 x 压入栈中。
pop() — 移除栈顶元素并返回这个值。
top() — 返回栈顶元素。
peekMax() — 返回栈中最大元素。
popMax() — 返回栈中最大的元素，并将其删除。如果有多个最大元素，只要删除最靠近栈顶的那个。

算法：链表 + 平衡树

数据结构设计：

list<int> l;
map<int, list<list<int>::iterator>> mapping;

• 用链表维护数据，插入始终从尾部插入，这样链表可以维护插入顺序。
• 用平衡树对链表做一层索引，key -> 链表节点集合，这里的链表节点集合仍然用链表维护，保持数据插入顺序的特性

代码 (C++)

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        l = list<int>();
        mapping = map<int, list<list<int>::iterator>>();
    }

    void push(int x) {
        l.push_back(x);
        mapping[x].push_back(--l.end());
    }

    int pop() {
        int x = l.back();
        l.pop_back();
        mapping[x].pop_back();
        if(mapping[x].empty())
            mapping.erase(x);
        return x;
    }

    int top() {
        return l.back();
    }

    int peekMax() {
        return mapping.rbegin() -> first;
    }

    int popMax() {
        int x = mapping.rbegin() -> first;
        auto it = mapping[x].back();
        l.erase(it);
        mapping[x].pop_back();
        if(mapping[x].empty())
            mapping.erase(x);
        return x;
    }

private:
    list<int> l;
    map<int, list<list<int>::iterator>> mapping;
};

---