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;
        }
    }
    
}

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

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。