算法数据结构

【模板】双向链表

字数统计: 2k字   |   阅读时长: 9分
, ,

摘要: 双向循环链表的实现

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

本文我们实现双向循环链表的代码模板。并用改模板解决 641. 设计循环双端队列。

双向链表

$1. 双向循环链表

(1) 节点定义

1
2
3
4
5
6
7
8
9
10
11
typedef int DLType;
const DLType DLTypeNULL = -1;

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

(2) 接口

迭代器相关

空链表的 head 和 tail 均指向 dummy_node。此时调用 get_head 和 get_tail 均返回 nullptr。

1
2
3
4
5
6
7
DLNode* get_head()            返回 dummy_node 后面的节点，空表返回 nullptr
DLNode* get_tail()            返回 dummy_node 前面的节点，空表返回 nullptr
bool is_dummy(DLNode *pos)     判断给定节点是否为虚拟头节点
bool is_head(DLNode *pos)      判断给定节点是否为头节点，空表返回 false
bool is_tail(DLNode *pos)      判断给定节点是否为尾结点，空表返回 false
DLNode* get_next(DLNode *pos)   返回给定节点的下一个节点，空表返回 nullptr，如果给定尾节点，则返回头结点
DLNode* get_prev(DLNode *pos)   返回给定节点的上一个节点 ，空表返回 nullptr，如果给定头结点，则返回尾节点

定点增删改查

对给定节点 pos 增删改查，不接受对 dummy_node 的修改和删除和查询，如果实参为 dummy_node 直接返回失败值。调用方代码要注意这个问题。

对 dummy_node 插入是可以的，相当于 insertHead()。

当调用方通过指针操作链表元素要获取相邻节点的时候，只用迭代器相关接口 get_next, get_prev 而不在调用侧访问 pos -> next, pos -> prev 可以减少 bug。

1
2
3
4
DLNode* remove(DLNode *pos)             返回被删点之后的节点，如果删点之后为空表返回 nullptr，如果被删点为 tail 则返回 head
DLNode* insert(DLNode *pos, DLType val)  新插入的节点在 pos -> next，返回新插入节点
bool change(DLNode* pos, DLType val)
DLType get(DLNode *pos)

头尾插入删除(栈和队列的接口)

1
2
3
4
5
6
bool insertHead(DLType val)   在 dummy_node 后面插入节点，满表直接返回 false
bool insertTail(DLType val)   在 dummy_node 前面插入节点，满表直接返回 false
bool removeHead(DLType val)   删除 dummy_node 后面的节点，空表直接返回 false
bool removeTail(DLType val)   删除 dummy_node 前面的节点，空表直接返回 false
DLType getHead(DLNode *pos)    获取 dummy_node 后面的节点值，空表返回 DLTypeNULL
DLType getTail(DLNode *pos)    获取 dummy_node 前面的节点值，空表返回 DLTypeNULL

其它

1
2
3
4
bool isEmpty()
bool isFull()
int size()
void traverse()

(3) 代码 C++ (模板: 双向循环链表)

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
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
{
private:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(DLTypeNULL);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    bool insertHead(DLType val)
    {
        if(isFull())
            return false;
        insert(head, val);
        return true;
    }

    bool insertTail(DLType val)
    {
        if(isFull())
            return false;
        insert(tail, val);
        return true;
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(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;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};

(4) 测试: 剑指 Offer 62. 圆圈中最后剩下的数字

注：模拟法 $O(NM)$ 超时，仅用于测试代码模板。正解参考文章 取模与分数取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lastRemaining(int n, int m) {
        DoubleCircleList *dclist = new DoubleCircleList();
        for(int i = 0; i < n; ++i)
        {
            dclist -> insertTail(i);
        }
        DLNode *iter = dclist -> get_head();
        while(dclist -> size() > 1)
        {
            for(int i = 0; i < m - 1; ++i)
                iter = dclist -> get_next(iter);
            iter = dclist -> remove(iter);
        }
        return dclist -> getHead();
    }
};

$2 应用

(1) 460. LFU缓存

(2) 641. 设计循环双端队列

问题

设计实现双端队列。
你的实现需要支持以下操作：

1
2
3
4
5
6
7
8
9
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。

代码：(直接实现循环双端队列)

  • 不使用双向循环链表模板
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
class MyCircularDeque {
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k) {
        capacity = k;
        head = new DoubleListNode(0);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if(isFull())
            return false;
        DoubleListNode *cur = new DoubleListNode(value);
        cur -> next = head -> next;
        cur -> prev = head;
        head -> next -> prev = cur;
        head -> next = cur;
        if(tail == head)
            tail = cur;
        ++length;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if(isFull())
            return false;
        DoubleListNode *cur = new DoubleListNode(value);
        cur -> next = head;
        cur -> prev = tail;
        tail -> next = cur;
        head -> prev = cur;
        tail = cur;
        ++length;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if(isEmpty())
            return false;
        DoubleListNode *tmp = head -> next;
        head -> next = tmp -> next;
        tmp -> next -> prev = head;
        delete tmp;
        --length;
        if(head -> next == head)
            tail = head;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if(isEmpty())
            return false;
        tail -> prev -> next = head;
        head -> prev = tail -> prev;
        delete tail;
        tail = head -> prev;
        --length;
        return true;
    }

    /** Get the front item from the deque. */
    int getFront() {
        if(isEmpty())
            return -1;
        return head -> next -> val;
    }

    /** Get the last item from the deque. */
    int getRear() {
        if(isEmpty())
            return -1;
        return tail -> val;
    }

    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return head == tail;
    }

    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return length == capacity;
    }

private:
    struct DoubleListNode {
        int val;
        DoubleListNode *next;
        DoubleListNode *prev;
        DoubleListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
    };

    DoubleListNode *head, *tail;
    int capacity;
    int length;
};

代码：使用模板

  • 使用循环双向链表模板，迭代器相关接口和定点增删改查的接口不用即可。
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
class MyCircularDeque {
public:
    MyCircularDeque(int k) {
        dclist = DoubleCircleList(k);
    }

    bool insertFront(int value) {
        return dclist.insertHead(value);
    }

    bool insertLast(int value) {
        return dclist.insertTail(value);
    }

    bool deleteFront() {
        return dclist.removeHead();
    }

    bool deleteLast() {
        return dclist.removeTail();
    }

    int getFront() {
        return dclist.getHead();
    }

    int getRear() {
        return dclist.getTail();
    }

    bool isEmpty() {
        return dclist.isEmpty();
    }

    bool isFull() {
        return dclist.isFull();
    }

private:
    DoubleCircleList dclist;
};
Share