[Data Structure] ArrayList, LinkedList, Vector

[List]

순서가 있는 데이터의 집합, 데이터 중복을 허용

List Interface 를 구현하는 ArrayList, LinkedList, Vector 는 모두 위 성질을 따름

 

[사용법]

ArrayList, LinkedList, Vector 모두 사용법이 동일하다.

List<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(2);    //중복허용, 순서보장
//al.remove(0);
 
System.out.print("ArrayList: ");
for(int i:al) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(2);    //중복허용, 순서보장
//ll.remove(0);
 
System.out.print("LinkedList: ");
for(int i:ll) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> v = new Vector<>();
v.add(1);
v.add(2);
v.add(2);    //중복허용, 순서보장
//v.remove(0);
 
System.out.print("Vector: ");
for(int i:v) {
    System.out.print(i+" ");
}

[실행 결과]

ArrayList: 1 2 2
LinkedList: 1 2 2
Vector: 1 2 2

 

[차이점]

ArrayList

배열과 동일하나 저장되는 자료크기에 따라 내부적으로 배열의 크기가 늘었다 줄었다 하는 resizable array.

조회 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 증가시킨다(한 칸씩 민다)

데이터 삭제가 발생하면 삭제된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 감소시킨다(한 칸씩 당긴다).

 

LinkedList

자료의 주소값을 기준으로 데이터들이 연결된 형태.

삽입과 삭제의 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입될 데이터 앞의 데이터는 삽입될 데이터의 주소값을,

삽입될 데이터는 삽입될 데이터 뒤에 위치한 데이터의 주소값을 참조하게 한다.

 

Vector

Thread Safe 한 ArrayList (Synchronized)

 

[ArrayList vs LinkedList 성능 비교]

private static long START_TIME = 0;
    private static long END_TIME = 0;
    
    public static void main(String[] args) {
        
        List<Integer> ArrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.add(0);
        }
        setEndTime();
        System.out.print("ArrayList add: ");
        printDuration();
 
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.add(0);
        }
        setEndTime();
        System.out.print("LinkedList add: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.get(i);
        }
        setEndTime();
        System.out.print("ArrayList get: ");
        printDuration();
        
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.get(i);
        }
        setEndTime();
        System.out.print("LinkedList get: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        Iterator<Integer> ai = ArrayList.iterator();
        while(ai.hasNext()) {
            ArrayList.remove(0);
        }
        setEndTime();
        System.out.print("ArrayList remove: ");
        printDuration();
        
        
        setStartTime();
        Iterator<Integer> li = linkedList.iterator();
        while(li.hasNext()) {
            linkedList.remove(0);
        }
        setEndTime();
        System.out.print("LinkedList remove: ");
        printDuration();
        
    }
    
    private static void setStartTime() {
        START_TIME = System.nanoTime();
    }
    
    private static void setEndTime() {
        END_TIME = System.nanoTime();
    }
    
    private static void printDuration() {
        System.out.println(END_TIME - START_TIME);
    }

[실행 결과]

ArrayList add: 1049700
LinkedList add: 1224800
-------------------------------------------------
ArrayList get: 861200
LinkedList get: 42666800
-------------------------------------------------
ArrayList remove: 6322100
LinkedList remove: 1229300

 

조회(get)는 ArrayList가 상대적으로 뛰어난 성능을 보여준다.

삽입(add)/삭제(remove)는 LinkedList가 상대적으로 뛰어난 성능을 보여준다.

[ArrayList vs LinkedList 시간복잡도]

	ArrayList	LinkedList
Indexing	Θ(1)	Θ(n)
Insert/delete at beginning	Θ(n)	Θ(1)
Insert/delete at end	Θ(1)	Θ(n)-last element is unknown Θ(1)-last element is known
Insert/delete in middle	Θ(n)	search time + Θ(1)
Wasted space (average)	Θ(n)	Θ(n)

 

 

참고 :

https://dzone.com/articles/arraylist-vs-linkedlist-vs

http://www.nextree.co.kr/p6506/