JAVA ArrayList와 LinkedList 성능 비교

자료구조(1) 에서 배열과 연결리스트의 시간 복잡도에 대해서 알아보았다. Java의 컬랙션 프레임워크 에 있는 배열(ArrayList) 와 연결리스트(LinkedList)의 성능을 여러 상황에서의 데이터 추가 / 삭제 / 조회 을 비교해보겠다.

성능 비교한 코드는 아래 주소에 있다. 실행되는 환경별로 성능의 차이가 있으니 걸리는 시간 값 자체보다는 ArrayList와 LinkedList가 어떤 차이를 보이는지를 보겠다.

테스트코드주소

1. 데이터 추가

기존에 데이터가 있는 상태에서 데이터를 추가하는 위치에 따라 4가지로 나눠서 성능을 비교해보았다.

- 순차 추가 : 리스트의 끝에서 추가

- 중간 추가 : 리스트의 사이즈로 중간 인덱스를 구해서 추가

- 역차 추가 : 리스트의 0번째 인덱스에 추가

- 랜덤 추가 : 리스트의 사이즈 내에 있는 랜덤한 인덱스에 추가

@Test
public void compareAddTest() {
    List<String> arrayList = new ArrayList<>();
    List<String> linkedList = new LinkedList<>();
    int initListSize = 100000;
    int addNumber = 50000;


    //순차 추가
    addAsc(arrayList, initListSize);
    addAsc(linkedList, initListSize);
    System.out.println("addAsc(arrayList)   :: " + addAsc(arrayList, addNumber));
    System.out.println("addAsc(linkedList)  :: " + addAsc(linkedList, addNumber));
    arrayList.clear();
    linkedList.clear();

    System.out.println();

    //중간 추가
    addAsc(arrayList, initListSize);
    addAsc(linkedList, initListSize);
    System.out.println("addInMiddle(arrayList)  :: " + addInMiddle(arrayList, addNumber));
    System.out.println("addInMiddle(linkedList) :: " + addInMiddle(linkedList, addNumber));
    arrayList.clear();
    linkedList.clear();

    System.out.println();

    //역순 추가
    addAsc(arrayList, initListSize);
    addAsc(linkedList, initListSize);
    System.out.println("addDesc(arrayList)  :: " + addDesc(arrayList, addNumber));
    System.out.println("addDesc(linkedList) :: " + addDesc(linkedList, addNumber));
    arrayList.clear();
    linkedList.clear();

    System.out.println();

    //랜덤 추가
    addAsc(arrayList, initListSize);
    addAsc(linkedList, initListSize);
    System.out.println("addRandom(arrayList)    :: " + addRandom(arrayList, addNumber));
    System.out.println("addRandom(linkedList)   :: " + addRandom(linkedList, addNumber));


}
/**
 * addAsc(arrayList)   :: 5
 * addAsc(linkedList)  :: 4
 *
 * addInMiddle(arrayList)  :: 564
 * addInMiddle(linkedList) :: 41330
 *
 * addDesc(arrayList)  :: 1425
 * addDesc(linkedList) :: 7
 *
 * addRandom(arrayList)    :: 635
 * addRandom(linkedList)   :: 39824
 */

1.1 순차 추가 - addAsc

ArrayList 와 LinkedList 둘다 매우 빠른 성능을 보인다.

ArrayList는 끝에 데이터를 추가하기만 하면 되고 내부 배열 보다 사이즈가 커지면 배열 Copy 하면 되기 때문에 빠르다.

LinkedList는 내부 노드 중 마지막(last) 에 있는 노드 뒤에 붙이기만 하기 때문에 빠르다.

1.2 중간 추가 - addInMiddle

ArrayList 와 LinkedList 둘다 순차 추가에 비하면 시간이 오래걸렸다.

ArrayList는 중간 인덱스(size/2) 이후의 값들을 한칸씩 옆으로 옴기는 과정이 있기 때문에 오래걸렸다.

