Introduction
雖然動態陣列相當好用，某些時候也可以代替鏈結串列，然而，我們用動態陣列還是有許多無法完成的工作，例如我們要刪除中間的某一個節點，或是你的動態陣列要存的單一節點資料非常多，導致每次開兩倍依舊不是一個好的選項時。除此之外，鏈結串列還可以把兩個不同的串列用非常快的速度連接起來 (\(O(1)\)) ，也因此即使過了40年以上，他依舊是我們資料結構與演算法中必修的一部分。
鏈結串列主要分為兩種，一個是單向的，另一個則是雙向的。兩者各有優缺。
Pointer
在談到鏈結串列之前，我們先來談談指標。指標是一個變數，他存的是一個記憶體位置。在C++中，我們可以用*來宣告一個指標，例如
1
2
| int a = 10;
int *p = &a;
|
這樣我們就宣告了一個指標p，他指向了變數a。如果我們想要取得a的值，我們可以透過*p來取得。如果我們想要改變a的值，我們可以透過*p來改變。
1
2
| *p = 20;
std::cout << a << "\n";
|
對於一個結構，我們也可以宣告一個指標，例如
1
2
3
4
5
6
7
8
9
10
11
| struct Node {
int data;
Node *next;
};
Node *node = new Node;
node->data = 10;
node->next = nullptr;
std::cout << node->data << "\n";
delete node;
|
這樣我們就宣告了一個結構Node，並且宣告了一個指標node，他指向了一個Node的記憶體位置。我們可以透過->來取得結構中的成員。
而nullptr是一個空指標，他代表了一個空的記憶體位置，嘗試取得這個位置的值會導致RE。
Singly Link List
單向串列是最簡單的一種串列，每個節點只有一個指標指向下一個節點，最後一個節點則指向NULL。這種串列的優點是非常簡單，但缺點是如果要找到倒數第\(k\)個節點，則需要\(O(k)\)的時間複雜度。不過，如果你想要使用它來實作一個堆疊或佇列，這是一個非常好的選擇。
Description
在這個問題中，我們要實作一個堆疊，這個堆疊可以執行以下幾個操作
PUSH data：將一個數字data放入堆疊中POP：將堆疊最上面的數字移除TOP：取得堆疊中最上面的數字LINK to from：將兩個堆疊連接在一起，呈現from的堆疊在to的堆疊上面，並且from的堆疊會被清空
Singly Link List Template
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
| #include <iostream>
#include <vector>
namespace SinglyLinkList {
struct Node {
int data;
Node *next;
};
Node* createNode(int data) {
Node *node = new Node;
node->data = data;
node->next = nullptr;
return node;
}
inline void deleteNode(Node *node) {
delete node;
}
void deleteList(Node *head) {
}
class List {
public:
List() : head(nullptr) {}
~List() { deleteList(head); }
List& push_front(int data);
List& pop_front();
int top();
List& link(List && other);
bool empty() { return head == nullptr; }
int size() { return sz; }
private:
Node *head, *tail;
int sz;
};
List& List::push_front(int data) {
return *this;
}
List& List::pop_front() {
return *this;
}
int List::top() {
}
List& List::link(List && other) {
return *this;
}
}
const int PUSH{1};
const int POP{2};
const int FRONT{3};
const int LINK{4};
const int MAX_PILES{100010};
int main(void) {
std::ios::sync_with_stdio(0);std::cin.tie(0);
int operation_num;
std::cin >> operation_num;
std::vector<SinglyLinkList::List> piles_of_plates(MAX_PILES);
for (int i{0}; i < operation_num; ++i) {
int op, value, index, other;
std::cin >> op;
switch (op) {
case PUSH:
std::cin >> index >> value;
piles_of_plates[index].push_front(value);
std::cout << piles_of_plates[index].size() << "\n";
break;
case POP:
std::cin >> index;
piles_of_plates[index].pop_front();
break;
case FRONT:
std::cin >> index;
std::cout << piles_of_plates[index].top() << "\n";
break;
case LINK:
std::cin >> index >> other;
piles_of_plates[index].link(std::move(piles_of_plates[other]));
std::cout << piles_of_plates[index].size() << "\n";
break;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| 10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
3 1
2 1
3 1
4 1 2
3 1
|
Sample Output
Doubly Link List
雙向串列是一種比較複雜的串列，每個節點有兩個指標，一個指向前一個節點，另一個指向下一個節點。這種串列的優點是可以在前後新增或刪除節點。不過，他的缺點是需要多一個指標，因此他的記憶體使用量會比單向串列多一些，而且實作會複雜許多。
Code
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
| namespace DoublyLinkList {
struct Node {
int data;
Node *next, *prev;
};
Node* createNode(int data) {
Node *node = new Node;
node->data = data;
node->next = nullptr;
node->prev = nullptr;
return node;
}
inline void deleteNode(Node *node) {
delete node;
}
void deleteList(Node *head) {
while (head != nullptr) {
Node *next = head->next;
deleteNode(head);
head = next;
}
}
class List {
public:
List() : head(nullptr), tail(nullptr), sz(0) {}
~List() { deleteList(head); }
List& push_front(int data);
List& pop_front();
List& push_back(int data);
List& pop_back();
int front();
int back();
List& link(List && other);
bool empty() { return head == nullptr; }
int size() { return sz; }
private:
Node *head, *tail;
int sz;
};
List& List::push_front(int data) {
Node *node = createNode(data);
if (head == nullptr) {
head = tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}
sz++;
return *this;
}
List& List::pop_front() {
if (head == nullptr) return *this;
Node *next = head->next;
deleteNode(head);
head = next;
if (head == nullptr) tail = nullptr;
else head->prev = nullptr;
sz--;
return *this;
}
List& List::push_back(int data) {
Node *node = createNode(data);
if (tail == nullptr) {
head = tail = node;
} else {
node->prev = tail;
tail->next = node;
tail = node;
}
sz++;
return *this;
}
List& List::pop_back() {
if (tail == nullptr) return *this;
Node *prev = tail->prev;
deleteNode(tail);
tail = prev;
if (tail == nullptr) head = nullptr;
else tail->next = nullptr;
sz--;
return *this;
}
int List::top() {
if (head == nullptr) return -1;
return head->data;
}
}
|