Language/Java

[JAVA - 자료구조] ArrayList vs LinkedList

leegeonwoo 2024. 6. 9. 17:32

직접 구현한 ArrayList와 LinkedList비교

EXAMPLE

기능 ArrayList LinkedList
앞에 추가(삭제) O(n) - 1369ms O(1) - 2ms
중간 추가(삭제) O(n) - 651ms O(n) - 1112ms
뒤에 추가(삭제) O(1) - 2ms O(n) - 2195ms
인덱스 조회 O(1) - 1ms O(n) - 평균 438ms
검색 O(n) - 평균 115ms O(n) - 평균 492ms

자바의 ArrayList와 LinkedList비교

기능 ArrayList LinkedList
앞에 추가(삭제) O(n) - 106ms O(1) - 2ms
중간 추가(삭제) O(n) - 49ms O(n) - 1112ms
뒤에 추가(삭제) O(1) - 1ms O(1) - 2ms
인덱스 조회 O(1) - 1ms O(n) - 평균 438ms
검색 O(n) - 평균 104ms O(n) - 평균 492ms

앞에 추가
===ArrayList===에서 맨 앞에 데이터를 추가할 경우 기존 모든 데이터를 한 칸씩 밀어야하는 과정이 필요했는데 이를 for문으로 한칸씩 데이터를 밀었었다.
하지만 자바에서 제공하는 ArrayList는 ===메모리 고속복사 연산===을 사용하여 성능을 10배이상 최적화한 것을 확인할 수 있다. ===O(n)===

[!NOTE] 메모리 고속복사 연산
메모리 고속복사 연산은 배열의 데이터는 순서대로 나열되어있다는 특징을 이용하여 ArrayList를 최적화 한것으로 데이터를 하나씩 일일이 미는 것이아니라 순서대로 나열되어있는 데이터를 통째로 묶어서 이동하는 방법이다.
System.arraycopy()를 사용

===LinkedList===는 데이터를 앞에 추가할 때 뒤에 데이터들은 밀 필요없이 노드의 참조값만 변경하기때문에 ArrayList보다는 빠른 연산속도를 갖는다. ===O(1)===

중간 추가(평균 추가)/삭제
===ArrayList===는 중간에 데이터를 추가할 때 인덱스를 검색하는 과정과 데이터를 추가하는 과정 두 가지 과정을 거치는데 인덱스를 검색하는 것은 배열의 특징으로 굉장히 빠르며 O(1)의 검색속도를 갖는다.
데이터를 추가하는 과정에서는 마찬가지로 데이터를 한 칸씩 밀어야하기때문에 O(n)의 속도를 갖는다.===O(n)===

===LinekdList===도 마찬가지로 추가하고자하는 index를 검색하는 과정과 추가하는 과정 두 가지 과정을 거치는데 LinkedList에서는 index를 검색하는 과정에서 O(n)의 속도를 갖고 추가하는 과정에서 O(1)의 속도를 갖기때문에 ===O(n)===의 빅오표기법이 산출된다.

뒤에 추가(삭제)
===ArrayList===에서는 데이터를 추가하고자하면 원래 맨 뒤에 추가되기때문에 데이터를 땡기거나 미뤄야할 필요가 없으며 데이터를 단순히 추가해주기만 하면되기때문에 ===O(1)===의 빅오 표기법이 산출된다

===LinkedList===에서는 last필드를 지원하기때문에 마지막 필드에 데이터를 추가해주기만 하면 되기떄문에 ===O(1)===의 빅오 표기법이 산출된다.

인덱스 조회
===ArrayList===의 특징중 하나는 메모리상에 순서대로 나열되어있기때문에 검색하고자하는 인덱스를 통해 값을 조회하기만하면 되기때문에 ===O(1)===의 빅오 표기법이 산출된다.

===LinkedList===에서는 찾고자하는 인덱스의 노드를 모두 조회해야하기때문에 평균적으로 ===O(n)===의 빅오 표기법이 산출된다.

검색
===ArrayList===는 검색하려는 데이터를 찾기위해 배열을 순회하기때문에 ===O(n)===빅오 표기법 산출
===LinkedList===도 마찬가지로 검색하려는 데이터를 찾기위해 모든 Node를 조회하기때문에 ===O(n)===빅오 표기법이 산출된다

공부자료 참조: 인프런 - 김영한
[https://www.inflearn.com/users/74366/@yh](https://www.inflearn.com/users/74366/@yh)

728x90