LinkedList는 중간 인덱스에 추가하기 위해 0번째 값부터 중간 인덱스까지 찾아야 하기 때문에 오래 걸렸다.

1.3 역차 추가 - addDesc

ArrayList는 모든 값들을 한칸씩 옆으로 옴기는 과정이 있기 때문에 중간 추가보다도 오래걸렸다.

LinkedList는 내부 노드 중 맨앞(first) 에 있는 노드 뒤에 붙이기만 하기 때문에 빠르다.

1.4 랜덤 추가 - addRandom

ArrayList는 Radom으로 나온 인덱스의 평균 기댓값이 중간 인덱스(size/2) 이기 때문에 순차보다는 느리고 역차보다는 빨랐다. 중간 추가 보다 느린 이유는 Random 값을 생성하는데에서 시간이 더 걸리지 않았나 싶다.

LinkedList는 내부가 Double LinkedList 이기 때문에 순차 추가와 중간 추가 사이 정도의 시간이 걸릴것으로 예상했다. 하지만 중간 추가보다도 오래 걸렸다.

중간 추가는 추가할때 마다 이전 추가와 비슷한 과정으로 추가하지만 랜덤은 아니니 메모리 캐싱에 있어서 도 효율적이지 않았을까 예상해본다.(완전 뇌피셜)

2. 데이터 삭제

데이터를 넣어둔 상태에서 삭제하는 위치에 따라 3가지로 나눠서 성능을 비교해보았다.

- 순차 삭제 : 리스트의 0번째 인덱스에 삭제

- 중간 삭제 : 리스트의 사이즈로 중간 인덱스를 구해서 삭제

- 역차 삭제 : 리스트의 끝에서 삭제

- 랜덤 삭제 : 리스트의 사이즈 내에 있는 랜덤한 인덱스에 삭제

@Test
public void compareRemoveTest(){
    List<String> arrayList = new ArrayList<>();
    List<String> linkedList = new LinkedList<>();
    int caseNumber = 100000;


    //순차 삭제
    addAsc(arrayList, caseNumber);
    addDesc(linkedList, caseNumber);
    System.out.println("removeAsc(arrayList)    :: "+removeAsc(arrayList));
    System.out.println("removeAsc(linkedList)   :: "+removeAsc(linkedList));

    System.out.println();

    //중간 삭제
    addAsc(arrayList, caseNumber);
    addDesc(linkedList, caseNumber);
    System.out.println("removeInMiddle(arrayList)   :: "+removeInMiddle(arrayList));
    System.out.println("removeInMiddle(linkedList)  :: "+removeInMiddle(linkedList));

    System.out.println();


    //역순 삭제
    addAsc(arrayList, caseNumber);
    addDesc(linkedList, caseNumber);
    System.out.println("removeDesc(arrayList)   :: "+removeDesc(arrayList));
    System.out.println("removeDesc(linkedList)  :: "+removeDesc(linkedList));

    System.out.println();

    //랜덤 삭제
    addAsc(arrayList, caseNumber);
    addDesc(linkedList, caseNumber);
    System.out.println("removeRandom(arrayList)     :: "+removeRandom(arrayList));
    System.out.println("removeRandom(linkedList)    :: "+removeRandom(linkedList));

}
/**
 * removeAsc(arrayList)    :: 502
 * removeAsc(linkedList)   :: 3
 *
 * removeInMiddle(arrayList)   :: 521
 * removeInMiddle(linkedList)  :: 28571
 *
 * removeDesc(arrayList)   :: 6
 * removeDesc(linkedList)  :: 5
 *
 * removeRandom(arrayList)     :: 830
 * removeRandom(linkedList)    :: 28464
 */

2.1 순차 삭제 - removeAsc

역차 추가와 같은 이유로 성능 차이가 발생하였다.

ArrayList는 모든 값들을 한칸씩 옆으로(i에서 i-1로) 옴기는 과정이 있기 때문에 오래걸렸다.

LinkedList는 내부 노드 중 맨앞(first) 에 있는 노드 뒤에 삭제만 하면 되기 때문에 빠르다.

