[Java] 배열과 리스트(Collection) Class 별 기능과 속도 확인

자료구조	특징	추가(ADD) 속도	읽기(READ) 속도	검색(SEARCH) 속도	삭제(DELETE) 속도
배열(Array)	고정 크기. 메모리 연속 저장. 인텍스 기반 접근.	불가(크기 고정)	O(1)	O(n)	-
ArrayList	크기 동적 증가. 인덱스 기반 접근.	O(1) (끝에 추가 시)	O(1)	O(n) (전체 탐색)	O(n) (중간 삭제 시)
LinkedList	노드 기반 연결 구조. 삽입 및 삭제 빠름.	O(1) (노드 추가 시)	O(n)	O(n)	O(1) (노드 삭제 시)
HashMap	키 - 값 기반 저장. 해싱 사용으로 빠른 접근.	O(1)	O(1)	O(1)	O(1)
HashSet	유일한 값만 저장. 순서 없음.	O(1)	O(1)	O(1)	O(1)
TreeMap	정렬된 키-값 쌍 저장. 키를 기준으로 자동 정렬.	O(log n)	O(log n)	O(log n)	O(log n)
TreeSet	정렬된 유일한 값 저장. 정렬된 구조.	O(log n)	O(log n)	O(log n)	O(log n)
PriorityQueue	Heap 기반 우선순위 큐. 우선순위에 따라 자동 정렬.	O(1) (최소값)	O(log n)	O(log n)	O(n)

 

라고 작성은 했지만,,, 바로 연상되지 않았다.. 

그래서 각 기능을 수행할 때 어느 정도의 시간이 소요되는 지 시각화해서 정리하기로 했다.

 

각 자료 구조 별 기능 수행 시간을 직접 그래프화 해보자.

직접 간단하게 코드를 작성하면서 처리 속도를 확인하고 싶었다.

 

---

공통 사항

• 처리 요소 수 : 100,000 개
• Y축 : 처리에 요청된 시간(ms)
• x축 : legend 참고
• 테스트 수행 횟수 : 1회
• Collection

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
Map<Integer, Integer> hashMap = new HashMap<>();
Set<Integer> hashSet = new HashSet<>();
Map<Integer, Integer> treeMap = new TreeMap<>();
Set<Integer> treeSet = new TreeSet<>();
Queue<Integer> priorityQueue = new PriorityQueue<>();

---

[1] Collection 별 Performance Graph

1. ArrayList Performance Graph

 

2. LinkedList Performance Graph

 

3. HashMap Performance Graph

 

4. HashSet Performance Graph

 

5. TreeMap Performance Graph

 

6. TreeSet Performance Graph

 

7. PriorityQueue Performance Graph

 

---

[2] Method 별 Performance Graph

1. add(put) Performance Graph

2. get(contains) Performance Graph

3. remove Performance Graph

 

---

1번만 수행해서 정확한 자료는 아니지만, 각 자료구조의 특징이 정말 잘 들어나는 것 같다.

---

Git Code

https://github.com/justdoit0730/codingTest/tree/master/main/java/performance

codingTest/main/java/performance at master · justdoit0730/codingTest