My Blog List

Tuesday, January 6, 2015

Difference between LinkedList and ArrayList and Performance Test

안녕하세요 저는 쯔앙구입니다.

3년전에 학원에서 처음으로 Java언어를 배우고 안드로이드 어플 개발중 왜 실력이 늘지 않는걸까?? 라는 생각에 자바 자료구조 책을 한권샀습니다.
거기에서는 c언어랑 의사코드랑 같이 섞여있는데 제가 자바만 배웠는데 알겠나요?? 너무 어려워서 Linked에서 포기...
에라 모르겠다. 몰라도 어플동작이 잘만 되자나??
라고 생각했는데 1년뒤에 제가 짠 어플 소스를 다시 보니깐 부끄러울 정도였더군요.
혹시나 저처럼 먹고살기 힘들어서 기초 없이 학원에서 속성과정으로 자바를 시작하는 사람에게 한번더 생각하면서
코딩을 할 수 있도록 도움을 주고자 작성합니다.


ArrayListLinked 리스트의 차이점.

학원에서 무조건 암기하라고 했습니다.
List list = new ArrayList();
그러다 보니 2-3년간 무조건 리스트는 ArrayList를 만들었습니다.

자바에서 대표적으로 사용하는 리스트는 ArrayList와 LinkedList가 있는데
잠깐 살표볼께요.

상황에 따라서 사용을 해야하는데 무조건 ArrayList를 고집해서 사용하게 될 경우 시스템에 어떠한 영향을 끼칠지 알아봅시다.


ArrayList = 말 그대로 new Object[] 배열을 생성해서 배열을 가지고 Insert, delete 하는 방법

LinkedList = Header부분에 왼쪽 노드, 오른쪽 노드의 주소값을 가지고 찾아가는 방법
아래는 코드를 돌린 내용입니다.



 1
 2
 3
 4
 5
 6
 7
 8
 9
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
59
60
61
package mybook;

import java.util.ArrayList;
import java.util.LinkedList;

public class DifferentList {

 public static void main(String[] args) {
  Long start =0l;
  Long end =0l;
  
  start = System.currentTimeMillis();
  
  ArrayList<String> array= new ArrayList<String>();
  for(int i=0; i<10000000; i++){
   array.add("hello");
  }
  logEnd(start, "array Insert");
  
  
  start = System.currentTimeMillis();
  LinkedList<String> linked= new LinkedList<String>();
  for(int i=0; i<10000000; i++){
   linked.add("hello");
  }
  logEnd(start, "Linked Insert");
  
  
  start = System.currentTimeMillis();
  for(int i=0; i< 10000; i++){
   array.remove(i); 
  }
  logEnd(start, "Array RemoveIndex");
  
  
  start = System.currentTimeMillis();
  for(int i=0; i< 10000; i++){
   linked.remove(i); 
  }
  logEnd(start, "Linked RemoveIndex");
  
  start = System.currentTimeMillis();
  for(int i=1000000; i< 10000; i++){
   array.remove(i); 
  }
  logEnd(start, "Array RemoveIndex");
  
  
  start = System.currentTimeMillis();
  for(int i=1000000; i< 10000; i++){
   linked.remove(i); 
  }
  logEnd(start, "Linked RemoveIndex");
 }
 
 public static void logEnd(long start,  String message){
  System.out.println(message + " : " +(System.currentTimeMillis() - start));
 }
 
 
}


== 결과 ==

array Insert : 94
Linked Insert : 1078

Array RemoveIndex : 78462
Linked RemoveIndex : 110

Array RemoveIndex : 0
Linked RemoveIndex : 0


결과를 봐서 add 하는 부분은 LinkedList에 비해 ArrayList 가 10배 정도 빠르고
index값의 데이터를 삭제하는 부분은 데이터가 크면 클수록 ArrayList 가 LinkedList에 비해 속도가 현저히 느렸습니다.

결론 : 무조건 ArrayList를 사용하는것이 아니라 고객의 Needs를 통해서 어떠한 방법으로 구현을 해야할지에 대해서 충분히 고민을 한 후 코딩을 해야한다.

No comments:

Post a Comment