2.2 중간 삭제 - removeInMiddle

중간 추가와 같은 이유로 위의 성능 차이가 나왔다.

2.3 역차 삭제 - removeDesc

순차 추가와 같은 이유로 둘다 매우 빠르다.

ArrayList는 끝에 데이터를 삭제하기만 하면 되고 내부 배열 보다 사이즈가 작아지면 배열 Copy 하면 되기 때문에 빠르다.

LinkedList는 내부 노드 중 마지막(last) 에 있는 노드 뒤에 삭제하면 되기 때문에 빠르다.

2.4 랜덤 삭제 - removeRandom

랜덤 추가와 같은 이유로 위의 성능 차이가 나왔다.

3. 데이터 조회

데이터를 넣어둔 상태에서 조회하는 위치에 따라 5가지로 나눠서 성능을 비교해보았다.

- 순차 조회 : 리스트의 0번째 부터 인덱스로 조회

- Iterator 순차 조회 : 리스트의 0번째 부터 Iterator 로 조회

- 역차 조회 : 리스트의 끝 부터 인덱스로 조회

- Iterator 역차 조회 : 리스트의 끝부터 Iterator 로 조회

- 랜덤 삭제 : 리스트의 사이즈 내에 있는 랜덤한 인덱스에 삭제

@Test
public void getTest(){
    List<String> arrayList = new ArrayList<>();
    List<String> linkedList = new LinkedList<>();
    int caseNumber = 100000;

    addAsc(arrayList, caseNumber);
    addAsc(linkedList, caseNumber);

    //순차 조회
    System.out.println("getAsc(arrayList)   :: "+getAsc(arrayList));
    System.out.println("getAsc(linkedList)  :: "+getAsc(linkedList));

    System.out.println();

    //iterator 순차 조회
    System.out.println("getAscIterator (arrayList)   :: "+getAscIterator(arrayList));
    System.out.println("getAscIterator(linkedList)  :: "+getAscIterator(linkedList));

    System.out.println();

    //역차 조회
    System.out.println("getDesc(arrayList)  :: "+getDesc(arrayList));
    System.out.println("getDesc(linkedList) :: "+getDesc(linkedList));

    System.out.println();

    //iterator 역차 조회
    System.out.println("getDescIterator (arrayList)   :: "+getDescIterator(arrayList));
    System.out.println("getDescIterator(linkedList)  :: "+getDescIterator(linkedList));

    System.out.println();

    //랜덤 조회
    System.out.println("getRandom(arrayList)    :: "+getRandom(arrayList));
    System.out.println("getRandom(linkedList)   :: "+getRandom(linkedList));
}
/**
 * getAsc(arrayList)   :: 7
 * getAsc(linkedList)  :: 10553
 *
 * getAscIterator (arrayList)   :: 4
 * getAscIterator(linkedList)  :: 4
 *
 * getDesc(arrayList)  :: 2
 * getDesc(linkedList) :: 10335
 *
 * getDescIterator (arrayList)   :: 5
 * getDescIterator(linkedList)  :: 5
 *
 * getRandom(arrayList)    :: 9
 * getRandom(linkedList)   :: 15035
 */

3.1 순차, 역차 조회 - getAsc, getDesc

ArrayList는 인덱스로 조회하기 때문에 순서에 상관없이 매우 빠른 성능을 보인다.

LinkedList는 0번째 값부터 i번째 노드까지 하나씩 찾아야 하기 때문에 오래 걸렸다.

LinkedList는 내부가 Double LinkedList 이기 때문에 순차 역차의 속도가 거의 같다.

3.2 iterator 순차, 역차 조회 - getAscIterator, getDescIterator

ArrayList는 인덱스로 조회하기 때문에 순서에 상관없이 매우 빠른 성능을 보인다.

LinkedList는 iterator 를 통해 다음 노드의 주소로 바로 접근하기 때문에 빠른 성능을 보인다.

3.3 랜덤 조회 - getRandom

