🧱 ArrayList vs LinkedList 특징 & 성능 비교

LinkedList vs ArrayList 특징 비교

LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성한 이유는 ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.

	ArrayList	LinkedList
컬렉션 구성	배열을 이용	노드를 연결 (linked)
데이터 접근 시간	모든 데이터 상수 시간 접근	위치에 따라 이동시간 발생
삽입 / 삭제 시간	삽입/삭제 자체는 상수 시간
	삽입/삭제 시 데이터 이동이 필요한 경우 추가시간 발생	삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요	공간이 부족할경우 새로운 배열에 복사하는 추가 시간 발생	-
데이터 검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인
CPU Cache	캐시 이점을 활용	-

 

ArrayList의 문제점

ArrayList는 배열 공간(capacity)가 꽉 차거나, 요소 중간에 삽입을 행하려 할때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.

이러한 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 리사이징 처리에서 시간이 소모된다.

 

LinkedList의 장단점

반면, LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다. 따라서 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다

 

하지만 LinkedList 에도 만능이 아니며 단점이 존재한다.

요소를 get 하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능하기 때문이다.

예를 들어 n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다.

이를 그림으로 표현하자면, 아래 빌딩 그림을 메모리(RAM)으로 비유하고 각기 방을 데이터라고 비유하자면, ArrayList는 연속적인 묶음으로 되어있지만, LinkedList는 각기 다른 방에 저장되어있고 링크로 연결되어 있음을 볼 수 있다.

그래서 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어 ArrayList보다 당연히 긴 지연 시간이 소모되게 된다. 특히 Singly Linked List는 단방향성만 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않는다.

LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점 이다. 배열 같은 경우 그냥 데이터 그대로만 저장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에 next 나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요 할 수 밖에 없다.

LinkedList 장점	LinkedList 단점
자료의 삽입과 삭제가 용이	포인터의 사용으로 인해 저장 공간의 낭비
리스트 내에서 자료의 이동이 불필요	알고리즘이 복잡
사용 후 기억 장소의 재사용이 가능	특정 자료의 탐색 시간이 많이 소요
연속적인 기억 장소의 할당이 불필요

---

LinkedList vs ArrayList 성능 비교

 

시간 복잡도 비교

LinkedList를 처음 배우는 새내기들이 착각하는 것이, 요소를 추가하는 것과 요소를 삭제하는 것의 시간복잡도가 오로지 O(1) 이라는 점이다. 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 시간복잡도는 O(1)이 맞지만, 중간에 요소를 추가 / 삭제 한다면 그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.

그래도 탐색 시간(search time)에 시간이 그리 소요되지않으면 ArrayList보다 삽입 속도가 빠르기 때문에 표기만 저렇지 왠만한 상황에선 LinkedList가 ArrayList보다 우위로 보면 된다.

연산	LinkedList (doubly)	ArrayList	추천
첫번째 위치에 insert / remove	O(1)	O(N)	LinkedList
마지막 위치에 insert / remove	O(1)	O(1) / O(N)	LinkedList
중간에 insert / remove	O(N) / search time + O(1)	O(N)	LinkedList
값으로 search	O(N)	O(N)	ArrayList
인덱스로 값 get	O(N)	O(1)	ArrayList
값으로 remove	O(N)	O(N)	LinkedList

위의 표에서 ArrayList에서 첫번째 삽입이 O(N)인 이유는 무조건적으로 요소들을 뒤로 이동해야 되기 때문이다. 그리고 마지막 위치 삽입이 O(1) 또는 O(N)이 되는 이유는 만일 공간 부족으로 인해 배열 복사가 일어나면 시간이 소요되기 때문이다.

 

실제 성능 측정

두 리스트에 대해 실제 메서드 동작 시간을 측정한 그래프이다.

조회(get)시에는 arraylist가 우위 지만 삽입/삭제(add/remove) 시에는 linkedlist가 뛰어난 성능을 보여준다.

public static void main(String[] args) {
    //추가할 데이터의 개수를 고려해서 크기를 지정해야함
    ArrayList<Number> al = new ArrayList<>();
    LinkedList<Number> ll = new LinkedList<>();

    System.out.println("+++ 순차적으로 추가하기 +++");
    System.out.println("ArrayList  : " + add1(al));
    System.out.println("LinkedList : " + add1(ll));
    System.out.println();

    System.out.println("+++ 중간에 추가하기 +++");
    System.out.println("ArrayList  : " + add2(al));
    System.out.println("LinkedList : " + add2(ll));
    System.out.println();

    System.out.println("+++ 접근시간 테스트 +++");
    System.out.println("ArrayList  : " + access(al));
    System.out.println("LinkedList : " + access(ll));
    System.out.println();

    System.out.println("+++ 중간에서 삭제하기 +++");
    System.out.println("ArrayList  : " + remove2(al));
    System.out.println("LinkedList : " + remove2(ll));
    System.out.println();

    System.out.println("+++ 순차적으로 삭제하기 +++");
    System.out.println("ArrayList  : " + remove1(al));
    System.out.println("LinkedList : " + remove1(ll));
    System.out.println();
}

