나의개발일지
[java] ArryaList 본문
📌 리스트란?
자바 DOC를 보면 리스트에 대한 설명이 이렇게 나와 있다.
🤣 영어 울렁증이 있어서 GPT로 요약 해보았다.
List 인터페이스는 순서가 있는 컬렉션을 나타내며, 중복된 요소와 null 값을 허용합니다. 사용자는 리스트의 요소를 인덱스로 접근할 수 있으며, add, remove, equals, hashCode 메서드에 대한 추가적인 규칙이 있습니다. List는 양방향 접근과 삽입 및 교체가 가능한 ListIterator를 제공하며, 여러 요소를 한 번에 삽입하거나 제거할 수 있는 메서드도 제공합니다. 일부 구현체는 요소에 제한을 둘 수 있으며, 부적합한 요소 추가 시 예외가 발생할 수 있습니다. List는 자바 컬렉션 프레임워크의 일부입니다.
https://docs.oracle.com/javase/8/docs/api/
Java Platform SE 8
docs.oracle.com
결론적으로 리스트란
List는 자바의 컬렉션 프레임워크에서 제공되는 인터페이스로, 순서를 유지하며 요소를 저장하는 자료구조이다. List 인터페이스를 구현한 클래스들은 배열과 비슷하게 인덱스를 사용해 요소를 관리하지만, 크기가 동적으로 조정된다는 차이점이 있다. 오늘은 이러한 리스트인터페이스를 구현한 ArrayList를 공부해 볼거다.
📌 ArrayList
역시나 ArrayList에 대해 알아보려고 자바8 DOC에 들어가 봤는데 설명이 많다.
요약하자면
- 리스트를 구현한 동적 배열이다.
- size, isEmpty, get, set, iterator, listlterator 등이 상수 시간에 실행 된다.
- add연산의 경우 여러 요소를 추가할때는 O(n), 하나를 추가할때는 O(1)
- 그 외의 연사은 선형 시간 O(n)이 소요
- ArrayList인스턴스는 용량(capacity)를 가진다. 자동으로 늘어나며 직접 지정할 수 도 있다.
추가로 ArrayList는 여러 쓰레드에서 접근하면 동기화가 안된다. 그러므로 5번의 용량 증가는 동기화가 안된다.
그래서 동기화된 List가 있다!
List<> list = Collections.synchronizedList(new ArrayList<>());동기화 리스트는 멀티쓰레드 환경에서 사용하니 요번 포스트에서는 ArrayList만 보겠다.
절대 공부가 안된거 아님
생성자
ArrayList의 생성자는 3개가 있다.
- ArrayList()
- ArrayList(Collection< ? extends E> c)
- ArrayList(int initalCapacity)
1번은 기본 생성자로 기본 크기는 10 이다.
2번은 주어진 컬렉션의 요소들을 포함하는 리스트를 생성하는 생성자이다
3번은 초기용량을 주어주고 생성하는 생성자이다.
// 1번 생성 예시
ArrayList<String> list = new ArrayList<>(); // 초기 용량이 10인 빈 리스트 생성
// 2번 생성 예시
List<String> otherList = Arrays.asList("Apple", "Banana", "Orange");
ArrayList<String> list = new ArrayList<>(otherList); // 다른 컬렉션의 요소로 리스트 생성
// 3번 생성 예시
ArrayList<String> list = new ArrayList<>(50); // 초기 용량이 50인 빈 리스트 생성
갑자기 초기 용량설정이 성능에 얼마나 영양을 미치는지 궁금 했다.
그래서 직접 실험해 봤다.
list1은 초기용량은 설정하지 않은 것이고, list2는 초기용량을 설정한 것이다.
두개의 리스트를 만들고 1억번의 삽입연산을 테스트 해보기로 했다.
import java.util.ArrayList;
import java.util.List;
public class ArrayListTest {
public static void main(String[] args) {
TimeCheck timer = new TimeCheck();
timer.start();
ArrayList<Integer> list1 = new ArrayList<>();
for(int i = 0; i < 100_000_000; i++) {
list1.add(i);
}
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
timer.start();
ArrayList<Integer> list2 = new ArrayList<>(100_000_000);
for(int i = 0; i < 100_000_000; i++) {
list2.add(i);
}
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
}
}
공정한 테스트를 위해 하나씩 주석을 처리하며 테스트 하였다.
왼쪽이 초기용량 설정 안한것, 오른쪽이 초기용량 설정 한것 (나노초 단위이다)
1억번의 삽입 연산을 해본 결과 약 0.5초 ~ 0.6초 정도 차이가 났다. (MacBookM1pro 16Ram)
메모리도 테스트해 본결과 당연하게도 값을 지정해준게 더 적은 메모리를 차지했다.
근데 이 생성자를 사용하려면 대강 리스트에 얼마가 삽입 되어야 할 지 알아야 할 것 같다.
📌 ArrayList 메서드
ArrayList에는 많은 메서드 들이 있다. 그중 자주쓰는 몇가지 메서드를 알아보자.
| 메서드 | 설명 |
| add(E e) | 리스트의 끝에 요소를 추가한다 |
| add(int index, E element) | 특정 인덱스 위치에 요소를 추가한다 |
| get(int index) | 지정된 인덱스에 있는 요소를 반환한다 |
| set(int index, E element) | 지정된 인덱스의 요소를 새로운 값으로 교체한다 |
| remove(int index) | 지정된 인덱스에 있는 요소를 제거한다 |
| remove(Object o) | 지정된 객체를 리스트에서 제거한다 |
| size() | 리스트의 요소의 개수를 반환한다 |
| contains(Object o) | 리스트에 특정 객체가 포함되어있는지 확인한다 |
| isEmpty() | 리스트가 비어있는지 확인한다 |
| clear() | 리스트의 모든 요소를 제거한다 |
| indexOf() | 리스트에서 지정된 객체의 첫 번째 인덱스를 반환한다. |
| lastIndexOf(Object o) | 리스트에서 지정된 객체의 마지막 인덱스를 반환한다 |
| toArray() | 리스트의 모든 요소를 배열로 반환한다 |
| subList(int fromIndex, int toIndex) | 지정된 범위의 부분 리스트를 반환한다 |
| forEach(Consumer<? super E> action) | 리스트의 각 요소에 대해 순회한다 |
| trimToSize() | 리스트의 용량을 현재 요소의 크기에 맞게 축소한다 |
사용 예시
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
// 1. add(E e)
ArrayList<Integer> list = new ArrayList<>();
list.add(10); // 리스트 끝에 10 추가
System.out.println("add: " + list);
// 2. add(int index, E element)
list.add(1, 20); // 인덱스 1에 20 추가
System.out.println("add at index 1: " + list);
// 3. get(int index)
int value = list.get(1); // 인덱스 1의 값 가져오기
System.out.println("get: " + value);
// 4. set(int index, E element)
list.set(0, 30); // 인덱스 0의 값을 30으로 변경
System.out.println("set at index 0: " + list);
// 5. remove(int index)
list.remove(1); // 인덱스 1의 값 제거
System.out.println("remove at index 1: " + list);
// 6. remove(Object o)
list.remove(Integer.valueOf(30)); // 값 30을 리스트에서 제거
System.out.println("remove value 30: " + list);
// 7. size()
System.out.println("size: " + list.size()); // 리스트 크기 반환
// 8. contains(Object o)
boolean contains = list.contains(10); // 10이 리스트에 포함되어 있는지 확인
System.out.println("contains 10: " + contains);
// 9. isEmpty()
System.out.println("isEmpty: " + list.isEmpty()); // 리스트가 비어있는지 확인
// 10. clear()
list.clear(); // 리스트의 모든 요소 제거
System.out.println("clear: " + list);
// 11. indexOf(Object o)
list.add(10);
list.add(20);
list.add(30);
System.out.println("indexOf 20: " + list.indexOf(20)); // 값 20의 첫 번째 인덱스 반환
// 12. lastIndexOf(Object o)
list.add(20);
System.out.println("lastIndexOf 20: " + list.lastIndexOf(20)); // 값 20의 마지막 인덱스 반환
// 13. toArray()
Integer[] array = list.toArray(new Integer[0]); // 리스트를 배열로 변환
System.out.println("toArray: ");
for (Integer num : array) {
System.out.println(num);
}
// 14. subList(int fromIndex, int toIndex)
List<Integer> sublist = list.subList(0, 2); // 인덱스 0부터 2 이전까지의 서브리스트 반환
System.out.println("subList (0, 2): " + sublist);
// 15. forEach(Consumer<? super E> action)
System.out.println("forEach: ");
list.forEach(num -> System.out.println(num)); // 리스트의 모든 요소 출력
// 16. trimToSize()
list.trimToSize(); // 리스트 용량을 현재 크기로 축소
System.out.println("trimToSize: " + list);
}
}
결과
add: [10]
add at index 1: [10, 20]
get: 20
set at index 0: [30, 20]
remove at index 1: [30]
remove value 30: []
size: 0
contains 10: false
isEmpty: true
clear: []
indexOf 20: 1
lastIndexOf 20: 3
toArray:
10
20
30
20
subList (0, 2): [10, 20]
forEach:
10
20
30
20
trimToSize: [10, 20, 30, 20]
📌 성능최적화
나는 ArrayList를 최대한 최적화를 해보고 싶었다.
추가연산과 조회연산을 실험해 보자
추가연산
테스트 시나리오
- 하나씩 add연산으로 추가
- 배열(Array)로 만들어서 addAll()메서드로 리스트 추가
- 병렬처리로 리스트에 추가
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;
public class ArrayListOptimization {
public static void main(String[] args) {
TimeCheck timer = new TimeCheck();
timer.start();
int[] arr = new int[100_000_000];
for(int i = 0; i < 100_000_000; i++) {
arr[i] = i;
}
List<Integer> list2 = new ArrayList<>(100_000_000);
List<Integer> tempList = Arrays.stream(arr)
.boxed()
.toList(); // int[] -> List<Integer> 변환
list2.addAll(tempList); // addAll로 추가
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
timer.start();
List<Integer> list = new ArrayList<>(100_000_000);
IntStream.range(0, 100_000_000)
.parallel()
.forEach(i -> list.add(i));
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
timer.start();
List<Integer> list1 = new ArrayList<>(100_000_000);
for(int i = 0; i< 100_000_000; i++) {
list1.add(i);
}
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
}
}
| 방법 | 시간(나노초) |
| 하나씩 add 연산 | 975353292 |
| 배열로 만들어서 addAll | 1834422375 |
| 병렬처리 | 7720796375 |
결과 : 하나씩 add < 배열로 만들기 < 병렬처리
이유를 GPT에게 물어보았다.
배열로 만들어서 addAll 방식은 배열을 리스트로 변환하는 box() 에서 int -> Integer로 변환을 해야해서 추가적인 오버헤드가 발생한다 고 하였다
병렬 처리방식은 여러쓰레드를 이용하여 리스트에 추가하는 방식인데 ArrayList는 동기화 되지 않아서 동기화를 시키는데 오버헤드가 많이 발생 한다고 하였다.
역시 기존 메서드 쓰는게 가장 좋은듯?
조회연산
테스트 시나리오
- for문으로 get메서드로 읽기
- 병렬처리로 리스트 읽기
- 직렬처리로 리스트 읽기
- Iterator
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.stream.IntStream;
public class ArrayListGetOptimization {
public static void main(String[] args) {
TimeCheck timer = new TimeCheck();
// 1. 데이터를 ArrayList에 저장
List<Integer> list = new ArrayList<>(100_000_000);
for (int i = 0; i < 100_000_000; i++) {
list.add(i);
}
// 2. 기본 get() 메서드를 사용하여 데이터 읽기
// 161245458
timer.start();
for (int i = 0; i < 100_000_000; i++) {
int value = list.get(i);
}
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
// 3. 병렬로 get() 메서드를 사용하여 데이터 읽기
// 286022541
timer.start();
IntStream.range(0, 100_000_000)
.parallel()
.forEach(i -> {
int value = list.get(i); // 병렬로 값을 읽음
});
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
// 4. 직렬로 get() 메서드를 사용하여 데이터 읽기
// 265045709
timer.start();
IntStream.range(0, 100_000_000)
.forEach(i -> {
int value = list.get(i); // 직렬로 값을 읽음
});
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
//
// 5. Iterator를 사용하여 데이터 읽기
// 232946334
timer.start();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
int value = iterator.next(); // Iterator를 사용하여 값을 읽음
}
timer.stop();
System.out.println(timer.getElapsedTimeInNano());
}
}
| 방법 | 시간(나노초) |
| for문으로 읽기 | 161245458 |
| 병렬처리 | 286022541 |
| 직렬처리 | 265045709 |
| Iterator | 232946334 |
결과 : for문 < Iterator < 직렬처리 < 병렬처리
예상외로 기본 for문이 제일 빨랐다..
왜그런지 이번에는 클로드 한테 물어봤다.
기본 for loop: 장점: 간단하고 직관적 단점: ArrayList의 get() 연산이 O(1)이지만 반복적인 메서드 호출 오버헤드 발생 메모리 접근이 순차적이라 캐시 효율은 좋음
Parallel Stream: 장점: 멀티코어 활용으로 처리 속도 향상 가능 단점: 스레드 생성과 관리 오버헤드 ArrayList의 get()이 스레드 안전하지 않음 메모리 접근이 불규칙해져 캐시 효율 저하
Sequential Stream: 장점: 함수형 프로그래밍 스타일 단점: 기본 for loop보다 오버헤드가 큼 내부적으로 Iterator를 사용
Iterator: 장점: 메모리 효율적, 순차적 접근 단점: get() 연산보다는 약간 느림 ArrayList의 경우 내부적으로 최적화된 Iterator 구현 제공
병렬처리가 느렸던것은 아마 데이터가 그렇게 많지 않고, 반복문에서 작업을 많이 안해서 그런듯 하다.
다시한번 느끼지만 ArrayList 잘만들어져 있다.
그러면 다른 것들은 어디에 쓰냐? 이것도 클로드한테 물어봤다.
단순 순차 접근: Iterator나 Enhanced for loop 사용
임의 접근 필요: 기본 for loop 사용
대용량 데이터 병렬 처리: Parallel Stream 고려
가독성 중시: Enhanced for loop 사용
병렬처리가 무조건 좋을줄 알았는데 그건 또 아닌것 같다.
병렬 스트림을 선택할 때 고려할 점:
- 작은 데이터셋에서는 오히려 병렬 스트림이 성능 저하를 일으킬 수 있음.
- 병렬화 작업이 독립적이어야만 효과적 (예: 값의 순서가 중요하지 않고 각 값에 대해 독립적으로 계산할 수 있을 때).
- 멀티코어 시스템에서만 성능 향상이 있음.
또 하나 좋은 지식을 얻어간다
🤔 느낀점
ArrayList를 프로젝트나 알고리즘 문제를 풀때 많이 사용해 봤지만, ArrayList를 절반도 이해하지 못하고 사용하고 있었던 것 같다. 나는 ArrayList는 그냥 동적 배열로만 알 고 있어서 배열과 많은 차이가 있을까? 생각 했지만 이번의 공부를 계기로 다양한 기술들이 들어가 있다는 것을 알게 되었다. 편리하게 다양한 메서드들을 자바에서 제공해주고 있어서 다음에 ArrayList를 사용할때 더욱 즐겁운 코딩이 될 것 같다^^ ArrayList만 해도 이렇게 내용이 많은데 다른 컬렉션 프레임워크도 기대된다 ㅎㅎ
'기본기를 다지자 > 자료구조' 카테고리의 다른 글
| [java] Map (1) | 2025.03.03 |
|---|---|
| [java] Stack (ArrayDeque) (0) | 2025.02.20 |
| [java] Queue (ArrayDeque) (0) | 2025.02.16 |
| [java] LinkedList (0) | 2025.02.14 |
| [java] 배열 (0) | 2025.02.11 |
