직접 구현한 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)
'Language > Java' 카테고리의 다른 글
[Java] - Generic (1) | 2024.06.15 |
---|---|
[Java - 자료구조] Set인터페이스 (0) | 2024.06.12 |
[JAVA - 자료구조] LinkedList (1) | 2024.06.09 |
[JAVA] 익명 클래스 (1) | 2024.06.09 |
[JAVA] 날짜와 시간 - LocalDate, LocalTime (0) | 2024.06.09 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!