算法数据结构

用数组模拟双向循环链表

字数统计: 2.4k字   |   阅读时长: 11分
,

摘要: 用数组模拟双向循环链表

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

在文章 【模板】双向链表 中，我们实现了双向循环链表，并将其用在实现了 LFU，以及实现循环双端队列中。

在文章 邻接表，中我们学习了一种基于链表的数据结构: 邻接表。这种邻接表可以应用在桶、开散列表以及图和树存储中。

在文章 加索引的数组 和 加索引的链表 中，我们学习了对链表和数组中加各种索引的方式。

本文我们来看一种用数组模拟双向循环链表的实现方法，相关的基础知识可以看前面的几篇文章，重点是 【模板】双向链表 这篇文章，这里我们直接给出代码。首先先给出最常见的基于动态分配内存+指针的方式的单链表的实现，然后给出用数组模拟的实现方法。

【用数组模拟】与【动态分配内存+指针】的对比

(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
46
47
struct Node
{
    int value; 
    Node *prev, *next;
};

Node *head, *tail;

void init()
{
    // 新建链表
    head = new Node();
    tail = new Node();
    head -> next = tail;
    tail -> prev = head;
}

Node* insert(Node* p, int val)
{
    // 在 p 后插入新节点，数据为 val
    Node *tmp = new Node();
    tmp -> value = val;
    p -> next -> prev = tmp;
    tmp -> next = p -> next;
    p -> next = tmp;
    tmp -> prev = p;
    return tmp;
}

void remove(Node* p)
{
    // 删除节点 p
    p -> prev -> next = p -> next;
    p -> next -> prev = p -> prev;
    delete p;
}

void recycle()
{
    // 链表内存回收
    while(head != tail)
    {
        head = head -> next;
        delete head -> prev;
    }
    delete tail;
}

(2) 用数组模拟双向循环链表(模板)

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
struct Node
{
    int value;
    int prev, next;
};

const int SIZE = 2e5;
Node node[SIZE];
int head, tail, tot; 
// tot 表示 node 数组已使用的最右位置，而不是链表长度

void init()
{
    tot = 2;
    head = 1;
    tail = 2;
    node[head].next = tail;
    node[tail].prev = head;
}

int insert(int p, int val)
{
    // 在 p 后插入新节点，数据为 val
    int tmp = ++tot;
    node[tmp].value = val;
    node[node[p].next].prev = tmp;
    node[tmp].next = node[p].next;
    node[p].next = tmp;
    node[tmp].prev = p;
    return tmp;
}

void remove(int p)
{
    // 删除节点 p
    node[node[p].prev].next = node[p].next;
    node[node[p].next].prev = node[p].prev;
}

void recycle()
{
    memset(node, 0, sizeof(node));
    head = tail = tot = 0;
}

应用：136. 邻值查找

我们以题目 136. 邻值查找 来验证上面的代码模板。

在文章 加索引的数组 中，我们用 STL 的 list 组件实现了本题的链表解法，具体的算法以及使用 STL list 的代码可以参考那篇文章。

题目描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 $A_{i}$，求：

以及令上式取到最小值的 j（记为 $P_{i}$）。若最小值点不唯一，则选择使 $A_{j}$ 较小的那个。

算法

将 A 排序，然后串成链表。

1
2
sort(A.begin(), A.end());
list l(A.begin(), A.end());

此时对于 l 中的元素 it, it -> next 和 it -> prev 就是 it 的前驱和后继。

从 A[n-1] 开始处理，一直处理到 A[0]，处理完后将对应在链表中的元素删掉。

l 排序之后，我还需要原始下标 idx 对应到排序后的链表 l 中的哪个节点，对 l 建立索引，实现方式是 vector<list<int>::iterator> indexes，it = indexes[i] 表示排序前的数组节点 A[i] 在排序后的链表中对应的节点。

it 相邻的元素就是其前驱后继，输出答案是需要带上前驱或后继的原始下标，方案为在 l 的节点中加一个原始下标的字段，由于 l 是在排序 A 的基础上建立的，因此在排序 A 的时候就要带着原始下标的字段。

代码 (STL list)

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
#include <iostream>
#include <vector>
#include <cmath>
#include <list>
#include <algorithm>

using namespace std;

struct Item
{
    int val;
    int idx; // 反向索引
    Item(int v, int i):val(v),idx(i){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val < i2.val;
    }
};

int main()
{
    // 输入
    int n;
    cin >> n;
    vector<Item> A;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        A.emplace_back(v, i);
    }
    sort(A.begin(), A.end(), Cmp());

    // 链表
    vector<list<Item>::iterator> indexes(n);
    // indexes[i] := 原始位置为 i 的元素 A[i] 在链表中对应的元素
    list<Item> l;
    for(int i = n - 1; i >= 0; --i)
    {
        l.push_front(A[i]);
        indexes[A[i].idx] = l.begin();
    }

    // 枚举
    vector<Item> result;
    for(int i = n - 1; i >= 1; --i)
    {
        auto it = indexes[i];
        if(it == l.end()) continue;
        int a = it -> val;
        int x = -1, p = -1;
        if(it != l.begin())
        {
            --it;
            int x1 = it -> val;
            int p1 = it -> idx;
            x = x1;
            p = p1;
            ++it;
        }
        ++it;
        if(it != l.end())
        {
            int x2 = it -> val;
            int p2 = it -> idx;
            if(p == -1 || x2 - a < a - x)
            {
                x = x2;
                p = p2;
            }
        }
        --it;
        result.emplace_back(abs(a - x), p + 1);
        l.erase(it);
        indexes[i] = l.end();
    }
    int m = result.size();
    for(int i = m - 1; i >= 0; --i)
        cout << result[i].val << " " << result[i].idx << endl;
}

