深入理解ArrayList与LinkedList的区别

深入理解ArrayList与LinkedList的区别

一、ArrayList与LinkedList在JDK中所在位置
ArrayList与LinkedList 在JDK中所在的位置,如下图所示:

从图中可以看出,ArrayList与LinkedList都是List接口的实现类,因此都实现了List的所有未实现的方法,只是实现的方式有所不同,(编程思想: 从中可以看出面向接口的好处, 对于不同的需求就有不同的实现!),而List接口继承了Collection接口,Collection接口又继承了Iterable接口,因此可以看出List同时拥有了Collection与Iterable接口的特性.
二、认识和理解ArrayList
ArrayList实现了List接口,它是以数组的方式来实现的,数组的特性是可以使用索引的方式来快速定位对象的位置,因此对于快速的随机取得对象的需求,使用ArrayList实现执行效率上会比较好.
ArrayListDemo:
Java代码
[Java] 纯文本查看 复制代码
?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class ArrayListDemo {

public static void main(String[] args) {  
       
    List<String> userlist = new ArrayList<String>();  
    userlist.add("yulon");  
    userlist.add("xiaoyun");  
    userlist.add("羽龙共舞");  
    System.out.println("使用普通for循环:");  
    for(int i=0; i<userlist.size(); i++){  
        System.out.print(userlist.get(i)+" ");  
    }  
    System.out.println();  
    System.out.println();  
    System.out.println("使用Iterator迭代器:");  
    Iterator it = userlist.iterator();  
    while(it.hasNext()){  
        System.out.print(it.next()+" ");  
    }  
    System.out.println();  
    System.out.println();  
    System.out.println("使用增强for循环:");  
       
    for(String s : userlist){  
        System.out.print(s+" ");  
    }  
}  

}

这里列举出了循环List列表的三种方式: 使用普通for循环,用get方法获取; 使用Iterator迭代器,使用next方法遍历;使用增强for循环,直接输出! 由此可见第三种方法是最方便,最简洁的!
三、认识和理解LinkedList
LinkedList是采用链表的方式来实现List接口的,它本身有自己特定的方法,如: addFirst(),addLast(),getFirst(),removeFirst()等. 由于是采用链表实现的,因此在进行insert和remove动作时在效率上要比ArrayList要好得多!适合用来实现Stack(堆栈)与Queue(队列),前者先进后出,后者是先进先出。
1、堆栈
Java代码

[Java] 纯文本查看 复制代码
?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class StringStack {

private LinkedList<String> linkedList   
= new LinkedList<String>();  

/** 
 * 将元素加入LinkedList容器 
 * (即插入到链表的第一个位置) 
 */ 
public void push(String name){  
    linkedList.addFirst(name);  
}  
/** 
 * 取出堆栈中最上面的元素 
 * (即取出链表linkedList的第一个元素) 
 * @return 
 */ 
public String getTop(){  
    return linkedList.getFirst();  
}  
/** 
 * 取出并删除最上面的元素 
 * (即移出linkedList的第一个元素) 
 * @return 
 */ 
public String pop(){  
    return linkedList.removeFirst();  
}  
/** 
 * 获取元素个数 
 * @return 
 */ 
public int size(){  
    return linkedList.size();  
}  
   
/** 
 * 判断堆栈是否为空 
 * (即判断 linkedList是否为空) 
 * @return 
 */ 
public boolean isEmpty(){  
    return linkedList.isEmpty();  
}  
//测试  
public static void main(String[] args) {  
    StringStack stack = new StringStack();  
    stack.push("yulon");  
    stack.push("xiaoyun");  
    stack.push("羽龙共舞");  
    System.out.print("第一个元素是:\t");  
    System.out.println(stack.getTop());  
    System.out.println();  
    System.out.println("全部元素:");  
    while(!stack.isEmpty()){  
        System.out.println("\t"+stack.pop());  
    }  
}  

}

输出结果是:
Xml代码
第一个元素是: 羽龙共舞

全部元素:

羽龙共舞  
xiaoyun  
yulon  

知识提示: LinkedList的特有方法(本身定义的方法)如:addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等
2、实现队列类似
3、如果要使用队列的功能,由于LinkedList也实现了java.util.Queue接口,所以可以直接使用LinkedList的实例来实现.
Java代码

[Java] 纯文本查看 复制代码
?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
public class QueueDemo {

public static void main(String[] args) {  
    //父类引用queue指向子类对象  
    Queue<String> queue = new LinkedList<String>();  
    //offer()方法是往队列加入元素  
    queue.offer("xiaoyun");  
    queue.offer("yulon");  
    queue.offer("羽龙共舞");  
    String element = null;  
    while((element=queue.poll())!=null){  
        System.out.println(element+"\t");  
    }  
}  

}

输出顺序是:
Xml代码
xiaoyun
yulon
羽龙共舞
四、在删除可插入对象的动作时,为什么ArrayList的效率会比较低呢?
解析: 因为ArrayList是使用数组实现的,若要从数组中删除或插入某一个对象,需要移动后段的数组元素,从而会重新调整索引顺序,调整索引顺序会消耗一定的时间,所以速度上就会比LinkedList要慢许多. 相反,LinkedList是使用链表实现的,若要从链表中删除或插入某一个对象,只需要改变前后对象的引用即可!

评论

暂无评论