ArrayList는 인덱스로 조회하기 때문에 순서에 상관없이 매우 빠른 조회 성능을 보인다.

LinkedList는 랜덤 추가와 같은 이유로 위의 성능 차이가 나온것 같다.

4. 마치며

종류별, 상황별 성능 테스트하는 방식은 coco3o 님 블로그 글에서 영향을 받아 작성하게 되었다. 하지만 coco3o 님의 글의 일부에 문제가 있다고 생각한다.

======순차적으로 추가하기======
ArrayList = 92
LinkedList = 145

======중간에 추가하기======
ArrayList = 3142
LinkedList = 11

======중간에 삭제하기======
ArrayList = 1746
LinkedList = 116

======순차적으로 삭제하기======
ArrayList = 8
LinkedList = 19

출처: https://dev-coco.tistory.com/19 [슬기로운 개발생활😃:티스토리]

coco3o 님은 위와 같은 성능 테스트를 통해 2가지 결론을 내리셨다.

하나는 '순차적으로 추가/삭제하는 경우 ArrayList가 LinkedList보다 빠르다' 는 것이고

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

coco3o 님의 첫번째 결론에는 동의한다. coco3o님은 스택처럼 데이터를 삭제하는것을 순차라고 생각하셨기 때문에 필자의 역차 삭제와 같아서 결론은 동일하다.

하지만 두번째 결론은 동의하지 않는다. 왜냐면 순차 추가의 경우는 1,000,000건의 데이터를 추가할때 걸리는 시간의 비교이다. 하지만 중간 추가는 사이즈가 1,000,000인 list 에 500번째 인덱스에 값을 10,000번 추가하는 상황이기 때문에 ArrayList 내부에 있는 배열 값중 99.95 % 의 데이터를 옴기는 과정 때문에 오래걸린 것이다. 또한 LinkedList 에서 데이터 추가는 500번째 값만 찾으면 되기 때문에 빠를 수 밖에 없다.

중간 데이터(비 순차적) 추가하는 경우는 각 경우에 따라 처리 속도가 다르기 때문에 상황에 맞게 선택하길 권한다.

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3)

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)

'개발' 카테고리의 다른 글

JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6) (0)	2022.05.30
JAVA Queue 그리고 offer, poll , peek - 자료구조(5) (0)	2022.05.30
JAVA LinkedList 직접 구현하기 - 자료구조(3) (0)	2022.05.26
JAVA ArrayList 직접 구현하기 - 자료구조(2) (0)	2022.05.26
자료구조의 종류와 개념 - 자료구조(1) (0)	2022.05.26

지극히 주관적인

JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

1. 데이터 추가

1.1 순차 추가 - addAsc

1.2 중간 추가 - addInMiddle

1.3 역차 추가 - addDesc

1.4 랜덤 추가 - addRandom

2. 데이터 삭제

2.1 순차 삭제 - removeAsc

2.2 중간 삭제 - removeInMiddle

2.3 역차 삭제 - removeDesc

2.4 랜덤 삭제 - removeRandom

3. 데이터 조회

3.1 순차, 역차 조회 - getAsc, getDesc

3.2 iterator 순차, 역차 조회 - getAscIterator, getDescIterator

3.3 랜덤 조회 - getRandom

4. 마치며

'개발' 카테고리의 다른 글

티스토리툴바

JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

1. 데이터 추가

1.1 순차 추가 - addAsc

1.2 중간 추가 - addInMiddle

1.3 역차 추가 - addDesc

1.4 랜덤 추가 - addRandom

2. 데이터 삭제

2.1 순차 삭제 - removeAsc

2.2 중간 삭제 - removeInMiddle

2.3 역차 삭제 - removeDesc

2.4 랜덤 삭제 - removeRandom

3. 데이터 조회

3.1 순차, 역차 조회 - getAsc, getDesc

3.2 iterator 순차, 역차 조회 - getAscIterator, getDescIterator

3.3 랜덤 조회 - getRandom

4. 마치며

'개발' 카테고리의 다른 글

'개발' Related Articles

티스토리툴바