면접질문 - ArrayList

면접 예상 질문

질문 1 : ArrayList와 LinkedList 의 차이점은?

ArrayList

• ArrayList는 배열을 기반하기 때문에 각 요소들은 연속적인 메모리 공간에 배치됨
• 따라서, 중간에 요소를 삽입하거나 삭제하는 경우에는 배열의 크기와 요소의 이동이 필수적임

LinkedList

• LinkedList는 연결 리스트를 기반으로 각 요소들은 노드로 구성되고 이전 노드와 다음 노드를 참조함
• 연속적안 메모리 공간이 아니다.
• 따라서, 중간에 요소를 삽입하거나 삭제하는 경우에는 해당 요소를 찾아 (O(n)소요) 그 앞/뒤의 노드의 참조를 변경함 (O(1) 소요)

질문 2 : ArrayList는 내부적으로 어떻게 동작하는가?

• 내부적으로 배열을 사용하여 동작함.
• 고정 크기의 배열이지만 크기가 증가하면 내부 배열의 크기도 자동으로 확장됨
• 배열에 여유 공간이 있는 경우에는 새 요소 추가는 리스트 끝에 추가되며 O(1) 의 시간 복잡도를 가짐
• 배열에 여유 공간이 없을 경우에는 새 배열을 할당하고 기존의 데이터를 새로운 배열로 복사한 뒤에 새 요소를 추가함. 이 과정에서 배열 복사가 이루어지며 O(n)의 시간 복잡도를 가짐
• 인덱스 기반으로 조회 및 삭제를 할 수 있음

질문 3 : ArrayList에서 중간 요소를 삭제할 때 성능이 저하되는 이유는 ?

• 삭제된 요소 이후의 모든 요소들은 한 칸씩 앞으로 밀어야 하는 이유로 성능이 저하됨

질문 4. LinkedList에서 중간에 요소에 추가하는 방법을 설명해주세요.

• 1. 추가하려는 위치의 노드 탐색 O(n)
• 앞 또는 뒤에서부터 순차적으로 노드를 탐색해야 함
• 2. 추가하려는 노드를 생성
• 3. 새로운 노드의 next 포인터를 현재 노드의 next 포인터로 설정
• 4. 이전 노드의 next 포인터를 새로운 노드로 설정