鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，并且是一種動態(tài)的數據結構。鏈表由節(jié)點（Node）構成。
鏈表的各個節(jié)點在內存上是隨機分布的，因而不能輕易的像數組那樣通過索引獲得數據，但是對于存儲無語義型的數據（如手機號碼，身份證號等），我們優(yōu)先使用鏈表，這樣無需開辟過多的內存空間。
一個節(jié)點由一個Node型的next和一個存儲數據的泛型變量e組成。next指的是下一個節(jié)點所在的位置，而e就是存儲的實際數據了。整個鏈表通過一個個節(jié)點通過next鏈接起來，最后一個節(jié)點的下一個值則為 NULL 。我們將鏈表的頭所在位置用head變量標記。

鏈表簡圖

public class LinkedList<E> {
    private Node head;
    private int size;

    public LinkedList(){
        head=null;
        size=0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void add(int index,E e){//模擬數組添加數據到指定索引節(jié)點
        if (index <0 ||index > size)
            throw new IllegalArgumentException("ADD FAILED.");
        if (index==0){
            head=new Node(e,head.next);
            size++;
        }else{
            Node prev=head;
            for (int i=0;i<index-1;i++){
                prev=prev.next;
            }
            prev.next=new Node(e,prev.next);
            size++;
        }
    }

    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e=e;
            this.next=next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }
}

由于每次添加操作還要對index==head的情況額外進行判斷，我們引入dummyHead（虛擬頭結點）。
所謂虛擬頭節(jié)點，就是在head之前添加一個虛擬的頭節(jié)點，這樣子就無需進行額外判斷。

重新編寫的代碼如下：

增

    public void add(int index,E e){
        if (index <0 ||index > size)
            throw new IllegalArgumentException("ADD FAILED.");
            Node prev=dummyHead;
            for (int i=0;i<index;i++){//由于是從head前一個節(jié)點開始遍歷，我們只需遍歷index次
                prev=prev.next;
            }
            prev.next=new Node(e,prev.next);
            size++;
    }

刪

    public E remove(int index){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("REMOVE FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        Node ret=cur.next;
        cur.next=ret.next //cur.next=cur.next.next;
        ret.next=null;
        size--;
        return ret.e;
    }

改

    public void set(int index,E e){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("SET FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        cur.e= e;
    }

查

    public E get(int index){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("GET FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        return cur.e
    }

    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if (cur.e.equals(e))
                return true;
            cur=cur.next;
        }
        return false;
    }