有序链表：
按关键值排序。删除链头时，就删除最小(/最大)的值，插入时，搜索插入的位置。
插入时需要比较O(N)，平均O(N/2)，删除最小(/最大)的在链头的数据时效率为O(1),
如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项，那么有序链表是一个不错的选择
优先级队列 可以使用有序链表来实现
有序链表的插入排序：
对一个无序数组，用有序链表来排序，比较的时间级还是O(N^2)
复制时间级为O(2*N)，因为复制的次数较少，第一次放进链表数据移动N次，再从链表复制到数组，又是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; /** * 有序链表 对数组进行插入排序 * @author stone */public class LinkedListInsertSort<T extends Comparable<T>> { private Link<T> first; //首结点 public LinkedListInsertSort() { } public boolean isEmpty() { return first == null; } public void sortList(T[] ary) { if (ary == null) { return; } //将数组元素插入进链表,以有序链表进行排序 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; //变更首结点，为下一结点 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) { 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(); //反转1 // h = Node.reverse1(head); // while (h != null) { // System.out.print(h.getData() + "\t"); // h = h.getNext(); // } //反转2 h = Node.reverse1(head); while (h != null) { System.out.print(h.getData() + "\t"); h = h.getNext(); } } } /* * 单链表的每个节点都含有指向下一个节点属性 */class Node { Object data;//数据对象 Node next; //下一节点 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; //反转后新的 头 Node q = head; //轮换结果：012,123,234,.... 10 null null while (head.next != null) { p = head.next; // 第1个 换成第2个 这时p表示原始序列头中的next head.next = p.next; // 第2个 换成第3个 p.next = q; //已经跑到第1位置的原第2个的下一个 就要变成 原第1个 q = p; //新的第1个 要变成 当前第一个 } return p; } //方法2 head没重置 static Node reverse2(Node head) { //将中间节点的指针指向前一个节点之后仍然可以继续向后遍历链表 Node p1 = head, p2 = head.next, p3; // 前 中 后 //轮换结果 ：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没变，当输出到0时，再请求0.next 为1 return p1; } } |
