模拟单链表
线性表：
线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表的逻辑结构简单，便于实现和操作。
在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。
线性结构的基本特征为:
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 |
