티스토리 뷰
List Interface를 구현하는 ArrayList, Vector, LinkedList에 대해 알아보도록 하겠습니다.
3 자료구조에 대한 클래스 계층은 아래 그림과 같습니다.
ArrayList vs Vector
Vector 는 ArrayList와 거의 동일하며, 유일한 차이점은 동기화(synchronized)입니다.
이로 인해 ArrayList 보다는 오버헤드가 더 있습니다.
그래서 대부분의 자바 프로그래머들은 ArrayList를 더 많이 사용하고,
동기화가 필요한 경우에는 명시적으로 동기화를 구현합니다.
ArrayList vs LinkedList
두 자료구조의 시간 복잡도를 살펴보겠습니다.
ArrayList | LinkedList | |
get() | O(1) | O(n) |
add() | O(1) | O(1) amortized |
remove() | O(n) | O(n) |
LinkedList의 get()에서 시간 복잡도가 ArrayList에 비해 느린데,
값끼리 서로 링크가 연결되어 있어 이를 따라가서 값을 읽어와야 하기 때문에 O(n)의 시간 복잡도를 가집니다.
remove()에서는 두 자료구조가 같은 시간복잡도를 가지지만
ArrayList는 첫 번째 값을 삭제 시, 마지막 값을 삭제하는 것보다 더 느리다는 것을 알고 있는 것이 좋습니다.
ArrayList는 내부적으로 배열로 이루어져 있기 때문에 첫 번째 값을 삭제하면,
그 뒤의 모든 값의 인덱스를 하나씩 당겨줘야 하기 때문입니다.
결론
시간 복잡도를 봐서는 ArrayList 대신 LinkedList를 굳이 사용할 이유는 없는 것 같습니다.
그럼, 동기화의 여부에 따라 ArrayList나 Vector를 선택하여 사용하면 됩니다.
'Java' 카테고리의 다른 글
[ Java ] 자바 컴파일에 대한 이해 (0) | 2020.11.06 |
---|---|
[ Java ] static 에 관하여 (0) | 2020.09.28 |
[ Java ] - String, StringBuffer, StringBuilder 비교 (0) | 2020.09.21 |
클래스패스 Class path 란? (0) | 2020.08.13 |
[ Java ] Exception, RuntimeException 에 대하여 (0) | 2020.06.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- intellij
- mac
- install
- Postman
- Container
- maven
- Filter
- AWS
- logstash
- error
- Index
- spring boot
- JSON
- Linux
- Java
- docker
- gradle
- apm
- Git
- spring
- JPA
- tomcat
- SpringBoot
- Spark
- Log
- elasticsearch
- Kibana
- plugin
- Size
- scala
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함