[자료구조] ArrayList가 크기가 가변적인 이유

0.🚶들어가며

 자바에서 배열은 크기가 고정되어있습니다. 코드 작성 시 배열에 들어갈 내용을 전부 알고 있다면 배열의 크기도 예상을 할 수 있을 것입니다. 이러한 환경 속에서는 배열을 사용하는 것이 성능면에서나 메모리면에서나 효율적입니다. 하지만 많은 경우 배열에 얼마만큼의 내용이 들어갈지 전부 파악하기가 어렵습니다.

 

 Java의 Collection 중 ArrayList 클래스는 이러한 문제점을 해결해줍니다. 바로 가변적인 크기의 배열 기능을 제공해주죠. 즉, 배열로 사용하다가 크기가 부족할 시 더 큰 배열로 확장해줍니다. 

 

 이 글은 ArrayList가 어떤 방식으로 가변적인 크기의 배열 기능을 제공해주는 지에 대해 궁금하여 찾아보다 작성하게 되었습니다.

---

1.📖본문

 배열의 크기를 확장하는 코드를 확인하려면 ArrayList 클래스의 어느곳부터 확인해야할까를 고민해봤습니다. 보통 배열의 크기가 부족해지는 경우는 배열에 데이터를 삽입하려할 때 생깁니다. 따라서 ArrayList의 add 메서드를 살펴보았습니다.

 

 

좌측 사진은 add 메서드 인자에 객체만 넘겨줬을 경우입니다. 보통 이렇게 많이 사용하죠.

조금 더 살펴보면 add(e, elementData, size) 라는 메서드를 호출하고 있네요. 이에 대해 알아보겠습니다.

• elementData : elementData는 ArrayList 내부에 저장하고 있는 배열입니다. 여기에 우리가 다루는 객체들이 담겨있습니다. ArrayList도 객체들을 배열로 저장하고 있는 것이죠.
• size : size는 ArrayList 내부의 private 필드입니다. 리스트에 몇 개의 데이터를 저장하고 있는지 정보를 담고 있죠.

 이제 좌측 add 메서드가 호출한 우측 add 메서드를 확인해봅시다. 주의 깊게 보셔야 하는 것은 if문입니다.

if문에서 s == elementData.length 라면 grow() 메서드를 호출하도록 되어있네요. 이 부분이 바로 배열의 크기가 부족할 때 배열을 확장시켜주는 부분입니다. 

 

 그러면 이제 grow() 메서드에 대해 알아보도록 합시다!

 

 

 좌측 사진의 grow() 메서드 return 값을 보면 grow(size + 1)이라는 메서드를 리턴함을 알 수 있네요! 여기서 size라 함은 ArrayList에 들어있는 객체의 개수입니다. (size + 1)이라는 인자가 어떤 역할을 할지 int형 매개 변수가 있는 grow함수를 찾아가 봅시다!

 

 바로 우측 사진입니다. return 값을 보면 Arrays.copyOf 메서드를 사용하는 것을 볼 수 있고 두 번째 인자에 newCapacity(minCapacity)를 넣어준 것을 볼 수 있습니다. 저희 상황에서는 newCapacity(size + 1)이 들어갔겠죠? copyOf 함수는 두 번째 인자 크기만큼 배열을 만든 후 첫 번째 인자에서 받은 배열을 복사해서 넘겨줍니다. 이런 식으로 ArrayList가 꽉 찼을 때 배열 공간을 늘려주는 것을 알 수 있습니다. 

 

 여기서 조금만 더 살펴보겠습니다. 배열 공간을 늘려주기는 하는데 얼마만큼 늘려주는 걸까? 에 대한 궁금증을 해결하기 위해 newCapacity를 따라가 보겠습니다. 

 

 

 newCapacity를 초기화하는 과정을 보면 (이전 배열 크기) + (이전 배열 크기 / 2)인 것을 볼 수 있습니다. 즉 1.5배 정도로 배열의 크기를 확장하는 것입니다. 

 

 결론은 ArrayList의 길이가 가변적일 수 있는 이유는 ArrayList가 꽉 찼을 때 약 1.5배 배열의 크기를 증가시켜주는 로직이 내부에 구현되어 있다라고 낼 수 있을 것 같습니다. 

---

 # 추가로,,

ArrayList가 확장될 때 생기는 오버헤드에 대해 알아보기 위해 천 만개의 데이터를 ArrayList에 넣어 비교해보았습니다.

비교군은 다음과 같습니다.

• 기본 생성자를 사용해 만든 ArrayList와 초기 공간을 설정해준 뒤 만든 ArrayList
• 두 ArrayList에 10,000,000개의 데이터를 삽입해보고 소요된 시간을 비교해보았습니다.\

 

 결과를 보시면 삽입 시간이 5배 이상 차이가 났음을 알 수 있습니다. 공간 확장을 하느라 오버헤드가 생긴 것입니다. 백 만개의 데이터 삽입 경우도 약 2배 정도의 시간 차이가 있는 것을 확인했습니다.

---

2.💨나가며

 오늘은 자바의 ArrayList는 어떻게 크기가 가변적일까에 대해 알아보았습니다. 이런 부분을 공부해두면 ArrayList가 확장될 때 어떤 오버헤드가 존재할 수 있을지 예상할 수 있고 이를 고려해서 코드를 작성해볼 수 있을 것 같습니다. 그리 어렵지 않은 내용이고 많이 쓰이는 내용인 만큼 확인해두면 좋을 것 같습니다.

출처: https://kjhoon0330.tistory.com/entry/Java-ArrayList는-어떻게-크기가-가변적일까 [Jahni's Blog:티스토리]

 

 

 

출처

[Java] ArrayList는 어떻게 크기가 가변적일까? (tistory.com)

[Java] ArrayList는 어떻게 크기가 가변적일까?