有序鏈表：
按關(guān)鍵值排序。刪除鏈頭時(shí)，就刪除最小(/最大)的值，插入時(shí)，搜索插入的位置。
插入時(shí)需要比較O(N)，平均O(N/2)，刪除最小(/最大)的在鏈頭的數(shù)據(jù)時(shí)效率為O(1),
如果一個(gè)應(yīng)用需要頻繁的存取(插入/查找/刪除)最小(/最大)的數(shù)據(jù)項(xiàng)，那么有序鏈表是一個(gè)不錯(cuò)的選擇
優(yōu)先級(jí)隊(duì)列 可以使用有序鏈表來實(shí)現(xiàn)
有序鏈表的插入排序：
對(duì)一個(gè)無(wú)序數(shù)組，用有序鏈表來排序，比較的時(shí)間級(jí)還是O(N^2)
復(fù)制時(shí)間級(jí)為O(2*N)，因?yàn)閺?fù)制的次數(shù)較少，第一次放進(jìn)鏈表數(shù)據(jù)移動(dòng)N次，再?gòu)逆湵韽?fù)制到數(shù)組，又是N次
每插入一個(gè)新的鏈結(jié)點(diǎn)，不需要復(fù)制移動(dòng)數(shù)據(jù)，只需要改變一兩個(gè)鏈結(jié)點(diǎn)的鏈域
|
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
|
import java.util.Arrays; import java.util.Random; /** * 有序鏈表 對(duì)數(shù)組進(jìn)行插入排序 * @author stone */public class LinkedListInsertSort<T extends Comparable<T>> { private Link<T> first; //首結(jié)點(diǎn) public LinkedListInsertSort() { } public boolean isEmpty() { return first == null; } public void sortList(T[] ary) { if (ary == null) { return; } //將數(shù)組元素插入進(jìn)鏈表,以有序鏈表進(jìn)行排序 for (T data : ary) { insert(data); } // } public void insert(T data) {// 插入 到 鏈頭, 以從小到大排序 Link<T> newLink = new Link<T>(data); Link<T> current = first, previous = null; while (current != null && data.compareTo(current.data) > 0) { previous = current; current = current.next; } if (previous == null) { first = newLink; } else { previous.next = newLink; } newLink.next = current; } public Link<T> deleteFirst() {//刪除 鏈頭 Link<T> temp = first; first = first.next; //變更首結(jié)點(diǎn)，為下一結(jié)點(diǎn) 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; //變更首結(jié)點(diǎn)，為下一結(jié)點(diǎn) 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) {//指針反向，遍歷的數(shù)據(jù)順序向后 t = q.next; //no3 if (p == first) {// 當(dāng)為原來的頭時(shí)，頭的.next應(yīng)該置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環(huán)中的if里，把first.next 置空了, 而當(dāng)q為null不執(zhí)行循環(huán)時(shí)，p就為原來的最且一個(gè)數(shù)據(jù)項(xiàng)，反轉(zhuǎn)后把p賦給first first = p; displayList(); } class Link<T> {//鏈結(jié)點(diǎn) T data; //數(shù)據(jù)域 Link<T> next; //后繼指針，結(jié)點(diǎn) 鏈域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); Random random = new Random(); int len = 5; Integer[] ary = new Integer[len]; for (int i = 0; i < len; i++) { ary[i] = random.nextInt(1000); } System.out.println("----排序前----"); System.out.println(Arrays.toString(ary)); System.out.println("----鏈表排序后----"); list.sortList(ary); list.displayList(); } } |
打印
|
1
2
3
4
5
6
7
8
9
|
----排序前---- [595, 725, 310, 702, 444] ----鏈表排序后---- List (first-->last): the data is 310 the data is 444 the data is 595 the data is 702 the data is 725 |
單鏈表反序:
|
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
|
public class SingleLinkedListReverse { public static void main(String[] args) { Node head = new Node(0); Node temp = null; Node cur = null; for (int i = 1; i <= 10; i++) { temp = new Node(i); if (i == 1) { head.setNext(temp); } else { cur.setNext(temp); } cur = temp; }//10.next = null; Node h = head; while (h != null) { System.out.print(h.getData() + "\t"); h = h.getNext(); } System.out.println(); //反轉(zhuǎn)1 // h = Node.reverse1(head); // while (h != null) { // System.out.print(h.getData() + "\t"); // h = h.getNext(); // } //反轉(zhuǎn)2 h = Node.reverse1(head); while (h != null) { System.out.print(h.getData() + "\t"); h = h.getNext(); } } } /* * 單鏈表的每個(gè)節(jié)點(diǎn)都含有指向下一個(gè)節(jié)點(diǎn)屬性 */class Node { Object data;//數(shù)據(jù)對(duì)象 Node next; //下一節(jié)點(diǎn) Node(Object d) { this.data = d; } Node(Object d, Node n) { this.data = d; this.next = n; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } //方法1 head被重置 static Node reverse1(Node head) { Node p = null; //反轉(zhuǎn)后新的 頭 Node q = head; //輪換結(jié)果：012,123,234,.... 10 null null while (head.next != null) { p = head.next; // 第1個(gè) 換成第2個(gè) 這時(shí)p表示原始序列頭中的next head.next = p.next; // 第2個(gè) 換成第3個(gè) p.next = q; //已經(jīng)跑到第1位置的原第2個(gè)的下一個(gè) 就要變成 原第1個(gè) q = p; //新的第1個(gè) 要變成 當(dāng)前第一個(gè) } return p; } //方法2 head沒重置 static Node reverse2(Node head) { //將中間節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)之后仍然可以繼續(xù)向后遍歷鏈表 Node p1 = head, p2 = head.next, p3; // 前 中 后 //輪換結(jié)果 ：012, 123, 234, 345, 456.... 9 10 null while (p2 != null) { p3 = p2.next; p2.next = p1; //指向后 變 指向前 p1 = p2; //2、3向前挪 p2 = p3; } head.next = null;//head沒變，當(dāng)輸出到0時(shí)，再請(qǐng)求0.next 為1 return p1; } } |
