簡介
連結串列 (Linked List 或稱鏈結串列) 是串列 (List) 的一種，是一種常見的資料結構，利用這個資料結構也能進一步實作出其他的資料結構，例如堆疊 (Stack) 和佇列 (Queue) 等。
它的特性是能夠不使用連續的記憶體空間的情況下，能夠保有並使用一份連續的資料；相對來看，陣列則需要使用連續的記憶體空間。
他的的實作方式是每個節點除了記錄資料之外，還使用額外的指標指向下一個節點，將節點以此方式串連起來形成一個連結串列。
由以上的說明可以知道，使用連結串列的優點如下：
- 不需使用連續記憶體空間，不需事先指定串列大小。
- 能夠容易的修改指標，插入或移除節點。
但也有缺點如下：
- 使用額外的記憶體空間紀錄節點指標。
- 無法快速索引到某個節點，必須迭代搜索。
此資料結構可以實作的操作變化相當多，這裡實作以下幾種操作：
- getFirst：取得第一個節點。
- getLast：取得最後一個節點。
- addFirst：加入節點在最前面。
- addLast：加入節點到最後。
- addBefore：加入節點在某節點之前。
- addAfter：加入節點在某節點之後。
- removeFirst：移除第一個節點。
- removeLast：移除最後一個節點。
- remove：移除某一個節點。
- size：取得串列的數目。
連結串列也有許多種類，這邊實作兩種基本的連結串列版本：
單向連結串列 (Singly Linked List)
單向連結串列的每個節點只記錄了下一個節點(或者上一個節點)，而尾端的節點指向空值。如下圖：
插入新節點示意圖
移除節點示意圖
然而我們從上圖中可以看到，刪除節點的時候是刪除指定的節點 (node) 後面的節點 (node.next)，而不是刪除節點本身，在程式介面中不是很直覺，例如 remove(node)，結果被刪除的是 node.next。
那為什麼不直接刪除指定節點？因為必須要找到被刪除的節點的前一個節點 (node.previous)，將他的下一個節點重新指向，而在單向連結串列中沒辦法直接取得上一個節點，除非從頭開始找。
雙向連結串列 (Doubly Linked List)
而雙向連結串列則同時記錄了下一個節點和上一個節點，除了尾端節點的下一個節點指向空值外，第一個節點的前一個節點也指向空值。如下圖：
因為多紀錄了上一個節點，所以就能夠解決單向連結串列中所提到的問題。
語法
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
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinkedList
{
abstract class LinkedList<T>
{
public int Count { get; protected set; }
public Node<T> First { get; protected set; }
public Node<T> Last { get; protected set; }
abstract public void AddFirst(T value);
abstract public void AddLast(T value);
abstract public void AddBefore(Node<T> node, T value);
abstract public void AddAfter(Node<T> node, T value);
abstract public void RemoveFirst();
abstract public void RemoveLast();
abstract public void Remove(Node<T> node);
}
class Node<T>
{
public Node<T> Next { get; internal set; }
public Node<T> Previous { get; internal set; }
public T Value { get; internal set; }
public Node(T value)
{
Value = value;
}
}
}
|
單向連結串列
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
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinkedList
{
class SinglyLinkedList<T> : LinkedList<T>
{
public override void AddFirst(T value)
{
Node<T> node = new Node<T>(value);
if (Count == 0)
Last = node;
else
node.Next = First;
First = node;
++Count;
}
public override void AddLast(T value)
{
Node<T> node = new Node<T>(value);
if (Count == 0)
First = node;
else
Last.Next = node;
Last = node;
++Count;
}
public override void AddBefore(Node<T> node, T value)
{
Node<T> newNode = new Node<T>(value);
if (node == First)
{
First = newNode;
}
else
{
Node<T> preNode = FindPreviousNode(node);
preNode.Next = newNode;
}
newNode.Next = node;
++Count;
}
public override void AddAfter(Node<T> node, T value)
{
Node<T> newNode = new Node<T>(value);
newNode.Next = node.Next;
node.Next = newNode;
if (node == Last)
{
Last = newNode;
}
++Count;
}
public override void RemoveFirst()
{
if (Count == 0)
throw new IndexOutOfRangeException();
else if (Count == 1)
{
First = null;
Last = null;
}
else
{
Node<T> node = First.Next;
First.Next = null;
First = node;
}
--Count;
}
public override void RemoveLast()
{
if (Count == 0)
throw new IndexOutOfRangeException();
else if (Count == 1)
{
First = null;
Last = null;
}
else
{
Node<T> node = FindPreviousNode(Last);
node.Next = null;
Last = node;
}
--Count;
}
public override void Remove(Node<T> node)
{
if (node == First)
RemoveFirst();
else if (node == Last)
RemoveLast();
else
{
Node<T> preNode = FindPreviousNode(node);
if (preNode == null)
throw new IndexOutOfRangeException();
preNode.Next = node.Next;
node.Next = null;
--Count;
}
}
private Node<T> FindPreviousNode(Node<T> node)
{
Node<T> preNode = First;
while (preNode != null)
{
if (node == preNode.Next)
break;
preNode = preNode.Next;
}
return preNode;
}
}
}
|
雙向連結串列
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
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinkedList
{
class DoublyLinkedList<T> : LinkedList<T>
{
public override void AddFirst(T value)
{
Node<T> node = new Node<T>(value);
if (Count == 0)
Last = node;
else
{
node.Next = First;
First.Previous = node;
}
First = node;
++Count;
}
public override void AddLast(T value)
{
Node<T> node = new Node<T>(value);
if (Count == 0)
First = node;
else
{
Last.Next = node;
node.Previous = Last;
}
Last = node;
++Count;
}
public override void AddBefore(Node<T> node, T value)
{
Node<T> newNode = new Node<T>(value);
newNode.Previous = node.Previous;
node.Previous.Next = newNode;
node.Previous = newNode;
newNode.Next = node;
if (node == First)
{
First = newNode;
}
++Count;
}
public override void AddAfter(Node<T> node, T value)
{
Node<T> newNode = new Node<T>(value);
newNode.Next = node.Next;
node.Next.Previous = newNode;
node.Next = newNode;
newNode.Previous = node;
if (node == Last)
{
Last = newNode;
}
++Count;
}
public override void RemoveFirst()
{
if (Count == 0)
throw new IndexOutOfRangeException();
else if (Count == 1)
{
First = null;
Last = null;
}
else
{
Node<T> node = First.Next;
First.Next = null;
node.Previous = null;
First = node;
}
--Count;
}
public override void RemoveLast()
{
if (Count == 0)
throw new IndexOutOfRangeException();
else if (Count == 1)
{
First = null;
Last = null;
}
else
{
Node<T> node = Last.Previous;
Last.Previous = null;
node.Next = null;
Last = node;
}
--Count;
}
public override void Remove(Node<T> node)
{
if (node == First)
RemoveFirst();
else if (node == Last)
RemoveLast();
else
{
node.Previous.Next = node.Next;
node.Next.Previous = node.Previous;
node.Next = null;
node.Previous = null;
--Count;
}
}
}
}
|
Java
抽象類別
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
| public abstract class LinkedList<T> {
protected int count;
protected Node<T> first;
protected Node<T> last;
public Node<T> getFirst()
{
return first;
}
public Node<T> getLast()
{
return last;
}
public int size()
{
return count;
}
abstract public void addFirst(T value);
abstract public void addLast(T value);
abstract public void addBefore(Node<T> node, T value);
abstract public void addAfter(Node<T> node, T value);
abstract public void removeFirst();
abstract public void removeLast();
abstract public void remove(Node<T> node);
}
|
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
| public class Node<T>
{
private Node<T> previous;
private Node<T> next;
private T value;
public Node<T> getPrevious()
{
return previous;
}
void setPrevious(Node<T> previous)
{
this.previous = previous;
}
public Node<T> getNext()
{
return next;
}
void setNext(Node<T> next)
{
this.next = next;
}
public T getValue()
{
return value;
}
void setValue(T value)
{
this.value = value;
}
public Node(T value)
{
this.value = value;
}
}
|
單向連結串列
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
| public class SinglyLinkedList<T> extends LinkedList<T> {
@Override
public void addFirst(T value) {
Node<T> node = new Node<T>(value);
if (count == 0)
last = node;
else
node.setNext(first);
first = node;
++count;
}
@Override
public void addLast(T value) {
Node<T> node = new Node<T>(value);
if (count == 0)
first = node;
else
last.setNext(node);
last = node;
++count;
}
@Override
public void addBefore(Node<T> node, T value) {
Node<T> newNode = new Node<T>(value);
if (node == first)
{
first = newNode;
}
else
{
Node<T> preNode = findPreviousNode(node);
preNode.setNext(newNode);
}
newNode.setNext(node);
++count;
}
@Override
public void addAfter(Node<T> node, T value) {
Node<T> newNode = new Node<T>(value);
newNode.setNext(node.getNext());
node.setNext(newNode);
if (node == last)
{
last = newNode;
}
++count;
}
@Override
public void removeFirst() {
if (count == 0)
throw new ArrayIndexOutOfBoundsException();
else if (count == 1)
{
first = null;
last = null;
}
else
{
Node<T> node = first.getNext();
first.setNext(null);
first = node;
}
--count;
}
@Override
public void removeLast() {
if (count == 0)
throw new ArrayIndexOutOfBoundsException();
else if (count == 1)
{
first = null;
last = null;
}
else
{
Node<T> node = findPreviousNode(last);
node.setNext(null);
last = node;
}
--count;
}
@Override
public void remove(Node<T> node) {
if (node == first)
removeFirst();
else if (node == last)
removeLast();
else
{
Node<T> preNode = findPreviousNode(node);
if (preNode == null)
throw new ArrayIndexOutOfBoundsException();
preNode.setNext(node.getNext());
node.setNext(null);
--count;
}
}
private Node<T> findPreviousNode(Node<T> node)
{
Node<T> preNode = first;
while (preNode != null)
{
if (node == preNode.getNext())
break;
preNode = preNode.getNext();
}
return preNode;
}
}
|
雙向連結串列
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
| public class DoublyLinkedList<T> extends LinkedList<T> {
@Override
public void addFirst(T value) {
Node<T> node = new Node<T>(value);
if (count == 0)
last = node;
else
{
node.setNext(first);
first.setPrevious(node);
}
first = node;
++count;
}
@Override
public void addLast(T value) {
Node<T> node = new Node<T>(value);
if (count == 0)
first = node;
else
{
last.setNext(node);
node.setPrevious(last);
}
last = node;
++count;
}
@Override
public void addBefore(Node<T> node, T value) {
Node<T> newNode = new Node<T>(value);
newNode.setPrevious(node.getPrevious());
node.getPrevious().setNext(newNode);
node.setPrevious(newNode);
newNode.setNext(node);
if (node == first)
{
first = newNode;
}
++count;
}
@Override
public void addAfter(Node<T> node, T value) {
Node<T> newNode = new Node<T>(value);
newNode.setNext(node.getNext());
node.getNext().setPrevious(newNode);
node.setNext(newNode);
newNode.setPrevious(node);
if (node == last)
{
last = newNode;
}
++count;
}
@Override
public void removeFirst() {
if (count == 0)
throw new ArrayIndexOutOfBoundsException();
else if (count == 1)
{
first = null;
last = null;
}
else
{
Node<T> node = first.getNext();
first.setNext(null);
node.setPrevious(null);
first = node;
}
--count;
}
@Override
public void removeLast() {
if (count == 0)
throw new ArrayIndexOutOfBoundsException();
else if (count == 1)
{
first = null;
last = null;
}
else
{
Node<T> node = last.getPrevious();
last.setPrevious(null);
node.setNext(null);
last = node;
}
--count;
}
@Override
public void remove(Node<T> node) {
if (node == first)
removeFirst();
else if (node == last)
removeLast();
else
{
node.getPrevious().setNext(node.getNext());
node.getNext().setPrevious(node.getPrevious());
node.setNext(null);
node.setPrevious(null);
--count;
}
}
}
|
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
| #ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
template<typename T>
class LinkedList
{
public:
LinkedList()
{
count = 0;
first = 0;
last = 0;
}
~LinkedList()
{
if(first != last)
delete first;
delete last;
}
int size()
{
return count;
}
Node<T>* front()
{
return first;
}
Node<T>* back()
{
return last;
}
virtual void push_front(T value) = 0;
virtual void push_back(T value) = 0;
virtual void insert_before(Node<T>* node, T value) = 0;
virtual void insert_after(Node<T>* node, T value) = 0;
virtual void pop_front() = 0;
virtual void pop_back() = 0;
virtual void erase(Node<T>* node) = 0;
protected:
int count;
Node<T>* first;
Node<T>* last;
private:
};
#endif
|
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
| #ifndef NODE_H
#define NODE_H
template<typename T>
class Node
{
public:
Node(T v)
{
value = v;
previous = 0;
next = 0;
}
~Node()
{
if(previous != next)
delete previous;
delete next;
}
Node<T>* previous;
Node<T>* next;
T value;
protected:
private:
};
#endif
|
單向連結串列
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
| #ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H
#include <stdexcept>
#include "LinkedList.h"
#include "Node.h"
template<typename T>
class SinglyLinkedList : public LinkedList<T>
{
public:
void push_front(T value)
{
Node<T>* node = new Node<T>(value);
if (LinkedList<T>::count == 0)
LinkedList<T>::last = node;
else
node->next = LinkedList<T>::first;
LinkedList<T>::first = node;
++LinkedList<T>::count;
}
void push_back(T value)
{
Node<T>* node = new Node<T>(value);
if (LinkedList<T>::count == 0)
LinkedList<T>::first = node;
else
LinkedList<T>::last->next = node;
LinkedList<T>::last = node;
++LinkedList<T>::count;
}
void insert_before(Node<T>* node, T value)
{
Node<T>* newNode = new Node<T>(value);
if (node == LinkedList<T>::first)
{
LinkedList<T>::first = newNode;
}
else
{
Node<T>* preNode = find_previous_node(node);
preNode->next = newNode;
}
newNode->next = node;
++LinkedList<T>::count;
}
void insert_after(Node<T>* node, T value)
{
Node<T>* newNode = new Node<T>(value);
newNode->next = node->next;
node->next = newNode;
if (node == LinkedList<T>::last)
{
LinkedList<T>::last = newNode;
}
++LinkedList<T>::count;
}
void pop_front()
{
if (LinkedList<T>::count == 0)
throw std::out_of_range ("empty list");
else if (LinkedList<T>::count == 1)
{
LinkedList<T>::first = 0;
LinkedList<T>::last = 0;
}
else
{
Node<T>* node = LinkedList<T>::first->next;
LinkedList<T>::first->next = 0;
LinkedList<T>::first = node;
}
--LinkedList<T>::count;
}
void pop_back()
{
if (LinkedList<T>::count == 0)
throw std::out_of_range ("empty list");
else if (LinkedList<T>::count == 1)
{
LinkedList<T>::first = 0;
LinkedList<T>::last = 0;
}
else
{
Node<T>* node = find_previous_node(LinkedList<T>::last);
node->next = 0;
LinkedList<T>::last = node;
}
--LinkedList<T>::count;
}
void erase(Node<T>* node)
{
if (node == LinkedList<T>::first)
pop_front();
else if (node == LinkedList<T>::last)
pop_back();
else
{
Node<T>* preNode = find_previous_node(node);
if (preNode == 0)
throw std::out_of_range ("node not in list");
preNode->next = node->next;
node->next = 0;
--LinkedList<T>::count;
}
}
protected:
private:
Node<T>* find_previous_node(Node<T>* node)
{
Node<T>* preNode = LinkedList<T>::first;
while (preNode != 0)
{
if (node == preNode->next)
break;
preNode = preNode->next;
}
return preNode;
}
};
#endif
|
雙向連結串列
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
| #ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H
#include <stdexcept>
#include "LinkedList.h"
#include "Node.h"
template<typename T>
class DoublyLinkedList : public LinkedList<T>
{
public:
void push_front(T value)
{
Node<T>* node = new Node<T>(value);
if (LinkedList<T>::count == 0)
LinkedList<T>::last = node;
else
{
node->next = LinkedList<T>::first;
LinkedList<T>::first->previous = node;
}
LinkedList<T>::first = node;
++LinkedList<T>::count;
}
void push_back(T value)
{
Node<T>* node = new Node<T>(value);
if (LinkedList<T>::count == 0)
LinkedList<T>::first = node;
else
{
LinkedList<T>::last->next = node;
node->previous = LinkedList<T>::last;
}
LinkedList<T>::last = node;
++LinkedList<T>::count;
}
void insert_before(Node<T>* node, T value)
{
Node<T>* newNode = new Node<T>(value);
newNode->previous = node->previous;
node->previous->next = newNode;
node->previous = newNode;
newNode->next = node;
if (node == LinkedList<T>::first)
{
LinkedList<T>::first = newNode;
}
++LinkedList<T>::count;
}
void insert_after(Node<T>* node, T value)
{
Node<T>* newNode = new Node<T>(value);
newNode->next = node->next;
node->next->previous = newNode;
node->next = newNode;
newNode->previous = node;
if (node == LinkedList<T>::last)
{
LinkedList<T>::last = newNode;
}
++LinkedList<T>::count;
}
void pop_front()
{
if (LinkedList<T>::count == 0)
throw std::out_of_range ("empty list");
else if (LinkedList<T>::count == 1)
{
LinkedList<T>::first = 0;
LinkedList<T>::last = 0;
}
else
{
Node<T>* node = LinkedList<T>::first->next;
LinkedList<T>::first->next = 0;
node->previous = 0;
LinkedList<T>::first = node;
}
--LinkedList<T>::count;
}
void pop_back()
{
if (LinkedList<T>::count == 0)
throw std::out_of_range ("empty list");
else if (LinkedList<T>::count == 1)
{
LinkedList<T>::first = 0;
LinkedList<T>::last = 0;
}
else
{
Node<T>* node = LinkedList<T>::last->previous;
LinkedList<T>::last->previous = 0;
node->next = 0;
LinkedList<T>::last = node;
}
--LinkedList<T>::count;
}
void erase(Node<T>* node)
{
if (node == LinkedList<T>::first)
pop_front();
else if (node == LinkedList<T>::last)
pop_back();
else
{
node->previous->next = node->next;
node->next->previous = node->previous;
node->next = 0;
node->previous = 0;
--LinkedList<T>::count;
}
}
protected:
private:
};
#endif
|
延伸閱讀
堆疊 (Stack)
佇列 (Queue)
