雙向鏈結串列實作

雙向鏈結串列代表的是結構中有二個指標，分別指向前面節點跟後面節點

img

結構定義

1
2
3
4
5
6

typedef int ElemType;
//定義節點
struct Node {
  ElemType data;
  Node *prev,*next;//前面節點與後面節點
};

初始化

以下程式碼是指把指向前面節點與後面節點的指標設為nullptr

1

head->prev = head->next = nullptr;

1
2
3
4
5
6
7
8
9
10
11
12

/**
 初始化鏈結串列
 */
Node* initLinkedList() {
  //頭節點
  Node* head = new (std::nothrow)Node;
  //頭節點記憶體分配失敗
  if(head == nullptr) return nullptr;
  //前面節點與後面節點全設為nullptr
  head->prev = head->next = nullptr;
  return head;
}

最前面新增節點

資料3要插入在最前面

img

步驟如下

  • 建立新節點
  • 新節點的next指向第一個節點
  • 新節點的prev指向頭節點
  • 頭節點的next指向新節點
  • 第一個節點的prev指向新節點(如果沒有第一個節點就不用做這個步驟)

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool addFirst(Node* head, const ElemType& ee) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return false;
  }
  //建立新節點
  Node* temp = new (std::nothrow)Node;
  if(temp == nullptr) return false;
  
  //新節點設定傳進來的資料
  temp->data = ee;
  
  //新節點的下一個節點是頭節點的下一個
  temp->next = head->next;
  //前面節點
  temp->prev = head;
  //頭節點的下一個是新節點
  head->next = temp;
  
  //下一個節點的前面節點，指向新建的節點
  if(temp->next != nullptr)
    temp->next->prev = temp;
  return true;
}

刪除節點

img

步驟如下

  • 將待刪除節點的前一個節點next指向待刪除節點的下一個節點
  • 將待刪除節點的下一個節點的prev指向待刪除節點的前一個節點
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 將節點刪除
 */
bool deleteNode(Node* node) {
  if(node == nullptr) {
    cout << "節點不存在" << endl;
    return false;
  }
  //node的前一個節點的next指向node的下一個節點
  node->prev->next = node->next;
  if(node->next != nullptr) {
    //node的下一個節點的prve指向node的prev
    node->next->prev = node->prev;
  }
  delete node;
  return true;
}

完整程式碼

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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308

using namespace std;
typedef int ElemType;
//定義節點
struct Node {
  ElemType data;
  Node *prev,*next;//前面節點與後面節點
};

/**
 初始化鏈結串列
 */
Node* initLinkedList() {
  //頭節點
  Node* head = new (std::nothrow)Node;
  //頭節點記憶體分配失敗
  if(head == nullptr) return nullptr;
  //前面節點與後面節點全設為nullptr
  head->prev = head->next = nullptr;
  return head;
}

/**
 鏈結串列記憶體回收
 參數為頭節點
 */
void destroyLinkedList(Node* head){
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return;
  }
  Node *temp; //暫存節點
  //繞行鏈結串列
  while(head != nullptr) {
    //先把下一個節點存起來
    temp = head->next;
    //刪掉目前的節點
    delete head;
    //把剛才存下來的節點作為頭節點
    head = temp;
  }
}

bool addFirst(Node* head, const ElemType& ee) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return false;
  }
  //建立新節點
  Node* temp = new (std::nothrow)Node;
  if(temp == nullptr) return false;
  
  //新節點設定傳進來的資料
  temp->data = ee;
  
  //新節點的下一個節點是頭節點的下一個
  temp->next = head->next;
  //前面節點
  temp->prev = head;
  //頭節點的下一個是新節點
  head->next = temp;
  
  //下一個節點的前面節點，指向新建的節點
  if(temp->next != nullptr)
    temp->next->prev = temp;
  return true;
}
bool addLast(Node* head, const ElemType& e) {
  if(head == nullptr) {
    cout << "鏈結不存在" << endl;
    return false;
  }
  //先找到尾節點
  Node *p = head;
  //判斷節點的下一個是否是null
  while(p->next != nullptr) {
    p = p->next;
  }
  
  //建立新節點
  Node* temp = new (std::nothrow)Node;
  if(temp == nullptr) return false;
  
  //新節點設定傳進來的資料
  temp->data = e;
  //新節點的前面節點
  temp->prev = p;
  
  //新節點的下一個節點是null
  temp->next = nullptr;
  
  //尾節點的下一個是新節點
  p->next = temp;
  return true;
}

/**
 在某個節點前插入元素
 參數Node* node 某個節點前
 參數ElemType& e 插入元素
 */
