模擬單鏈表
線性表：
線性表（亦作順序表）是最基本、最簡單、也是最常用的一種數據結構。
線性表中數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素之外，其它數據元素都是首尾相接的。
線性表的邏輯結構簡單，便于實現和操作。
在實際應用中，線性表都是以棧、隊列、字符串等特殊線性表的形式來使用的。
線性結構的基本特征為:
1．集合中必存在唯一的一個“第一元素”；
2．集合中必存在唯一的一個 “最后元素” ；
3．除最后一個元素之外，均有 唯一的后繼(后件)；
4．除第一個元素之外，均有 唯一的前驅(前件)。
鏈表：linked list
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的
每個數據項都被包含在“鏈結點”（Link）中。
鏈結點是一個類的對象，這類可叫做Link。鏈表中有許多類似的鏈結點，每個Link中都中包含有一個對下一個鏈結點引用的字段next。
鏈表對象本身保存了一個指向第一個鏈結點的引用first。(若沒有first，則無法定位)
鏈表不能像數組那樣(利用下標)直接訪問到數據項，而需要用數據間的關系來定位，即訪問鏈結點所引用的下一個鏈結點，而后再下一個，直至訪問到需要的數據
在鏈頭插入和刪除的時間復雜度為O(1)，因為只需要改變引用的指向即可
而查找、刪除指定結點、在指定結點后插入，這些操作都需要平均都需要搜索鏈表中的一半結點，效率為O(N)。
單鏈表：
以“結點的序列”表示線性表 稱作線性鏈表（單鏈表）
是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。(這組存儲單元既可以是連續的，也可以是不連續的)
鏈結點的結構：
存放結點值的數據域data;存放結點的引用 的指針域（鏈域）next
鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。
每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked 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
|
/** * 單鏈表:頭插法 后進先出 * 將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。 * 頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。 * 頭插法最先得到的是尾結點 * @author stone */public class SingleLinkedList<T> { private Link<T> first; //首結點 public SingleLinkedList() { } public boolean isEmpty() { return first == null; } public void insertFirst(T data) {// 插入 到 鏈頭 Link<T> newLink = new Link<T>(data); newLink.next = first; //新結點的next指向上一結點 first = newLink; } public Link<T> deleteFirst() {//刪除 鏈頭 Link<T> temp = first; first = first.next; //變更首結點，為下一結點 return temp; } public Link<T> find(T t) { Link<T> find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link<T> temp = first; first = first.next; //變更首結點，為下一結點 return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//表示到鏈尾還沒找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍歷 System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍歷 Link<T> p = first, q = first.next, t; while (q != null) {//指針反向，遍歷的數據順序向后 t = q.next; //no3 if (p == first) {// 當為原來的頭時，頭的.next應該置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環中的if里，把first.next 置空了, 而當q為null不執行循環時，p就為原來的最且一個數據項，反轉后把p賦給first first = p; displayList(); } class Link<T> {//鏈結點 T data; //數據域 Link<T> next; //后繼指針，結點 鏈域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList<Integer> list = new SingleLinkedList<Integer>(); list.insertFirst(33); list.insertFirst(78); list.insertFirst(24); list.insertFirst(22); list.insertFirst(56); list.displayList(); list.deleteFirst(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(24)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } } |
打印
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22 |
單鏈表:尾插法 、后進先出 ——若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。
尾插法建立鏈表時，頭指針固定不動，故必須設立一個尾部的指針，向鏈表右邊延伸，
尾插法最先得到的是頭結點。
|
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
|
public class SingleLinkedList2<T> { private Link<T> head; //首結點 public SingleLinkedList2() { } public boolean isEmpty() { return head == null; } public void insertLast(T data) {//在鏈尾 插入 Link<T> newLink = new Link<T>(data); if (head != null) { Link<T> nextP = head.next; if (nextP == null) { head.next = newLink; } else { Link<T> rear = null; while (nextP != null) { rear = nextP; nextP = nextP.next; } rear.next = newLink; } } else { head = newLink; } } public Link<T> deleteLast() {//刪除 鏈尾 Link<T> p = head; Link<T> q = head; while (p.next != null) {// p的下一個結點不為空，q等于當前的p(即q是上一個，p是下一個) 循環結束時，q等于鏈尾倒數第二個 q = p; p = p.next; } //delete q.next = null; return p; } public Link<T> find(T t) { Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //變更首結點，為下一結點 return temp; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {//表示到鏈尾還沒找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍歷 System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍歷 Link<T> p = head, q = head.next, t; while (q != null) {//指針反向，遍歷的數據順序向后 t = q.next; //no3 if (p == head) {// 當為原來的頭時，頭的.next應該置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環中的if里，把head.next 置空了, 而當q為null不執行循環時，p就為原來的最且一個數據項，反轉后把p賦給head head = p; displayList(); } class Link<T> {//鏈結點 T data; //數據域 Link<T> next; //后繼指針，結點 鏈域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>(); list.insertLast(33); list.insertLast(78); list.insertLast(24); list.insertLast(22); list.insertLast(56); list.displayList(); list.deleteLast(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(78)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } } |
打印
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33 |
模擬雙端鏈表，以鏈表實現棧和隊列
雙端鏈表：
雙端鏈表與傳統鏈表非常相似.只是新增了一個屬性-即對最后一個鏈結點的引用rear
這樣在鏈尾插入會變得非常容易，只需改變rear的next為新增的結點即可，而不需要循環搜索到最后一個節點
所以有insertFirst、insertLast
刪除鏈頭時，只需要改變引用指向即可；刪除鏈尾時，需要將倒數第二個結點的next置空，
而沒有一個引用是指向它的，所以還是需要循環來讀取操作
|
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
|
/** * 雙端鏈表 * @author stone */public class TwoEndpointList<T> { private Link<T> head; //首結點 private Link<T> rear; //尾部指針 public TwoEndpointList() { } public T peekHead() { if (head != null) { return head.data; } return null; } public boolean isEmpty() { return head == null; } public void insertFirst(T data) {// 插入 到 鏈頭 Link<T> newLink = new Link<T>(data); newLink.next = head; //新結點的next指向上一結點 head = newLink; } public void insertLast(T data) {//在鏈尾 插入 Link<T> newLink = new Link<T>(data); if (head == null) { rear = null; } if (rear != null) { rear.next = newLink; } else { head = newLink; head.next = rear; } rear = newLink; //下次插入時，從rear處插入 } public T deleteHead() {//刪除 鏈頭 if (isEmpty()) return null; Link<T> temp = head; head = head.next; //變更首結點，為下一結點 if (head == null) { <span style="white-space:pre"> </span>rear = head; } return temp.data; } public T find(T t) { if (isEmpty()) { return null; } Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } if (find == null) { return null; } return find.data; } public T delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //變更首結點，為下一結點 return temp.data; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {//表示到鏈尾還沒找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p.data; } public void displayList() {//遍歷 System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍歷 if (isEmpty()) { return; } Link<T> p = head, q = head.next, t; while (q != null) {//指針反向，遍歷的數據順序向后 t = q.next; //no3 if (p == head) {// 當為原來的頭時，頭的.next應該置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環中的if里，把head.next 置空了, 而當q為null不執行循環時，p就為原來的最且一個數據項，反轉后把p賦給head head = p; displayList(); } class Link<T> {//鏈結點 T data; //數據域 Link<T> next; //后繼指針，結點 鏈域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { TwoEndpointList<Integer> list = new TwoEndpointList<Integer>(); list.insertLast(1); list.insertFirst(2); list.insertLast(3); list.insertFirst(4); list.insertLast(5); list.displayList(); list.deleteHead(); list.displayList(); System.out.println("find:" + list.find(6)); System.out.println("find:" + list.find(3)); System.out.println("delete find:" + list.delete(6)); System.out.println("delete find:" + list.delete(5)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } } |
打印
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 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
45
46
47
48
49
50
51
52
53
54
55
|
public class LinkStack<T> { private TwoEndpointList<T> datas; public LinkStack() { datas = new TwoEndpointList<T>(); } // 入棧 public void push(T data) { datas.insertFirst(data); } // 出棧 public T pop() { return datas.deleteHead(); } // 查看棧頂 public T peek() { return datas.peekHead(); } //棧是否為空 public boolean isEmpty() { return datas.isEmpty(); } public static void main(String[] args) { LinkStack<Integer> stack = new LinkStack<Integer>(); for (int i = 0; i < 5; i++) { stack.push(i); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 0; i < 6; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } } } |
打印
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5 |
鏈表實現 隊列 用雙端鏈表實現：
|
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
|
public class LinkQueue<T> { private TwoEndpointList<T> list; public LinkQueue() { list = new TwoEndpointList<T>(); } //插入隊尾 public void insert(T data) { list.insertLast(data); } //移除隊頭 public T remove() { return list.deleteHead(); } //查看隊頭 public T peek() { return list.peekHead(); } public boolean isEmpty() { return list.isEmpty(); } public static void main(String[] args) { LinkQueue<Integer> queue = new LinkQueue<Integer>(); for (int i = 1; i < 5; i++) { queue.insert(i); } for (int i = 1; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); } for (int i = 1; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek2:" + peek); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } } } |
打印
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 ---- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1 |