代码 (动态分配内存 + 指针)

算法与前面用 STL list 的代码完全一样，只是把 list 改为了本文的双向循环链表。

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
124
125
126
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Item
{
    int val;
    int idx; // 排序后的数组元素在原数组中的索引
    Item(){}
    Item(int v, int i):val(v),idx(i){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val < i2.val;
    }
};

struct Node
{
    int value; // 排序后的数组中的索引
    Node *prev, *next;
};

Node *head, *tail;

void init()
{
    // 新建链表
    head = new Node();
    tail = new Node();
    head -> next = tail;
    tail -> prev = head;
}

Node* insert(Node* p, int val)
{
    // 在 p 后插入新节点，数据为 val
    Node *tmp = new Node();
    tmp -> value = val;
    p -> next -> prev = tmp;
    tmp -> next = p -> next;
    p -> next = tmp;
    tmp -> prev = p;
    return tmp;
}

void remove(Node* p)
{
    // 删除节点 p
    p -> prev -> next = p -> next;
    p -> next -> prev = p -> prev;
    delete p;
}

void recycle()
{
    // 链表内存回收
    while(head != tail)
    {
        head = head -> next;
        delete head -> prev;
    }
    delete tail;
}

int main()
{
    // 输入
    int n;
    cin >> n;
    vector<Item> A;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        A.emplace_back(v, i);
    }
    sort(A.begin(), A.end(), Cmp());

    // 链表
    init();
    vector<Node*> indexes(n);
    for(int i = 0; i < n; ++i)
    {
        Node *node = insert(tail -> prev, i);
        indexes[A[i].idx] = node;
    }

    // 枚举
    vector<Item> result(n); // A[result[i]].val, A[result[i]].idx
    for(int i = n - 1; i >= 1; --i)
    {
        Node *node = indexes[i];
        if(node == tail)
            continue;
        int a = A[node -> value].val;
        int x = -1, p = -1;
        if(node -> prev != head)
        {
            x = A[node -> prev -> value].val;
            p = A[node -> prev -> value].idx;
        }
        if(node -> next != tail)
        {
            int x2 = A[node -> next -> value].val;
            int p2 = A[node -> next -> value].idx;
            if(p == -1 || x2 - a < a - x)
            {
                x = x2;
                p = p2;
            }
        }
        result[i].idx = p + 1;
        result[i].val = abs(x - a);
        remove(node);
        indexes[i] = tail;
    }
    for(int i = 1; i < n; ++i)
        cout << result[i].val << " " << result[i].idx << endl;
}

代码 (数组模拟双向循环链表)

算法与前面用 STL list 和双向循环链表的代码完全一样，这里只是把双向循环链表的部分改为了本文的用数组模拟的双向循环链表。

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
struct Node
{
    int value;
    int prev, next;
};

const int SIZE = 2e5;
Node node[SIZE];
int head, tail, tot;

void init()
{
    tot = 2;
    head = 1;
    tail = 2;
    node[head].next = tail;
    node[tail].prev = head;
}

int insert(int p, int val)
{
    // 在 p 后插入新节点，数据为 val
    int tmp = ++tot;
    node[tmp].value = val;
    node[node[p].next].prev = tmp;
    node[tmp].next = node[p].next;
    node[p].next = tmp;
    node[tmp].prev = p;
    return tmp;
}

void remove(int p)
{
    // 删除节点 p
    node[node[p].prev].next = node[p].next;
    node[node[p].next].prev = node[p].prev;
}

void recycle()
{
    memset(node, 0, sizeof(node));
    head = tail = tot = 0;
}

struct Item
{
    int val;
    int idx; // 反向索引
    Item(){}
    Item(int v, int i):val(v),idx(i){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val < i2.val;
    }
};

int main()
{
    // 输入
    int n;
    cin >> n;
    vector<Item> A;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        A.emplace_back(v, i);
    }
    sort(A.begin(), A.end(), Cmp());

    // 链表
    init();
    vector<int> indexes(n);
    for(int i = 0; i < n; ++i)
    {
        int nodeidx = insert(node[tail].prev, i);
        indexes[A[i].idx] = nodeidx;
    }

    // 枚举
    vector<Item> result(n); // A[result[i]].val, A[result[i]].idx
    for(int i = n - 1; i >= 1; --i)
    {
        int nodeidx = indexes[i];
        if(nodeidx == tail)
            continue;
        int a = A[node[nodeidx].value].val;
        int x = -1, p = -1;
        if(node[nodeidx].prev != head)
        {
            x = A[node[node[nodeidx].prev].value].val;
            p = A[node[node[nodeidx].prev].value].idx;
        }
        if(node[nodeidx].next != tail)
        {
            int x2 = A[node[node[nodeidx].next].value].val;
            int p2 = A[node[node[nodeidx].next].value].idx;
            if(p == -1 || x2 - a < a - x)
            {
                x = x2;
                p = p2;
            }
        }
        result[i].idx = p + 1;
        result[i].val = abs(x - a);
        remove(nodeidx);
        indexes[i] = tail;
    }
    for(int i = 1; i < n; ++i)
        cout << result[i].val << " " << result[i].idx << endl;
}

最后，我们给出一个解法和最终代码与本题非常相似的题目，参考这篇文章 结合链表容易删除的特点使用逆向思维

Share