單鏈表：
insertFirst：在表頭插入一個新的鏈接點，時間復雜度為O(1)
deleteFirst：刪除表頭的鏈接點，時間復雜度為O(1)
find：查找包含指定關鍵字的鏈接點，由于需要遍歷查找，平均需要查找N/2次，即O(N)
remove：刪除包含指定關鍵字的鏈接點，由于需要遍歷查找，平均需要查找N/2次，即O(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
|
public class LinkedList { private class Data{ private Object obj; private Data next = null; Data(Object obj){ this.obj = obj; } } private Data first = null; public void insertFirst(Object obj){ Data data = new Data(obj); data.next = first; first = data; } public Object deleteFirst() throws Exception{ if(first == null) throw new Exception("empty!"); Data temp = first; first = first.next; return temp.obj; } public Object find(Object obj) throws Exception{ if(first == null) throw new Exception("LinkedList is empty!"); Data cur = first; while(cur != null){ if(cur.obj.equals(obj)){ return cur.obj; } cur = cur.next; } return null; } public void remove(Object obj) throws Exception{ if(first == null) throw new Exception("LinkedList is empty!"); if(first.obj.equals(obj)){ first = first.next; }else{ Data pre = first; Data cur = first.next; while(cur != null){ if(cur.obj.equals(obj)){ pre.next = cur.next; } pre = cur; cur = cur.next; } } } public boolean isEmpty(){ return (first == null); } public void display(){ if(first == null) System.out.println("empty"); Data cur = first; while(cur != null){ System.out.print(cur.obj.toString() + " -> "); cur = cur.next; } System.out.print("\n"); } public static void main(String[] args) throws Exception { LinkedList ll = new LinkedList(); ll.insertFirst(4); ll.insertFirst(3); ll.insertFirst(2); ll.insertFirst(1); ll.display(); ll.deleteFirst(); ll.display(); ll.remove(3); ll.display(); System.out.println(ll.find(1)); System.out.println(ll.find(4)); } } |
|
1
2
3
4
5
|
1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 -> 4 -> null4 |
雙端鏈表(不是雙向鏈表)：
與單向鏈表的不同之處在保存有對最后一個鏈接點的引用(last)
insertFirst：在表頭插入一個新的鏈接點，時間復雜度O(1)
insertLast：在表尾插入一個新的鏈接點，時間復雜度O(1)
deleteFirst：刪除表頭的鏈接點，時間復雜度O(1)
deleteLast:：刪除表尾的鏈接點，由于只保存了表尾的鏈接點，而沒有保存表尾的前一個鏈接點(這里就體現(xiàn)出雙向鏈表的優(yōu)勢了)，所以在刪除表尾鏈接點時需要遍歷以找到表尾鏈接點的前一個鏈接點，需查找N-1次，也就是O(N)
有了這幾個方法就可以用雙端鏈表來實現(xià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
|
public class FirstLastList { private class Data{ private Object obj; private Data next = null; Data(Object obj){ this.obj = obj; } } private Data first = null; private Data last = null; public void insertFirst(Object obj){ Data data = new Data(obj); if(first == null) last = data; data.next = first; first = data; } public void insertLast(Object obj){ Data data = new Data(obj); if(first == null){ first = data; }else{ last.next = data; } last = data; } public Object deleteFirst() throws Exception{ if(first == null) throw new Exception("empty"); Data temp = first; if(first.next == null) last = null; first = first.next; return temp.obj; } public void deleteLast() throws Exception{ if(first == null) throw new Exception("empty"); if(first.next == null){ first = null; last = null; }else{ Data temp = first; while(temp.next != null){ if(temp.next == last){ last = temp; last.next = null; break; } temp = temp.next; } } } public void display(){ if(first == null) System.out.println("empty"); Data cur = first; while(cur != null){ System.out.print(cur.obj.toString() + " -> "); cur = cur.next; } System.out.print("\n"); } public static void main(String[] args) throws Exception { FirstLastList fll = new FirstLastList(); fll.insertFirst(2); fll.insertFirst(1); fll.display(); fll.insertLast(3); fll.display(); fll.deleteFirst(); fll.display(); fll.deleteLast(); fll.display(); } } |
|
1
2
3
4
|
1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> |
有序鏈表：
鏈表中的數(shù)據(jù)按從小到大排列
|
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
|
public class SortedList { private class Data{ private Object obj; private Data next = null; Data(Object obj){ this.obj = obj; } } private Data first = null; public void insert(Object obj){ Data data = new Data(obj); Data pre = null; Data cur = first; while(cur != null && (Integer.valueOf(data.obj.toString()) .intValue() > Integer.valueOf(cur.obj.toString()) .intValue())){ pre = cur; cur = cur.next; } if(pre == null) first = data; else pre.next = data; data.next = cur; } public Object deleteFirst() throws Exception{ if(first == null) throw new Exception("empty!"); Data temp = first; first = first.next; return temp.obj; } public void display(){ if(first == null) System.out.println("empty"); System.out.print("first -> last : "); Data cur = first; while(cur != null){ System.out.print(cur.obj.toString() + " -> "); cur = cur.next; } System.out.print("\n"); } public static void main(String[] args) throws Exception{ SortedList sl = new SortedList(); sl.insert(80); sl.insert(2); sl.insert(100); sl.display(); System.out.println(sl.deleteFirst()); sl.insert(33); sl.display(); sl.insert(99); sl.display(); } } |
|
1
2
3
4
|
first -> last : 2 -> 80 -> 100 -> 2first -> last : 33 -> 80 -> 100 -> first -> last : 33 -> 80 -> 99 -> 100 -> |
表的插入和刪除平均需要比較N/2次，即O(N)，但是獲取最小數(shù)據(jù)項只需O(1)，因為其始終處于表頭，對頻繁操作最小數(shù)據(jù)項的應用，可以考慮使用有序鏈表實現(xiàn)，如：優(yōu)先級隊列和數(shù)組相比，鏈表的優(yōu)勢在于長度不受限制，并且在進行插入和刪除操作時，不需要移動數(shù)據(jù)項，故盡管某些操作的時間復雜度與數(shù)組想同，實際效率上還是比數(shù)組要高很多。劣勢在于隨機訪問，無法像數(shù)組那樣直接通過下標找到特定的數(shù)據(jù)項 。
以上所述是小編給大家介紹的Java數(shù)據(jù)結構之鏈表(動力節(jié)點之Java學院整理)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網(wǎng)站的支持！
