單鏈表：
insertFirst：在表頭插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度為O(1)
deleteFirst：刪除表頭的鏈接點(diǎn)，時(shí)間復(fù)雜度為O(1)
find：查找包含指定關(guān)鍵字的鏈接點(diǎn)，由于需要遍歷查找，平均需要查找N/2次，即O(N)
remove：刪除包含指定關(guān)鍵字的鏈接點(diǎn)，由于需要遍歷查找，平均需要查找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 |
雙端鏈表(不是雙向鏈表)：
與單向鏈表的不同之處在保存有對(duì)最后一個(gè)鏈接點(diǎn)的引用(last)
insertFirst：在表頭插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
insertLast：在表尾插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
deleteFirst：刪除表頭的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
deleteLast:：刪除表尾的鏈接點(diǎn)，由于只保存了表尾的鏈接點(diǎn)，而沒(méi)有保存表尾的前一個(gè)鏈接點(diǎn)(這里就體現(xiàn)出雙向鏈表的優(yōu)勢(shì)了)，所以在刪除表尾鏈接點(diǎn)時(shí)需要遍歷以找到表尾鏈接點(diǎn)的前一個(gè)鏈接點(diǎn)，需查找N-1次，也就是O(N)
有了這幾個(gè)方法就可以用雙端鏈表來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列了
|
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ù)項(xiàng)只需O(1)，因?yàn)槠涫冀K處于表頭，對(duì)頻繁操作最小數(shù)據(jù)項(xiàng)的應(yīng)用，可以考慮使用有序鏈表實(shí)現(xiàn)，如：優(yōu)先級(jí)隊(duì)列和數(shù)組相比，鏈表的優(yōu)勢(shì)在于長(zhǎng)度不受限制，并且在進(jìn)行插入和刪除操作時(shí)，不需要移動(dòng)數(shù)據(jù)項(xiàng)，故盡管某些操作的時(shí)間復(fù)雜度與數(shù)組想同，實(shí)際效率上還是比數(shù)組要高很多。劣勢(shì)在于隨機(jī)訪問(wèn)，無(wú)法像數(shù)組那樣直接通過(guò)下標(biāo)找到特定的數(shù)據(jù)項(xiàng) 。
以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)之鏈表(動(dòng)力節(jié)點(diǎn)之Java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)服務(wù)器之家網(wǎng)站的支持！
