链表的实现：

package com.lt.datastructure.LinkedList;public class LinkedList
     
       {    //虚拟头结点    private Node dummyhead;    private int size;        public 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();        }    }        public LinkedList(){        dummyhead = new Node(null,null);        size = 0;    }    //    返回元素个数    public int getSize(){        return size;    }        //    返回链表是否为空    public boolean isEmpty(){        return size == 0;    }    //    链表添加元素    public void add(int index,E e){        if(index<0 || index >size)            throw new IllegalArgumentException("Add failed");                //目的是找index的前一个位置            Node prev = dummyhead;//dymmyhead.next 则 for(; i
      
       =size){            throw new IllegalArgumentException("Get failes.Illegal index");        }        //目的是从第一个开始        Node cur = dummyhead.next;        for(int i =0; i
       
        size ){            throw new IllegalArgumentException("Set failed. Illeagal index");        }        //目的是找到index位置的元素        Node cur = dummyhead.next;        for(int i=0; i
        
         =size ){            throw new IllegalArgumentException("remove failed. Illeagal index");        }        //找到前一个结点，使其指向删除结点的后一个结点        Node prev = dummyhead;        for(int i=0;i< index ; i++){            prev = prev.next;        }        //找到删除结点        Node retNode = prev.next;        prev.next = retNode.next;        retNode.next = null;        size--;        return retNode.e;    }        //删除第一个元素    public E removeFirst(){        return remove(0);    }        //删除最后一个元素    public E removeLast(){        return remove(size-1);    }        //toString    @Override    public String toString() {                StringBuilder res = new StringBuilder();    //        Node cur = dummyhead.next;//        while(cur!=null){//         res.append(cur+"->");//         cur = cur.next;//        }            //使用for循环实现        for(Node cur= dummyhead.next; cur!=null; cur=cur.next){            res.append(cur+"->");        }        res.append("null");                return res.toString();    }    }
        
       
      
     

测试：

package com.lt.datastructure.LinkedList;public class Main {    public static void main(String[] args) {       LinkedList
     
       linkedList = new LinkedList<>();       for(int i=0 ; i<5 ; i++){           linkedList.addFirst(i);           System.out.println(linkedList);       }       linkedList.add(2, 666);       System.out.println(linkedList);           linkedList.remove(2);       System.out.println(linkedList);//              linkedList.removeFirst();       System.out.println(linkedList);//              linkedList.removeLast();       System.out.println(linkedList);    }               }
     

测试结果：

复杂度分析：

• 增  ：需要遍历找到找到前一个位置   O(n/2)   O(n)
• 删  ：需要遍历，平均为O(n/2)  O(n)
• 改   : 需要遍历，平均为O(n/2)  O(n)
• 查  ：需要遍历，平均为O(n/2)  O(n)

和数组对比：

• 数组有索引的时候，可以快速访问
• 如果只对链表头进行操作，和数组的时间复杂度差不多：O(1)
• 链表是动态的，不会浪费内存空间