Java LinkedList 与 ArrayList 效率比较

蔚落 2023-02-17 03:19 29阅读 0赞

**时间测试：**

public class test2SpendTime { 
    
        public static void main(String[] args) { 
            int len = 1000000;   //100000 十万元素以内，array 比 link慢（正常）, 但 1000000 一百万元素后，array 比 link 快
            int insertLen = 100;
            int getLen = 10000;
            int setLen = 10000;
            int removeLen = 100;
    
            List<Circle> arrList =  testArrListAdd(len);     //初始填充两个容器
            List<Circle> linkList =  testLinkListAdd(len);
    
            testArrListInsert(arrList, insertLen);
            testLinkListInsert(linkList, insertLen);
    
            testArrListGet(arrList,getLen);
            testLinkListGet(linkList,getLen);
    
            testArrListSet(arrList,setLen );
            testLinkListSet(linkList, setLen);
    
            testArrListRm(arrList,removeLen);
            testLinkListRm(linkList, removeLen);
    
            System.out.println(arrList.size());
            System.out.println(linkList.size());
    
        }
    
        static List<Circle> testArrListAdd(int len){ 
            long startTime  = System.currentTimeMillis();
            List<Circle> arrayList = new ArrayList<>();
            for (int i = 0; i < len; i++){ 
                arrayList.add(new Circle(i));
            }
            long endTime = System.currentTimeMillis();
            System.out.printf(String.format("ArrayList Add %d element spend: %dms", len,(endTime-startTime)));
            return  arrayList;
        }
    
        static  void testArrListInsert(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.add(i, new Circle(i));
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("ArrayList Insert %d element spend: %dms", len, (endTime-startTime)));
        }
    
        static  void testArrListGet(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.get(i);
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("ArrayList get %d element spend: %dms", len, (endTime-startTime)));
        }
        static  void testArrListSet(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.set(i,new Circle(i));
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("ArrayList Set %d element spend: %dms", len, (endTime-startTime)));
        }
        static  void testArrListRm(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.remove(i);
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("ArrayList Remove %d element spend: %dms", len, (endTime-startTime)));
        }
        static  List<Circle> testLinkListAdd(int len){ 
            long startTime  = System.currentTimeMillis();
            List<Circle> linkList = new LinkedList<>();
            for (int i = 0; i < len; i++){ 
                linkList.add(new Circle(i));
            }
            long endTime = System.currentTimeMillis();
             System.out.println(String.format("LinkList Add %d element spend: %dms", len, (endTime-startTime)));
            return  linkList;
        }
        static void testLinkListInsert(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.add(i, new Circle(i));
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("LinkList Insert %d element spend: %dms", len, (endTime-startTime)));
        }
        static void testLinkListGet(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.get(i);
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("LinkList Get %d element spend: %dms", len, (endTime-startTime)));
        }
    
        static void testLinkListSet(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.set(i, new Circle(i));
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("LinkList Set %d element spend: %dms", len, (endTime-startTime)));
        }
    
        static void testLinkListRm(List<Circle> list,  int len){ 
            long startTime  = System.currentTimeMillis();
            for (int i = 0; i < len; i++){ 
                list.remove(i);
            }
            long endTime = System.currentTimeMillis();
            System.out.println(String.format("LinkList Remove %d element spend: %dms", len, (endTime-startTime)));
        }
    
    
    }

**输出：**

ArrayList Add 10000000 element spend: 1240ms
    LinkList Add 10000000 element spend: 4704ms
    ArrayList Insert 100 element spend: 4962ms
    LinkList Insert 100 element spend: 0ms
    ArrayList get 10000 element spend: 2ms
    LinkList Get 10000 element spend: 168ms
    ArrayList Set 10000 element spend: 2ms
    LinkList Set 10000 element spend: 161ms
    ArrayList Remove 100 element spend: 2808ms
    LinkList Remove 100 element spend: 0ms
    10000000
    10000000

**Circle类：**

public class Circle extends Shape implements zqExperiment5.Shape, Comparable{ 
        private double radius;
    
        public double getRadius() { 
            return radius;
        }
    
        public void setRadius(double radius) { 
            this.radius = radius;
        }
    
        public  Circle(){ 
            this(1.0);
        }
        public Circle(double radius){ 
           setRadius(radius);
        }
        @Override
        public double getArea() { 
            return Math.PI * Math.pow(getRadius(),2);
        }
    
        @Override
        public void getDescribe() { 
            System.out.println(String.format("Circle radius: %f, area: %f", getRadius(), getArea()));
        }
    
        @Override
        public String toString() { 
            return "Circle{" +
                    " radius = " + radius +
                    " area = " + getArea() +
                    '}';
        }
    
    
        @Override
        public int compareTo(Object o) {    // A 比 B
            return this.getArea() < ((Circle) o).getArea()? -1 : 1;
        }
    
        @Override
        public boolean equals(Object o) { 
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Circle circle = (Circle) o;
            return Double.compare(circle.radius, radius) == 0;
        }
    
        @Override
        public int hashCode() { 
            return Objects.hash(radius + getArea());
        }
    }