算法数据结构

【模板】双向链表的懒释放

字数统计: 1.5k字   |   阅读时长: 6分
,

摘要: 双向链表的懒释放

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

$1 惰性更新与懒释放

惰性更新是一种面对频繁操作时，先把操作记下来，等查询时再把记下的操作一次性都做掉，这在很多时候可以提高性能，因为有时候操作可以合并。参考 惰性更新。

在基于数组的数据结构中对指定节点删除经常是一种比较重的操作，需要根据实际情况判断是否要用惰性更新的方式，即懒删除，具体的操作是只标记删除，但不调整节点，比如支持按 key 删除的堆，使用标记删除是一种可以采用的方案，参考 堆的标记删除。

对于基于指针的链式结构，虽然调整节点是高效的，但是空间的释放比较重，所以也需要判断是否使用惰性更新的方式，即懒释放。只调整节点，但不释放空间，例如在 Redis 中就有懒释放的配置。

链式结构的懒释放还有一个场景很有用处，即节点指针有时候会被其它辅助数据结构持有，那么删除节点很可能会使得辅助数据结构中持有的指针指向了非法区域，这个时候懒释放就有用了。

执行删除时，仅改动节点链接关系，被删的节点不释放而维护在一个表里，辅助数据机构的节点依然指向合法位置，此时需要一个方法可以快速查询该节点是否已经被删，表里的节点需要可以通过一个方法集中释放。

总结：懒释放需要 1 个结构和 3 个方法，一个结构是维护被删节点的，3 个方法分别是懒删除，判断节点是否被删，释放所有被删节点。

1
2
3
4
lazy_list
bool is_lazy(DLNode* pos) const
void delete_lazylist()
DLNode* remove_lazy(DLNode *pos)

$2 带懒释放的双向循环链表

(1) 懒释放

有的时候，链表外面会有别的数据结构持有链表的节点，在链表节点被其它数据结构持有期间，可能已经被某些逻辑删除掉了，后面从该数据结构访问其持有的链表节点时，就访问到了一个已经释放掉的位置。

解法是使用懒释放，删除的时候只改链接关系，不将节点删除，因为其它持有链表节点的数据结构中可能还有指针指向那个节点。

使用懒释放的双向循环链表，用另一个链表维护被删除的节点，在节点 node 被删的时候，将 node -> next 链接到该链表，然后把 node -> prev 置空，在判断数据结构中持有的链表节点 node 是否已经被删的时候，node -> prev 可以作为删除标记。

(2) 代码 (C++，模板)

带懒释放的双向循环链表。DoubleCircleList 除了懒释放相关的代码，其余部分与不带懒释放的双向循环链表模板完全一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;

struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
protected:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN);

    bool removeHead();
    bool removeTail();
    DLType getHead() const;
    DLType getTail() const;
    bool insertHead(DLType val);
    bool insertTail(DLType val);

    DLNode* insert(DLNode *pos, DLType val);
    DLType get(DLNode *pos) const;
    DLNode* remove(DLNode *pos);
    bool change(DLNode* pos, DLType val);

    DLNode* get_next(DLNode *pos) const;
    DLNode* get_prev(DLNode *pos) const;
    bool is_dummy(DLNode *pos) const;
    bool is_head(DLNode *pos) const;
    bool is_tail(DLNode *pos) const;
    DLNode* get_tail() const;
    DLNode* get_head() const;

    bool isEmpty() const;
    int size() const;
    bool isFull() const;
    void traverse() const;
};

class LazyDoubleCircleList: public DoubleCircleList
{
private:
    int lazy_size;
    DLNode *lazy_list;

public:
    LazyDoubleCircleList(int k=MAX_LEN):DoubleCircleList(k)
    {
        lazy_size = 0;
        lazy_list = new DLNode(0);
    }

    bool is_lazy(DLNode* pos) const
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return false;
        return !pos -> prev;
    }

    DLNode* remove_lazy(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        // 懒释放
        pos -> next = lazy_list -> next;
        pos -> prev = nullptr; // node -> prev 为空表示该节点已经被懒释放
        ++lazy_size;
        /* 立即释放
         * delete pos;
         * pos = nullptr;
         */
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool removeHead_lazy()
    {
        if(isEmpty())
            return false;
        remove_lazy(get_head());
        return true;
    }

    bool removeTail_lazy()
    {
        if(isEmpty())
            return false;
        remove_lazy(get_tail());
        return true;
    }

    void delete_lazylist()
    {
        DLNode *iter;
        while(lazy_list -> next)
        {
            iter = lazy_list -> next;
            lazy_list -> next = iter -> next;
            delete iter;
        }
        lazy_size = 0;
    }
};

(3) 测试: 1388. 3n 块披萨

1
2
3
4
5
每次选择最大的点，用一个最大堆维护。
每次取出 3 个点，放回 1 个点，需要 O(1) 插入删除
  可以用双向循环链表，堆中放节点指针，删除的时候只改链接关系，不将节点删除，因为堆中可能还有指针指向那个节点。
  也可以用数组模拟链表。
i 位置的点可以不做删除，只修改值，i - 1 和 i + 1 需要删掉(标记已删)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        LazyDoubleCircleList dclist;
        for(int i: slices) dclist.insertTail(i);
        priority_queue<PID, vector<PID>, Cmp> pq;
        DLNode *it = dclist.get_head();
        vector<DLNode*> deletelist;
        for(int i = 0; i < n; ++i)
        {
            pq.push(PID(it -> val, it));
            it = dclist.get_next(it);
        }
        int result = 0;
        for(int i = 0; i < n / 3; ++i)
        {
            while(dclist.is_lazy(pq.top().second))
                pq.pop();
            DLNode *cur = pq.top().second;
            pq.pop();
            result += cur -> val;
            int new_val = 0 - cur -> val;
            DLNode *it_left = dclist.get_prev(cur), *it_right = dclist.get_next(cur);
            new_val += it_left -> val + it_right -> val;
            dclist.remove_lazy(it_left);
            dclist.remove_lazy(it_right);
            dclist.change(cur, new_val);
            pq.push(PID(new_val, cur));
        }
        dclist.delete_lazylist();
        return result;
    }

private:
    using PID = pair<int, DLNode*>;

    struct Cmp
    {
        bool operator()(const PID& a1, const PID& a2) const
        {
            return a1.first < a2.first;
        }
    };
};
Share