bool insert(Node* node, const ElemType& e) {
  if(node == nullptr) {
    cout << "節點不存在" << endl;
    return false;
  }
  //建立新節點
  Node* new_node = new Node;
  //塞入資料
  new_node->data = e;
  //新節點的前一個節點是插入節點的前一個
  new_node->prev = node->prev;
  //插入節點的前個節點的下一個是新節點
  node->prev->next = new_node;
  //插入節點的前一個節點是新節點
  node->prev = new_node;
  return true;
}
/**
 將節點刪除
 */
bool deleteNode(Node* node) {
  if(node == nullptr) {
    cout << "節點不存在" << endl;
    return false;
  }
  //node的前一個節點的next指向node的下一個節點
  node->prev->next = node->next;
  if(node->next != nullptr) {
    //node的下一個節點的prve指向node的prev
    node->next->prev = node->prev;
  }
  delete node;
  return true;
}
Node* getNode(const Node* head, const ElemType& e) {
  Node* p = head->next;//排除頭節點，從第1個節點開始繞
  while(p != nullptr) {
    //如果節點的資料與參數e相同，傳回節點
    if(p->data == e) return p;
    //移到下一個節點
    p = p->next;
  }
  //最後的是nullptr
  //返回nullptr
  return p;
}
void printList(const Node* head) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return;
  }
  //從head的下一個節點開始
  //head不存在值
  Node *p = head->next;
  while(p != nullptr) {
    cout << p->data << ",";
    //節點p換成下一個節點
    p = p->next;
  }
  cout << endl;
}
size_t size(Node* head) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return 0;
  }
  //不包含頭節點
  Node* p = head->next;
  size_t size = 0;
  //繞行到null
  while(p != nullptr) {
    p = p->next;
    size++;
  }
  return size;
  //遞迴方式
  //if(head == nullptr) return 0;
  //return size(head->next) + 1;
}
bool removeFirst(Node* head) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return false;
  }
  //只有頭節點，沒有後面的資料
  if(head->next == nullptr) {
    cout << "沒有任何節點" << endl;
    return false;
  }
  //不包含頭節點，取得頭節點的下一個
  Node* p = head->next;
  //頭節點的下一個是 p的下一個
  head->next = p->next;
  //p的下一個節點的prev是頭節點
  p->next->prev = head;
  //把p刪掉
  delete p;
  return true;
}
/**
 刪除鏈結串列，但頭節點不刪除
 */
void clearList(Node* head) {
  if(head == nullptr) {
    cout << "鏈結串列不存在" << endl;
    return;
  }
  //不包含頭節點，頭節點下一個節點不存在
  if(head->next == nullptr) {
    cout << "鏈結串列沒有節點" << endl;
    return;
  }
  Node* temp1;
  //從下一個節點開始刪，頭節點要保留
  Node* temp2 = head->next;
  while(temp2 != nullptr) {
    //下一個節點先丟到temp1
    temp1 = temp2->next;
    //刪掉temp2
    delete temp2;
    //temp2變成下一個節點
    temp2 = temp1;
  }
  
  head->next = nullptr;
}
/**
 刪除最後一個節點
 參數頭節點
 */
bool removeLast(Node* head) {
  if(head == nullptr) {
    cout << "鏈結不存在" << endl;
    return false;
  }
  
  Node *p = head;
  //判斷是不是至少有一個節點
  if(head->next == nullptr){
    cout << "鏈結沒結點" << endl;
    return false;
  }
  //先找到倒數第二個節點
  while(p->next->next != nullptr) {
    p = p->next;
  }
  //刪掉最後一個節點
  delete p->next;
  //把倒數第二個節點作為最後一個節點
  //下一個節點為null
  p->next = nullptr;
  return true;
}
int main() {
  //建立頭節點
  Node* head = initLinkedList();
  //增加節點
  addFirst(head, 1);
  //增加節點
  addFirst(head, 2);
  //增加節點
  addFirst(head, 3);
  //增加節點
  addFirst(head, 4);
  //印出所有節點
  printList(head);
  
  cout << "--------------" << endl;
  //增加節點
  addLast(head, 5);
  //增加節點
  addLast(head, 6);
  //增加節點
  addLast(head, 7);
  //增加節點
  addLast(head, 8);
  //印出所有節點
  printList(head);
  cout << "size = " << size(head) << endl;
  
  cout << "--------------" << endl;
  //取得資料為"5"的節點
  Node* node = getNode(head, 5);
  //在資料為"5"的節點之前，新增54
  insert(node, 54);
  //印出所有節點
  printList(head);
  //刪除54節點
  deleteNode(getNode(head, 54));
  //印出所有節點
  printList(head);
  
  //刪除第一個節點
  removeFirst(head);
  //印出所有節點
  printList(head);
  //刪除最後一個節點
  removeLast(head);
  //印出所有節點
  printList(head);
  
  //清空所有節點，(不包含頭節點)
  clearList(head);
  
  //釋放記憶體(包含頭節點)
  destroyLinkedList(head);
  return 0;
}

results matching ""

    No results matching ""