CS/Data Structure
[Java-자료구조] ArrayList vs LinkedList
egovici
2022. 1. 16. 18:30
지금까지 ArrayList와 LinkedList의 특징과 장단점, 구현까지 해보았다.
[Java] ArrayList 사용과 구현
ArrayList List 인터페이스를 상속받은 클래스 일반적인 배열과 동일하게 연속적인 공간을 사용하고 인덱스 또한 0부터 시작된다. 인덱스를 통한 임의접근이 가능하다 객체가 추가되면서 현재 가
minit-devlog.tistory.com
[Java] LinkedList 사용과 구현
LinkedList List 인터페이스를 상속받은 클래스 연속적인 공간을 사용하지 않고 모든 데이터가 노드(데이터 + 주소)로 구성되어있다. index가 없기 때문에 임의접근이 불가능하다. Singly LinkedList(data + n
minit-devlog.tistory.com
Collection Framework에서의 계층구조
LinkedList를 확인하면 Abstract Sequential List를 상속하고 있는 반면, ArrayList의 경우 AbstractList를 상속하고 있다.
즉 구조적인 차이가 나타나는 것을 확인할 수 있다.
| data | data | data | data |
ArrayList
| ArrayList | LinkedList | |
| 저장방식 | 연속적인 메모리 공간 | 불연속적인 메모리 공간 |
| 검색 | 인덱스 기반의 자료구조로 빠름 | 모든 요소 탐색이 필요하기에 느림 |
| 삽입/삭제 | 느림 | 빠름 |
| 유리한 상황 | 데이터의 개수가 자주 변하지 않고 검색, 수정을 자주 할 경우 | 데이터의 개수의 변경이 잦고 삽입이나 삭제가 자주 일어나는 경우 |
시간 복잡도(Time Complexity)
| 작업 | 메소드 | ArrayList | LinkedList |
| 데이터 마지막에 추가 | add() | O(1) copy op가 필요시 O(N) |
O(1) |
| 데이터 중간에 추가 | add(int index, Object element) | O(N) | O(N) |
| index에 위치한 데이터 제거 | remove(int index) | O(N) | O(N) |
| 특정 데이터를 제거 | remove(Object element) | O(N) | O(N) |
| index로 데이터 검색/ 수정 | get(int index) set(int index, Object element) |
O(1) | O(N) |
| 데이터로 index 검색 | indexOf(Object element) | O(N) | O(N) |