Java单链表、双端链表、有序链表实现原理

单链表：

insertFirst：在表头插入一个新的链接点，时间复杂度为O(1)

deleteFirst：删除表头的链接点，时间复杂度为O(1)

有了这两个方法，就可以用单链表来实现一个栈了，见http://blog.csdn.net/a19881029/article/details/22579759

find：查找包含指定关键字的链接点，由于需要遍历查找，平均需要查找N/2次，即O(N)

remove：删除包含指定关键字的链接点，由于需要遍历查找，平均需要查找N/2次，即O(N)

[java] view plain copy

1. public class LinkedList {  
2.     private class Data{  
3.         private Object obj;  
4.         private Data next = null;  
5.           
6.         Data(Object obj){  
7.             this.obj = obj;  
8.         }  
9.     }  
10.       
11.     private Data first = null;  
12.       
13.     public void insertFirst(Object obj){  
14.         Data data = new Data(obj);  
15.         data.next = first;  
16.         first = data;  
17.     }  
18.       
19.     public Object deleteFirst() throws Exception{  
20.         if(first == null)  
21.             throw new Exception("empty!");  
22.         Data temp = first;  
23.         first = first.next;  
24.         return temp.obj;  
25.     }  
26.       
27.     public Object find(Object obj) throws Exception{  
28.         if(first == null)  
29.             throw new Exception("LinkedList is empty!");  
30.         Data cur = first;  
31.         while(cur != null){  
32.             if(cur.obj.equals(obj)){  
33.                 return cur.obj;  
34.             }  
35.             cur = cur.next;  
36.         }  
37.         return null;  
38.     }  
39.       
40.     public void remove(Object obj) throws Exception{  
41.         if(first == null)  
42.             throw new Exception("LinkedList is empty!");  
43.         if(first.obj.equals(obj)){  
44.             first = first.next;  
45.         }else{  
46.             Data pre = first;  
47.             Data cur = first.next;  
48.             while(cur != null){  
49.                 if(cur.obj.equals(obj)){  
50.                     pre.next = cur.next;  
51.                 }  
52.                 pre = cur;  
53.                 cur = cur.next;  
54.             }  
55.         }  
56.     }  
57.       
58.     public boolean isEmpty(){  
59.         return (first == null);  
60.     }  
61.       
62.     public void display(){  
63.         if(first == null)  
64.             System.out.println("empty");  
65.         Data cur = first;  
66.         while(cur != null){  
67.             System.out.print(cur.obj.toString() + " -> ");  
68.             cur = cur.next;  
69.         }  
70.         System.out.print("\n");  
71.     }  
72.       
73.     public static void main(String[] args) throws Exception {  
74.         LinkedList ll = new LinkedList();  
75.         ll.insertFirst(4);  
76.         ll.insertFirst(3);  
77.         ll.insertFirst(2);  
78.         ll.insertFirst(1);  
79.         ll.display();  
80.         ll.deleteFirst();  
81.         ll.display();  
82.         ll.remove(3);  
83.         ll.display();  
84.         System.out.println(ll.find(1));  
85.         System.out.println(ll.find(4));  
86.     }  
87. }  

[plain] view plain copy

1. 1 -> 2 -> 3 -> 4 ->   
2. 2 -> 3 -> 4 ->   
3. 2 -> 4 ->   
4. null  
5. 4  

双端链表(不是双向链表)：

与单向链表的不同之处在保存有对最后一个链接点的引用(last)

insertFirst：在表头插入一个新的链接点，时间复杂度O(1)

insertLast：在表尾插入一个新的链接点，时间复杂度O(1)

deleteFirst：删除表头的链接点，时间复杂度O(1)

deleteLast:：删除表尾的链接点，由于只保存了表尾的链接点，而没有保存表尾的前一个链接点(这里就体现出双向链表的优势了)，所以在删除表尾链接点时需要遍历以找到表尾链接点的前一个链接点，需查找N-1次，也就是O(N)

有了这几个方法就可以用双端链表来实现一个队列了，http://blog.csdn.net/a19881029/article/details/22654121

[java] view plain copy

