[Java] ArrayList vs LinkedList 비교

자료구조 란?

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 한다.

리스트 자료구조 란?

순서가 있고, 중복을 허용하는 자료 구조를 리스트(List)라 한다.

 

ArrayList

출처 : medium

동적배열을 사용하여 데이터를 저장하는 리스트 형태의 자료구조

 

내부구조 : ArrayList는 내부적으로 배열을 사용해서 데이터를 저장한다. 초기 크기를 설정할수 있지만 데이터가 추가되면 크키가 자동으로 증가된다.

 

특징

https://poiemaweb.com/js-array-is-not-arrray

 - 인덱스를 통한 접근 속도 : 내부적으로 배열으로 되어 있기 때문에 인덱스를 통해 데이터를 접근하기 때문에 굉장히 빠르다.O(1)

- 삽입/삭제 속도 : 배열의 특정 위치에 삽입하거나 삭제하려면 해당 위치 요소를 다 이동해야 하므로 성능이 떨어진다. O(n)

- 메모리 사용효율 : 배열은 메모리가 할당될때 연속적으로 할당되므로 LinkedList보다 메모리 사용이 효율적이다.

 

LinkedList

노드를 사용해서 데이터를 저장하는 리스트 자료구조

 

public class Node {

  Object item;
  Node next;

  public Node(Object item){
    this.item = item;
  }
}

public class MyLinkedListV3<E> {

  private Node<E> first;
  private int size = 0;

...
}

내부구조 : LinkedList 는 내부적으로 노드들로 이어져 있다. 노드는 데이터와 다음, 이전 노드를 가리키는 참조로 되어 있다.

 

특징

 - 삽입/삭제 속도 : 리스트의 처음이나 중간에 데이터를 삽입하거나 삭제하는 경우, 노드의 이전 이후 참조만 변경하면 되므로 빠르다 O(1)

- 인덱스를 통한 접근 속도 : 인덱스를 통해 접근하려면 첫 노드부터 순차적으로 탐색 해야하므로 속도가 느리다. O(n)

- 메모리 사용 효율 : 각 노드가 데이터와 두개의 참조(다음,이전)을 가지고 있기 때문에, ArrayList 보다 메모리를 더 많이 사용한다.

 

 

ArrayList vs LinkedList 성능 비교

package collection.list;

public class MyListPerformanceTest {

  public static void main(String[] args) {
    int size = 50_000;
    System.out.println("== MyArrayList 추가 ==");	// 크기만큼 데이터 추가
    addFirst(new MyArrayList<>(),size);
    addMid(new MyArrayList<>(),size);
    MyArrayList<Integer> arrayList = new MyArrayList<>();
    addLast(arrayList,size); 

    System.out.println("== MyLinkedList 추가 ==");
    addFirst(new MyLinkedList<>(),size);
    addMid(new MyLinkedList<>(),size);
    MyLinkedList<Integer> linkedList = new MyLinkedList<>();
    addLast(linkedList,size);

    int loop = 10000;
    System.out.println("==MyArrayList 조회=="); // 루프만큼 인덱스로 조회
    getIndex(arrayList, loop, 0);
    getIndex(arrayList, loop, size / 2);
    getIndex(arrayList, loop, size - 1);
    System.out.println("==MyLinkedList 조회==");
    getIndex(linkedList, loop, 0);
    getIndex(linkedList, loop, size / 2);
    getIndex(linkedList, loop, size - 1);
    System.out.println("==MyArrayList 검색==");
    search(arrayList, loop, 0);
    search(arrayList, loop, size / 2);
    search(arrayList, loop, size - 1);
    System.out.println("==MyLinkedList 검색==");
    search(linkedList, loop, 0);
    search(linkedList, loop, size / 2);
    search(linkedList, loop, size - 1);
  }

