ArrayList与LinkedList的区别-白红宇

ArrayList与LinkedList的区别

阅读量：4129 次

发布时间：2019-05-25

本文共 2410 字，大约阅读时间需要 8 分钟。

List ADT有两种流行的实现方式。

1.ArrayList类提供了List ADT的一种可增长数组的实现。使用ArrayList的优点在于，对get和set的调用花费常数时间。其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在ArrayList的末端是在ArrayList的末端运行。

2.LinkedList类则提供了List ADT的双链表实现。使用LinkedList的优点在于，新项的插入和现有项的删除均开销很小，这里假设变动项的位置是已知的。

解释下数组类型和双链表的区别

a.数组

b.双链表

import java.util.* ;public class ListDemo01{	public static void main(String args[]){		List
   
     li = new LinkedList
    
     () ;		long startTime = System.currentTimeMillis() ;		for(int i=0;i<1000000;i++){			li.add(0,i) ;               //print : 803			//li.add(i) ;				//print : 790		}		long endTime = System.currentTimeMillis() ;		System.out.println(endTime-startTime) ;	}}

下面的代码得不出结果速度太慢

import java.util.* ;public class ListDemo01{	public static void main(String args[]){		List
   
     li = new LinkedList
    
     () ;		for(int i=0;i<1000000;i++){			li.add(0,i) ;               //print : 803			//li.add(i) ;				//print : 790		}		long startTime = System.currentTimeMillis() ;		for(int i=0;i<1000000;i++){			li.get(i) ;		}		long endTime = System.currentTimeMillis() ;		System.out.println(endTime-startTime) ;	}}

下面化成ArrayList速度就超快

import java.util.* ;public class ListDemo01{	public static void main(String args[]){		List
   
     li = new ArrayList
    
     () ;		for(int i=0;i<1000000;i++){			li.add(i) ;						}		long startTime = System.currentTimeMillis() ;		for(int i=0;i<1000000;i++){			li.get(i) ;      //print : 15        		}		long endTime = System.currentTimeMillis() ;		System.out.println(endTime-startTime) ;	}}

remove方法对LinkedList类的使用

a.利用iterator类

import java.util.* ;public class ListDemo01{	public static void main(String args[]){		List
   
     li = new LinkedList
    
     () ;		for(int i=0;i<1000000;i++){			li.add(i) ;						}		long startTime = System.currentTimeMillis() ;		Iterator
     
       it = li.iterator() ;		while(it.hasNext()){			if(it.next()%2==0){				it.remove() ;			}		}		long endTime = System.currentTimeMillis() ;		System.out.println(endTime-startTime) ;	}}

b.不利用iterator的话则则需要调用get方法。则效率很低

import java.util.* ;public class ListDemo01{	public static void main(String args[]){		List
   
     li = new LinkedList
    
     () ;		for(int i=0;i<1000000;i++){			li.add(i) ;						}		long startTime = System.currentTimeMillis() ;		for(int i=0;i<10000;i++){			if(li.get(i)%2==0){				li.remove(i)  ;			}		}		long endTime = System.currentTimeMillis() ;		System.out.println(endTime-startTime) ;	}}

转载地址：http://whwvi.baihongyu.com/

你可能感兴趣的文章