1. public class FirstLastList {  
2.     private class Data{  
3.         private Object obj;  
4.         private Data next = null;  
5.           
6.         Data(Object obj){  
7.             this.obj = obj;  
8.         }  
9.     }  
10.       
11.     private Data first = null;  
12.     private Data last = null;  
13.       
14.     public void insertFirst(Object obj){  
15.         Data data = new Data(obj);  
16.         if(first == null)  
17.             last = data;  
18.         data.next = first;  
19.         first = data;  
20.     }  
21.       
22.     public void insertLast(Object obj){  
23.         Data data = new Data(obj);  
24.         if(first == null){  
25.             first = data;  
26.         }else{  
27.             last.next = data;  
28.   
29.         }  
30.         last = data;  
31.     }  
32.       
33.     public Object deleteFirst() throws Exception{  
34.           if(first == null)  
35.              throw new Exception("empty");  
36.           Data temp = first;  
37.           if(first.next == null)  
38.              last = null;  
39.           first = first.next;  
40.           return temp.obj;  
41.    }     
42.       
43.     public void deleteLast() throws Exception{  
44.         if(first == null)  
45.             throw new Exception("empty");  
46.         if(first.next == null){  
47.             first = null;  
48.             last = null;  
49.         }else{  
50.             Data temp = first;  
51.             while(temp.next != null){  
52.                 if(temp.next == last){  
53.                     last = temp;  
54.                     last.next = null;  
55.                     break;  
56.                 }  
57.                 temp = temp.next;  
58.             }  
59.         }  
60.     }  
61.       
62.     public void display(){  
63.         if(first == null)  
64.             System.out.println("empty");  
65.         Data cur = first;  
66.         while(cur != null){  
67.             System.out.print(cur.obj.toString() + " -> ");  
68.             cur = cur.next;  
69.         }  
70.         System.out.print("\n");  
71.     }  
72.       
73.     public static void main(String[] args) throws Exception {  
74.         FirstLastList fll = new FirstLastList();  
75.         fll.insertFirst(2);  
76.         fll.insertFirst(1);  
77.         fll.display();  
78.         fll.insertLast(3);  
79.         fll.display();  
80.         fll.deleteFirst();  
81.         fll.display();  
82.         fll.deleteLast();  
83.         fll.display();  
84.     }  
85. }  

[plain] view plain copy

1. 1 -> 2 ->   
2. 1 -> 2 -> 3 ->   
3. 2 -> 3 ->   
4. 2 ->   

有序链表：链表中的数据按从小到大排列

[java] view plain copy

1. public class SortedList {  
2.     private class Data{  
3.         private Object obj;  
4.         private Data next = null;  
5.           
6.         Data(Object obj){  
7.             this.obj = obj;  
8.         }  
9.     }  
10.   
11.     private Data first = null;  
12.       
13.     public void insert(Object obj){  
14.         Data data = new Data(obj);  
15.         Data pre = null;  
16.         Data cur = first;  
17.         while(cur != null && (Integer.valueOf(data.obj.toString())  
18.                 .intValue() > Integer.valueOf(cur.obj.toString())  
19.                 .intValue())){  
20.             pre = cur;  
21.             cur = cur.next;  
22.         }  
23.         if(pre == null)  
24.             first = data;  
25.         else  
26.             pre.next = data;  
27.         data.next = cur;  
28.     }  
29.       
30.     public Object deleteFirst() throws Exception{  
31.         if(first == null)  
32.             throw new Exception("empty!");  
33.         Data temp = first;  
34.         first = first.next;  
35.         return temp.obj;  
36.     }  
37.       
38.     public void display(){  
39.         if(first == null)  
40.             System.out.println("empty");  
41.         System.out.print("first -> last : ");  
42.         Data cur = first;  
43.         while(cur != null){  
44.             System.out.print(cur.obj.toString() + " -> ");  
45.             cur = cur.next;  
46.         }  
47.         System.out.print("\n");  
48.     }  
49.       
50.     public static void main(String[] args) throws Exception{  
51.         SortedList sl = new SortedList();  
52.         sl.insert(80);  
53.         sl.insert(2);  
54.         sl.insert(100);  
55.         sl.display();  
56.         System.out.println(sl.deleteFirst());  
57.         sl.insert(33);  
58.         sl.display();  
59.         sl.insert(99);  
60.         sl.display();  
61.     }  
62. }  

[plain] view plain copy

1. first -> last : 2 -> 80 -> 100 ->   
2. 2  
3. first -> last : 33 -> 80 -> 100 ->   
4. first -> last : 33 -> 80 -> 99 -> 100 ->   

表的插入和删除平均需要比较N/2次，即O(N)，但是获取最小数据项只需O(1)，因为其始终处于表头，对频繁操作最小数据项的应用，可以考虑使用有序链表实现，如：优先级队列

 

和数组相比，链表的优势在于长度不受限制，并且在进行插入和删除操作时，不需要移动数据项，故尽管某些操作的时间复杂度与数组想同，实际效率上还是比数组要高很多

劣势在于随机访问，无法像数组那样直接通过下标找到特定的数据项