  private static void addFirst(MyList<Integer> list, int size){
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < size; i++) {
      list.add(0,i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
  }
  
  private static void addMid(MyList<Integer>list, int size){
    long startTime = System.currentTimeMillis();
    for (int i = 0; i <size ; i++) {
      list.add(i/2,i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
  }

  private static void addLast(MyList<Integer>list, int size){
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < size ; i++) {
      list.add(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
  }

  private static void getIndex(MyList<Integer> list, int loop, int index){
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < loop; i++) {
      list.get(index);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
  }

  private static void search(MyList<Integer> list, int loop ,int findValue){
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < loop; i++) {
      list.indexOf(findValue);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
  }
}

 

== MyArrayList 추가 ==
앞에 추가 - 크기: 50000, 계산 시간: 2051ms
평균 추가 - 크기: 50000, 계산 시간: 1018ms
뒤에 추가 - 크기: 50000, 계산 시간: 3ms
== MyLinkedList 추가 ==
앞에 추가 - 크기: 50000, 계산 시간: 4ms
평균 추가 - 크기: 50000, 계산 시간: 1316ms
뒤에 추가 - 크기: 50000, 계산 시간: 1626ms
==MyArrayList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms
index: 25000, 반복: 10000, 계산 시간: 1ms
index: 49999, 반복: 10000, 계산 시간: 0ms
==MyLinkedList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms
index: 25000, 반복: 10000, 계산 시간: 313ms
index: 49999, 반복: 10000, 계산 시간: 624ms
==MyArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 123ms
findValue: 49999, 반복: 10000, 계산 시간: 231ms
==MyLinkedList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 447ms
findValue: 49999, 반복: 10000, 계산 시간: 904ms

 

위에서 구현한 배열리스트와 연결리스트 성능

기능	배열 리스트	연결 리스트
앞에 데이터 추가(삭제)	O(n) - 2051ms (크기만큼 뒤로 밈)	O(1) - 4ms (first정보가 있음)
평균 데이터 추가(삭제)	O(n) - 1018ms (인덱스로 한번에 찾지만 데이터를 뒤로 밈)	O(n) - 1316ms(루프만큼 돌아서 인덱스를 찾음)
뒤에 데이터 추가(삭제)	O(1) - 3ms (인덱스로 한번에 찾고 뒤로 밀 데이터 없음)	O(n) - 1626ms (루프만큼 돌아서 인덱스를 찾음)
인덱스 조회	O(1) - 1ms (내부가 배열로 되어 있음 한버넹 찾음)	O(n) - (평균) 313ms
검색	O(n) - (평균) 123ms	O(n) - (평균) 447ms

 

자바에서 제공하는 배열리스트와 연결리스트 성능 비교

(※자바에서 제공하는 연결리스트는 이중연결리스트이다.)

(왼) 자바 제공 (오) 구현한 연결리스트

 

기능	배열 리스트	연결 리스트
앞에 데이터 추가(삭제)	O(n) - 106ms	O(1) - 2ms
평균 데이터 추가(삭제)	O(n) - 49ms	O(n) - 1116ms
뒤에 데이터 추가(삭제)	O(1) - 1ms	O(n) - 2ms
인덱스 조회	O(1) - 1ms	O(n) - (평균) 312ms
검색	O(n) - (평균) 104ms	O(n) - (평균) 427ms

 

실제 성능

- 이론적으로 LinkedList의 중간 삽입 연산은 ArrayList보다 빠를 수 있다.(왜냐면 순차로 찾아서 중간에 싸악 삽입 또는 삭제해주면 되니깐 ArraylList는 뒤로 데이터를 다 밀어줘야해서 더 늦다.) 그러나 실제적 접근 속도, 메모리 할당 및 해체 비용, cpu  캐시 활용도 등 다양한 요소에 의해 영향 받는다.

 

추가로 'ArrayList' 는 데이터를 한 칸씩 직접 이동하지 않고, 대신에 메모리 고속 복사(자바에서 System.arrayCopy)를 사용한다.

'ArrayList' 는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.

반면, 'LinkedList' 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율
이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다

 

정리하면 이론적으로 'LinkedList' 가 중간 삽입에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패
턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 'ArrayList'가 실제 사용 환경에서 더 나은 성능을 보여주는
경우가 많다.

 

배열 리스트 vs 연결 리스트

대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다.
만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

 

참고

김영한의 실전자바 - 중급2편

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

김영한의 실전 자바 - 중급 2편 강의 | 김영한 - 인프런