[Java] ArrayList

기술 면접을 대비해
Java의 자료구조와 관련된 질문과 답을
꼬리 질문 형태로 작성한 글입니다.

 

 

Q. ArrayList 내부 동작 원리에 대해 설명해주세요. 해당 동작 원리를 알면 ArrayList를 사용할 때 어떤 점에 주의해야 하는지 알 수 있습니다.

 

A : ArrayList는 배열과 같은 원리로 동작합니다.  데이터를 조회할땐 시간복잡도가 O(1)이지만, 데이터를 삽입 삭제하는 경우 최악일때 O(n)이 됩니다.

 

피드백

답변에 대한 평가 60점

평가 이유 : 답변은 ArrayList의 일반적인 동작 방식을 어느 정도 이해하고 있지만, 좀 더 세부적인 동작 원리에 대해 설명이 필요합니다. 실제로 ArrayList는 내부적으로 배열을 이용하지만, 배열크기를 조절하거나 삽입/삭제 시에는 어떤 과정을 거치는지 더 알아보는 것이 좋습니다.

추천 검색 키워드 : Java ArrayList internal workings, ArrayList resizing

 

Q. ArrayList에서 데이터를 삽입할 때, 배열 크기가 조절되는 과정은 어떻게 이루어지나요? 그리고, 데이터를 삭제할 때에는 어떤 과정이 일어나는지 설명해주세요.

 

A : ArrayList에 데이터를 삽일할 때, 인덱스를 전달받은 경우, ArrayList의 크기를 한칸 늘 린 후, 한칸씩 앞으로 값을 옮겨주는 작업을 하고, 지정해 놓은 인덱스에 값을 삽입해 줍니다. 인덱스를 전달받지 않은 경우엔, ArrayList 크기를 한 칸 늘린 후, 값을 추가합니다. 

데이터를 삭제하는 과정은 주어진 인덱스의 값을 제거한 후, 만약 인덱스가 중간에 위치한다면 빈칸을 매꾸기 위해 한칸씩 땡겨주고, 맨 뒤인 경우에는 그냥 바로 삭제해줍니다. ArrayList는 값을 추가 삭제함에 따라 유동적으로 배열 크기를 조절해줍니다.

 

피드백

답변에 대한 평가 : 70점
평가 이유 : 답변에는 ArrayList에서 데이터를 삽입하고 삭제하는 일반적인 과정에 대해 언급했지만, 좀 더 자세한 내부 동작 원리에 대한 설명이 필요합니다. 실제로 ArrayList는 데이터를 추가/삭제하는 과정에서 배열의 크기를 동적으로 조절하며, 이 때 몇 가지 최적화 과정이 수행됩니다.
추천 검색 키워드 : Java ArrayList add operation, ArrayList remove operation, dynamic array resizing

 

Q. ArrayList에서 데이터를 추가할 때 배열 크기를 조절하는 최적화 방법에는 어떤 것들이 있고, 이를 효율적으로 수행하기 위해 어떤 전략을 사용해야 할까요? 또한, 데이터를 삭제할 때 공간을 채우는 과정에서 발생하는 오버헤드를 최소화하기 위해 어떤 방법을 사용해야 할까요?

 

A : 먼저 ArrayList에서 데이터를 추가할 때 배열 크기를 조절하는 최적화된 방법으로는 내부적으로 동적 배열을 사용하여 데이터를 추가할 때 크기가 부족하면 배열 크기를 n배로 확장합니다. 초기에 오버헤드를 줄이기 위해서 데이터의 예상 크기를 아는 경우엔 초기 용량을 지정하거나 ensureCapacity() 메서드를 사용해 미리 배열 크기를 늘리는 방식이 있습니다. 데이터 삭제시 공간을 채우는 과정에서 발생하는 오버헤드를 최소화하기 위해 사용하는 방법으로는 반복 삭제보다는 범위를 지정해 한 번에 삭제하거나, 삽입/삭제가 빈번한 상황에서는 LinkedList로의 전환을 고려할 수 있습니다.

 

피드백

답변에 대한 평가 : 90점
평가 이유 : 답변에는 ArrayList에서 데이터를 추가할 때 배열 크기를 조절하는 최적화된 방법과 데이터 삭제시 공간을 채우는 과정에서 발생하는 오버헤드를 최소화하기 위한 방법에 대해 상세히 설명했습니다. 또한, 초기 용량 설정과 ensureCapacity() 메서드의 활용, 그리고 LinkedList로의 전환을 언급하여 ArrayList의 최적화에 대해 잘 이해하고 있는 것으로 보입니다.
검색 키워드 : Java ArrayList optimization, ArrayList initial capacity, ArrayList ensureCapacity(), ArrayList to LinkedList conversion

 

Q. ArrayList에서 배열 크기를 조절할 때 n배로 확장하는 이율은 어떻게 결정되나요? 그리고, 반복적인 삽입/삭제 작업이 필요한 경우에 LinkedList 대신에 어떤 자료구조를 고려할 수 있을까요?

 

A: 기본적으로 Java 8버전 부터는 1.5배를 채택해서 하고 있습니다. 이는 자바의 기본 구현에서 성능과 메모리 사용 간의 균형을 맞추기 위한 최적의 값으로 설정되었습니다. 반복적인 삽입/삭제 작업이 필요한 경우에는 LinkedList가 적합하다고 생각하지만, 양 끝에서 삽입/삭제가 일어날 경우엔 ArrayDeque가 더 효율적일 수 있다고 생각합니다. 특히 ArrayDeque는 순환 배열 기반으로 동작하기 때문에 LinkedList보다 캐시 성능(메모리 연속성)이 뛰어나고, 메모리 오버헤드가 적습니다.

 

피드백

답변에 대한 평가 : 100점
평가 이유 : Java ArrayList에서 배열 크기를 조절할 때 n배로 확장하는 이율이 Java 8 이후에는 1.5배로 설정되었으며, LinkedList와 ArrayDeque의 활용에 대해 잘 설명했습니다. ArrayDeque가 LinkedList보다 캐시 성능이 우수하고 메모리 오버헤드가 적다는 내용도 정확하게 설명했습니다. 이에 대한 깊은 이해를 보여주는 좋은 답변입니다.
검색 키워드 : Java ArrayList resizing factor, LinkedList vs ArrayDeque, ArrayDeque cache performance

 

 

순환 배열의 장점

 

• 캐시 성능: ArrayDeque는 배열 기반으로 동작하기 때문에, 메모리의 연속성을 유지하여 캐시 효율이 높습니다. (LinkedList는 각 노드가 메모리의 여기저기 흩어져 있어 캐시 효율이 떨어질 수 있음.)
• O(1) 시간 복잡도: 삽입/삭제가 끝이나 시작에서 이루어질 때, 배열을 이동하거나 재배열하지 않아도 되므로 성능이 빠릅니다.
• 메모리 효율성: 순환 구조를 통해 빈 공간을 재사용하므로 추가적인 메모리 낭비를 줄입니다.