[기술 면접] ArrayList와 LinkedList의 차이

ArrayList vs LinkedList

위 사진을 보면 알 수 있듯 ArrayList는 index가 있고, LinkedList는 각 원소마다 앞,뒤 원소의 위치를 가지고 있다.

이러한 각각의 특징은 조회, 삽입, 삭제 시에 성능의 차이를 발생시킨다.

ArrayList

ArrayList는 기본적으로 배열을 사용한다. 하지만 배열과 차이점이 존재한다.
일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만, ArrayList는 크기를 지정하지 않고, 동적으로 값을 삽입하고 삭제할 수 있다.

조회

ArrayList는 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에 해당 index의 데이터를 한번에 가져올 수 있다.

데이터 삽입과 삭제

데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다.
예를 들어 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 4개를 앞으로 한 칸씩 이동해야 한다.
삽입과 삭제가 많다면 ArrayList는 비효율적이다.

LinkedList

LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회 가능 (배열의 단점을 보완하기 위해 LinkedList가 고안되었다.)

조회

LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.

데이터 삽입과 삭제

LinkedList는 데이터를 추가-삭제 시 가리키고 있는 주소값만 수정해주면 도기ㅣ 때문에 ArrayList에 비해 상당히 효율적이다.
예를 들어 두 번째 값을 삭제하면 첫 번째 노드가 세 번째 노드를 가리키게 하기만 하면 된다.

이처럼 조회 시에는 ArrayList가 우위에 있지만, 삽입 / 삭제 시에는 LinkedList가 뛰어난 성능을 보여준다.

소량의 데이터를 가지고 사용할 때는 사실 큰 차이가 없지만, 정적인 데이터를 활용하면서 조회가 빈번하다면 ArrayList를 사용하는 것이 좋고, 동적으로 추가 / 삭제 요구사항이 빈번하다면 LinkedList를 사용하는 것이 좋다.

ArrayList와 LinkedList의 성능 차이 비교

package study.dataStructure;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        ArrayList ary = new ArrayList(2000000);
        LinkedList lkd = new LinkedList();
 
        System.out.println("======순차적으로 추가하기======");
        System.out.println("ArrayList = " + addF(ary));
        System.out.println("LinkedList = " + addF(lkd));
 
        System.out.println("\n======중간에 추가하기======");
        System.out.println("ArrayList = " + addM(ary));
        System.out.println("LinkedList = " + addM(lkd));
 
        System.out.println("\n======중간에 삭제하기======");
        System.out.println("ArrayList = " + removeM(ary));
        System.out.println("LinkedList = " + removeM(lkd));
 
        System.out.println("\n======순차적으로 삭제하기======");
        System.out.println("ArrayList = " + removeF(ary));
        System.out.println("LinkedList = " + removeF(lkd));
 
    }
 
    public static long addF(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1000000; i++) {
            list.add(i+"");
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
 
    public static long addM(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) {
            list.add(500,"X");
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
 
    public static long removeF(List list) {
        long start = System.currentTimeMillis();
        for(int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
 
    public static long removeM(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
}

실행 결과

======순차적으로 추가하기======
ArrayList = 92
LinkedList = 145
 
======중간에 추가하기======
ArrayList = 3142
LinkedList = 11
 
======중간에 삭제하기======
ArrayList = 1746
LinkedList = 116
 
======순차적으로 삭제하기======
ArrayList = 8
LinkedList = 19
 
Process finished with exit code 0

결론

1. 순차적으로 추가 / 삭제하는 경우 ArrayList가 LinkedList보다 빠르다.

큰 차이는 없지만, 처음 또는 마지막 데이터부터 순차적으로 데이터를 쭉 삭제하면 각 요소들의 재배치가 필요하지 않기 때문에 ArrayList도 빠르다.

2. 중간 데이터(비 순차적)를 추가 / 삭제하는 경우 LinkedList가 ArrayList보다 빠르다.

중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 노드간 연결만 변경해주면 되기 때문에 처리 속도가 빠르다.
반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하기 때문에 처리속도가 늦다.