线性链表--哨兵节点

   哨兵（sentinel）是一个哑对象，可以简化边界条件。是一个附加的链表节点，该节点作为第一个节点，但是它其实并不存储任何东西，只是为了操作的方便而引入的。因此，如果一个链表有哨兵节点的话，那么线性表的第一个元素应该是链表的第二个节点（个位置的时候，需要考虑该位置上原来的节点并没有前驱节点；而如果有哨兵节点的话， 线性表的每个位置的节点都有前驱节点，因此可以统一处理。（注意：哨兵节点根本不出现在线性表中，所以虽然它没有前驱，但是前面的那句话并不矛盾）。


              带哨兵节点的双链表     

1. package com.eshore.sweetop.dataframe;
2. 
   
3. public class DoubleLinkedList {
4.     private Element nil;
5.     
6.     public DoubleLinkedList() {
7.         nil=new Element(null);
8.         nil.pre=nil;
9.         nil.next=nil;
10.     }
11.     
12.     public void insert(Object o){
13.         Element e=new Element(o);
14.         e.next=nil.next;
15.         nil.next.pre=e;
16.         nil.next=e;
17.         e.pre=nil;
18.     }
19.     
20.     public Element search(Object o){
21.         Element e=nil.next;
22.         while(e!=nil&&e.key!=o){
23.             e=nil.next;
24.         }
25.         return e;
26.     }
27.     
28.     public void delete(Object o){
29.         Element e=search(o);
30.         e.pre.next=e.next;
31.         e.next.pre=e.pre;
32.     }
33.     
34.     public class Element{
35.         private Element pre;
36.         private Element next;
37.         public Object key;
38.         
39.         public Element(Object x){
40.             this.key=x;
41.         }
42.     }
43.     
44.     public static void main(String[] args) {
45.         DoubleLinkedList dll=new DoubleLinkedList();
46.         dll.insert(Integer.valueOf(1));
47.         System.out.println(dll.search(Integer.valueOf(1)).key);
48.         dll.delete(Integer.valueOf(1));
49.     }
50. }