Java 문법을 복습하며 Collection 구현체들을 사용하는 것 자체에서 고민이 많았습니다.
조금이라도 효율적으로 구성해야하는 서버의 특성 상 자세히 그 특성을 알고 쓰고 싶은데, 그정도의 지식 깊이를 쌓지 못한 것 같습니다.
부족한 내용들을 다시 공부하였고, 나중에 까먹으면 다시 보기 위해 정리하였습니다.
kai6666님의 글 | Jeerryy님의 글
geeksforgeeks
순서 O, 데이터 중복 O
List는 순서를 가지고 중복을 허용하는 자료구조로, 내부 element들은 추가순서에 따라 정리됩니다.
특정 항목에 접근하기 위해 index 번호를 사용할 수 있으며, 위치와 무관하게 모든 데이터에 접근할 수 있음을 의미합니다.
| 유형 | Method | Return | 설명 |
|---|---|---|---|
| 추가 | List.add( int index, Object element ) | void | index 위치에 element를 추가합니다 |
| 추가 | List.addAll( int index, Collection c ) | boolean | index 위치에 c를 추가합니다 |
| 수정 | List.set( int index, Object element ) | Object | index 위치에 element를 저장합니다 (기존값이 있다면 덮어씌웁니다) |
| 수정 | List.sort( Comparator c ) | void | List에 담겨있는 값들을 주어진 Comparator의 기준에 맞춰 정렬합니다 |
| 조회 | List.get( int index ) | Object | index 위치의 값을 불러옵니다 |
| 조회 | List.indexOf( Object o ) | int | 특정 객체가 저장된 index 값을 불러옵니다 (순방향 탐색 / 동일객체가 저장된 경우 가장 빠른순번을 return) |
| 조회 | List.lastIndexOf( Object o ) | int | 특정 객체가 저장된 index 값을 불러옵니다 (역방향 탐색 / 동일객체가 저장된 경우 가장 늦은순번을 return) |
| 조회 | List.contains( Object o ) | boolean | 특정 객체가 list 내부에 포함되어있는지 확인합니다 |
| 제거 | List.remove( int index ) | Object | index 위치의 값을 삭제하고, 삭제한 값을 return 합니다 |
| 제거 | List.remove( Object o ) | boolean | 주어진 객체를 List에서 찾아 삭제하고, 삭제여부를 return 합니다 |
전체적인 구현체들의 상속관계는 다음과 같습니다
- AbstractCollection (implements Collection) [Class(Abstract)]
- AbstractList (implements List) [Class(Abstract)]
- ArrayList (implements List, RandomAccess, Cloneable, java.io.Serializable) [Class]
- AbstractSequentialList [Class(Abstract)]
- LinkedList (implements List, Deque, Cloneable, java.io.Serializable) [Class]
조회를 많이하는 경우 사용하면 좋은 List 구현체. 추가/삭제를 많이하는경우 "최대한" 지양
Vector를 개선한 List 구현 클래스로, Object 배열을 사용하여 데이터를 순차적으로 저장합니다.
따라서 초기에 생성된 배열의 크기보다 더 많은 양의 Object가 입력되면 배열의 크기를 늘려 다시 선언하고 데이터를 옮기는 작업이 발생합니다.
(보통은 크기를 늘릴 때 1.5~2배를 늘리므로 크기조정이 필요한 경우가 많지는 않다고 합니다)
List<Integer> nums = new ArrayList<Integer>(); // default: 10
List<Integer> nums = new ArrayList<Integer>(50); // 사이즈 지정 시 해당 크기만큼 초기배열 생성
| 동작유형 | 시간복잡도 | 설명 |
|---|---|---|
| 추가 | O(1) / O(n) | 배열크기를 초과하여 재할당 시 O(n) |
| 조회 - get | O(1) | - |
| 조회 - next | O(1) | - |
| 조회 - indexOf | O(n) | - |
| 조회 - contains | O(n) | - |
| 삭제 | O(n) | 위치로 이동 후 삭제 / 뒤에 있는 값들을 1칸씩 당김 |
추가/삭제를 많이하는 경우 사용하면 좋은 List 구현체. 조회를 많이하는경우 지양
element 상호 간 다음데이터를 바라보는 필드 (next)를 가지고 있어 논리적으로만 데이터들을 순서대로 연결한 형태입니다.
덕분에 데이터의 추가/삭제가 빠르지만, 조회의 경우 성능이 떨어집니다
(1번째 데이터부터 next 필드를 통해 다음데이터로 계속 이동하며 찾아야 하기 때문)
| 동작유형 | 시간복잡도 | 설명 |
|---|---|---|
| 추가 | O(1) | - |
| 조회 - get | O(n) | next 필드를 보며 처음부터 하나씩 이동하며 데이터를 찾아야 하기 때문 |
| 조회 - next | O(1) | next 필드를 통해 바로 다음 값은 빠르게 찾을 수 있음 |
| 조회 - indexOf | O(n) | - |
| 조회 - contains | O(n) | - |
| 삭제 | O(1) | 해당 데이터를 바라보는 이전노드의 next 필드값만 수정하면 됨 |
TIP) 대량조회를 빠르게하는 방법
- 리스트 내부의 다수 데이터를 빠르게 찾아야한다면, Iterator를 활용하자
- 만약 연속적으로 모든 값에 접근해야한다면, 일반적인 for문 보다는 내부적으로 Iterator를 활용하여 접근하는 for-each문을 애용하자
List를 구현하는 각 구현체별로 외우기만 했던 특징들이 왜 그런 특징을 가지게 되었는지 '이유'를 알아보는 기회가 되었습니다.
다양한 List를 문제상황에 맞게 적절히 사용하는 연습을 하며 익혀야겠습니다.
조회는 ArrayList, 추가/삭제는 LinkedList, 대량접근은 iterator나 for-each!