[List] ArrayList 와 LinkedList

#1. ArrayList

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

• 데이터 추가 : 기존 배열 크기 + 1을 가지는 임시배열을 하나 만들고, 추가할 위치의 인덱스를 제외한 위치에 각 데이터를 전체 복제한다. 그리고 난 후, 신규 데이터를 추가한다.
• 데이터 접근 : 인덱스를 이용하여 바로 접근한다.

데이터 추가/삭제 과정에서 데이터 Shift작업이 일어나기 때문에 LinkedList에 비해 추가 연산이 필요하다.

하지만, 인덱스를 이용하여 무작위접근(random access)가 가능하다.

ArrayList에서 데이터 추가

 

#2. LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

• 데이터 추가 : 연결된 노드의 앞/뒤 주소값를 바꿔주는 것으로 추가한다.
• 데이터 접근 : 순차 접근만 가능하다.(HEAD 노드나 TAIL 노드에서 부터 순차 탐색)

배열을 기반으로 하지 않고 연결된 노드의 개념을 이용해서 데이터를 관리한다.

이중연결리스트 기준으로 각 노드는 앞과 뒤 노드의 주소값으로 연결되어 있기 때문에

데이터 추가/삭제시에 앞/뒤 노드의 주소값만 변경하면 된다. ArrayList에 비해 상대적으로 속도가 빠르다.

하지만, 순차접근(sequential access) 만 가능하므로 자료 검색에는 효율성이 좋지 않다.

LinkedList에서 데이터 추가

 

#3. ArrayList vs. LinkedList add/get 속도 비교

public class ListTest {

    public static void main(String[] args) {

        for(int k = 0; k < 5; k++) {

            List<String> ar = new ArrayList<String>();
            List<String> li = new LinkedList<String>();

            // Add 속도 비교
            long arAddStartNano = System.nanoTime();
            for (int i = 0; i < 100000; i++) {
                ar.add("Data".concat(String.valueOf(i)));
            }
            long arAddEndNano = System.nanoTime();
            System.out.println("ArrayList Add Time = " + (arAddEndNano - arAddStartNano));

            long liAddStartNano = System.nanoTime();
            for (int i = 0; i < 100000; i++) {
                li.add("Data".concat(String.valueOf(i)));
            }
            long liAddEndNano = System.nanoTime();
            System.out.println("LinkedList Add Time = " + (liAddEndNano - liAddStartNano));

            // Get 속도 비교
            long arGetStartNano = System.nanoTime();
            ar.get(50000);
            long arGetEndNano = System.nanoTime();
            System.out.println("ArrayList Get Time = " + (arGetEndNano - arGetStartNano));

            long liGetStartNano = System.nanoTime();
            li.get(50000);
            long liGetEndNano = System.nanoTime();
            System.out.println("LinkedList Get Time = " + (liGetEndNano - liGetStartNano));
        }
    }
}

add / get 을 각 5회 수행해본 결과

ArrayList Add Time = 27894400
LinkedList Add Time = 19893100
ArrayList Get Time = 7400
LinkedList Get Time = 996600
ArrayList Add Time = 6052200
LinkedList Add Time = 26558200
ArrayList Get Time = 15200
LinkedList Get Time = 1365100
ArrayList Add Time = 6855900
LinkedList Add Time = 24400000
ArrayList Get Time = 4200
LinkedList Get Time = 2408700
ArrayList Add Time = 5503600
LinkedList Add Time = 29252800
ArrayList Get Time = 2900
LinkedList Get Time = 1302400
ArrayList Add Time = 10415400
LinkedList Add Time = 17901200
ArrayList Get Time = 177200
LinkedList Get Time = 1675500

 

	Add		Get
	ArrayList	LinkedList	ArrayList	LinkedList
1회	27894400	19893100	7400	996600
2회	6052200	26558200	15200	1365100
3회	6855900	24400000	4200	2408700
4회	5503600	29252800	2900	1302400
5회	10415400	17901200	177200	1675500
평균	11344300	23601060	41380	1549660

5회 테스트에서는 add로 가장 뒤에 데이터를 추가했기 때문에 add도 ArrayList가 더 빠른것 처럼 보여진다.

만약 데이터를 중간에 끼워넣는 시도를 했다면 Add에서 LinkedList가 더 빠르지 않겠나... 하는 추측이지만

 

결론 : 특수한 상황이 아니고서는 왠만하면 ArrayList를 사용하자.