java实现双向链表详解编程语言

第一个版本，没有最后一个节点，每次从根节点开始遍历

public class  LinkedList<E> { 
      
    private Node head; 
      
    public LinkedList() { 
    } 
      
    public E getFirst(){ 
        if(head==null){ 
            return null; 
        } 
        return head.value; 
    } 
      
    public LinkedList<E> addFirst(E e){ 
        head.pre=new Node(e, null, head); 
        head=head.pre; 
        return this; 
    } 
      
    public LinkedList<E> addNode(E e){ 
        Node lst=head; 
        if(lst==null){ 
            this.head=new Node(e, null, null); 
            return this; 
        }else{ 
            while(true){ 
                if(lst.next==null){ 
                    break; 
                }else{ 
                    lst=lst.next; 
                } 
            } 
            lst.next=new Node(e, lst, null); 
            return this; 
        } 
    } 
      
    public LinkedList<E> remove(E e){ 
        Node lst=head; 
        if(lst==null){ 
            throw new NullPointerException("the LinkedList is empty."); 
        }else{ 
            while(true){ 
                if(e.equals(lst.value)){ 
                    //移除这个元素 
                    if(lst.pre!=null){ 
                        lst.pre.next=lst.next; 
                    } 
                    if(lst.next!=null){ 
                        lst.next.pre=lst.pre; 
                    } 
                    lst=null; 
                    break; 
                } 
                lst=lst.next; 
            } 
            return this; 
        } 
    } 
      
      
    @Override 
    public String toString() { 
        StringBuffer buff=new StringBuffer("["); 
        Node lst=this.head; 
        while(lst!=null){ 
            buff.append(lst.value+","); 
            lst=lst.next; 
        } 
        return buff.substring(0, buff.length()-1)+"]"; 
    } 
      
    /**节点信息*/ 
    private class Node{ 
        public Node pre; 
        public E value; 
        public Node next; 
          
        public Node(E value,Node pre,Node next) { 
            this.value=value; 
            this.pre=pre; 
            this.next=next; 
        } 
    } 
      
}

第二个版本，有了最后一个节点

public class  LinkedList<E> { 
     
    private Node head; 
    private Node last; 
     
    public LinkedList() { 
    } 
     
    public E getFirst(){ 
        if(head==null){ 
            return null; 
        } 
        return head.value; 
    } 
    public E getLast(){ 
        if(last==null){ 
            return null; 
        } 
        return last.value; 
    } 
     
    public LinkedList<E> addFirst(E e){ 
        head.pre=new Node(e, null, head); 
        head=head.pre; 
        return this; 
    } 
     
    public LinkedList<E> addNode(E e){ 
        Node lst=last; 
        if(lst==null){//如果最后一个节点是空的则这个链表就是空的 
            this.last=new Node(e, null, null); 
            this.head=this.last; 
            return this; 
        }else{ 
            while(true){ 
                if(lst.next==null){// 
                    break; 
                }else{ 
                    lst=lst.next; 
                } 
            } 
            lst.next=new Node(e, lst, null); 
            last=lst.next; 
            return this; 
        } 
    } 
     
    public LinkedList<E> remove(E e){ 
        Node lst=head; 
        if(lst==null){ 
            throw new NullPointerException("the LinkedList is empty."); 
        }else{ 
            while(true){ 
                if(e.equals(lst.value)){ 
                    //移除这个元素 
                    if(lst.pre!=null){ 
                        lst.pre.next=lst.next; 
                    } 
                    if(lst.next!=null){ 
                        lst.next.pre=lst.pre; 
                    } 
                    lst=null; 
                    break; 
                } 
                lst=lst.next; 
            } 
            return this; 
        } 
    } 
     
     
    @Override 
    public String toString() { 
        StringBuffer buff=new StringBuffer("["); 
        Node lst=this.head; 
        while(lst!=null){ 
            buff.append(lst.value+","); 
            lst=lst.next; 
        } 
        return buff.substring(0, buff.length()-1)+"]"; 
    } 
     
    /**节点信息*/ 
    private class Node{ 
        public Node pre; 
        public E value; 
        public Node next; 
         
        public Node(E value,Node pre,Node next) { 
            this.value=value; 
            this.pre=pre; 
            this.next=next; 
        } 
    } 
     
}

注：以上两个版本都没有考虑在多线程下使用的情况。