public static long add1(List list) {
    long start = System.nanoTime();
    for (int i = 0; i < 10000; i++)
        list.add(i + 1);
    long end = System.nanoTime();
    return end - start;
}

public static long add2(List list) {
    long start = System.nanoTime();
    for (int i = 0; i < 10000; i++)
        list.add(500, 1);
    long end = System.nanoTime();
    return end - start;
}

public static long remove1(List list) {
    long start = System.nanoTime();
    for (int i = list.size() - 1; i >= 0; i--)
        list.remove(i);
    long end = System.nanoTime();
    return end - start;
}

public static long remove2(List list) {
    long start = System.nanoTime();
    for (int i = 0; i < 10000; i++)
        list.remove(500);
    long end = System.nanoTime();
    return end - start;
}

public static long access(List list) {
    long start = System.nanoTime();
    for (int i = 0; i < 10000; i++)
        list.get(i);
    long end = System.nanoTime();
    return end - start;
}

값이 작을 수록 빠르다

1. [순차 추가] 가 linkedlist가 우위인 이유는 arraylist는 공간 부족으로 인한 배열 복사가 일어나기 때문이다.
2. [중간 추가] 가 linkedlist가 우위인 이유는 arraylist는 배열 복사 및 데이터 이동(shift)가 발생하기 때문이다.
3. [접근 시간] 이 arraylist가 우위인 이유는 메모리 저장 구조상 배열은 연속된 공간에 저장되고 인덱스로 단번에 엑세스하기 때문이다.
4. [중간 삭제] 가 linkedlist가 우위인 이유는 요소 이동 없이 그저 노드의 포인팅만 교체만 하면 되기 때문이다.
5. [순차 삭제] 가 arraylist가 우위인 이유는 아무래도 노드의 링크를 끊고 하는 작업 보단 배열에서 요소를 삭제하는게 더 빠르기 때문이다.

---

✋ LinkedList는 의외로 잘 사용되지 않는다

보통 ArrayList 와 LinkedList 중에 어느걸 사용하면 되냐고 묻는다면, 삽입 / 삭제가 빈번하면 LinkedList를, 요소 가져오기가 빈번하면 ArrayList를 사용하면 된다 라고들 가르쳐 주지만, 사실 성능면에서 둘은 큰 차이가 없다.

예를들어 ArrayList는 리사이징 과정에서 배열 복사하는 추가 시간이 들지만, 배열을 새로 만들고 for문을 돌려 기존 요소를 일일히 대입하는 그러한 처리가 아니라, 내부적으로 잘 튜닝이 되고 최적화 되어있어 우리가 생각하는 것처럼 전혀 느리지않다.

위의 성능 코드 예시 역시 두각을 나타내기 위해 극단적으로 나노초로 비교해서 차이가 확연히 보여서 그렇지 체감상 차이가 그리 큰 편도 아니다.

또한 외국 사례를 검색하여 살펴보면 LinkedList를 사용하는 사례보다 그냥 ArrayList를 사용하는 사례가 많은데, 자바의 컬렉션 프레임워크 등 자바 플랫폼의 설계와 구현을 주도한 조슈아 블로치(Joshua Bloch) 본인도 자신이 설계했지만 사용하지 않는다고 말할 정도이다.

https://twitter.com/joshbloch/status/583813919019573248

몇몇 분들은 FIFO(선입선출)이 빈번할 경우, ArrayList 경우 첫번째에 요소를 추가할 때마다 자주 데이터 이동(shift)가 일어나기 때문에 큐(queue)를 사용해야 할때 LinkedList를 사용한다 라고 말하지만, 차라리 그런경우엔 따로 ArrayDeQue라는 더욱 최적화된 컬렉션을 쓰는 것이 훨씬 좋다.

---

# 참고자료

http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/

https://youtu.be/sq49IpxBl2k

https://youtu.be/xvi-n11kym0

https://youtu.be/1R8H-T1u-7E