Java에서 배열(Array), ArrayList, LinkedList는 자주 사용되는 기본 자료구조입니다. 면접에서 이들 자료구조의 특징과 차이점을 묻는 질문은 매우 흔하기 때문에, 각 자료구조가 어떤 상황에서 유리한지, 성능 차이가 어떻게 나는지에 대한 이해는 중요합니다. 이번 포스트에서는 자료구조의 기능, 장단점, 사용할 때의 고려사항을 중심으로 설명해 보겠습니다.

1. Array(배열)

배열은 고정 크기의 순차적 자료구조로, 메모리 상에서 연속된 공간에 데이터를 저장합니다. 데이터에 접근할 때 인덱스를 사용하여 빠르게 접근할 수 있습니다.

장점

• 빠른 인덱스 접근: 배열은 데이터가 연속된 메모리 공간에 저장되므로 인덱스를 통해 빠르게 접근할 수 있습니다. O(1)의 시간 복잡도로 데이터를 접근 할 수 있습니다.
• 고정 크기: 배열의 크기가 고정되어 메모리 할당이 효율적입니다.

단점

• 고정 크기: 배열은 한 번 크기를 지정하면 더 이상 크기를 변경할 수 없습니다. 크기를 변경하려면 새 배열을 할당하고 기존 데이터를 복사해야 하므로, 데이터 크기가 변동하는 경우 불편합니다.
• 중간 삽입/삭제 비효율적: 배열의 중간에 데이터를 삽입하거나 삭제할 경우, 다른 요소들을 밀어야 하므로 시간 복잡도가 O(N)이 됩니다.

사용하면 좋은 경우

데이터의 크기가 고정적이고, 순차적으로 저장해야 하는 데이터에 적합합니다. 예를 들어, 주식 차트나 날짜별 데이터에 적합합니다.

2. ArrayList

ArrayList는 동적 배열 기반의 자료구조입니다. 배열과 달리 크기가 자동으로 증가하여 데이터를 유연하게 처리할 수 있습니다.

장점

• 가변 크기: ArrayList는 데이터가 추가되면 자동으로 크기를 증가시킬 수 있어 크기가 동적으로 변하는 데이터에 유리합니다.
• 빠른 인덱스 접근: 배열처럼 인덱스를 사용하여 O(1)로 데이터를 빠르게 접근할 수 있습니다.
• 자동 리사이징: ArrayList는 내부적으로 크기가 부족하면 자동으로 크기를 1.5배씩 증가시켜 리사이징합니다.

단점

• 리사이징 비용: ArrayList의 크기가 초과하면 새로운 배열을 할당하고 기존 데이터를 복사하는 과정에서 O(N)의 시간 복잡도가 발생합니다.
• 원시 자료형 저장 불가: ArrayList는 객체만 저장할 수 있으므로, 원시 자료형(int, char 등)은 자동 박싱을 통해 객체로 변환되어 저장됩니다. 이로 인해 약간의 성능 저하가 발생할 수 있습니다.

사용하면 좋은 경우

• 데이터 크기가 동적으로 변하는 경우 사용됩니다. 예를 들어, 사용자 리스트나 데이터가 자주 추가되는 경우에 적합합니다.

3. LinkedList (연결 리스트)

LinkedList는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 자료구조입니다. 데이터가 연속된 메모리 공간에 저장되지 않으며, 각 노드가 독립적으로 연결됩니다.

장점

• 빠른 삽입/삭제: O(1)의 시간 복잡도로 중간에 데이터를 삽입하거나 삭제 할 수 있습니다. 삽입 시 노드 간 연결만 수정하면 되기 때문에 빠릅니다.
• 동적 크기: 데이터를 추가할 때마다 새로운 노드를 생성하므로 크기가 자동으로 변합니다.

단점

• 검색 비효율적: 배열처럼 인덱스를 이용한 직접적인 접근이 불가능하여, 특징 값을 찾기 위해 O(N) 시간이 소요됩니다.
• 메모리 오버헤드: 각 노드는 데이터와 함께 포인터를 저장해야 하므로 배열에 비해 메모리 사용량이 많습니다.

사용하면 좋은 경우

• 중간 삽입/삭제가 자주 발생하는 경우, 데이터 크기가 예측되지 않거나 동적으로 변경되는 경우에 적합합니다. 예를 들어, 데이터베이스의 레코드 처리나 작은 크기의 데이터 관리에 적합합니다.

4. Array와 LinkedList의 차이

Array

• Array는 순서가 있는 선형 자료구조이며, 고정 길이의 크기를 가진 자료구조입니다.
• 순서를 의미하는 index가 존재합니다. (O(1)의 시간복잡도가 소요)
• 삽입/삭제에 대해선, 모두 한 칸씩 밀거나 당겨야 하므로 O(N)의 시간복잡도가 소요)

LinkedList

• Array의 고정길이, 느린 삽입/삭제 연산을 해결하기 위해 나온 자료구조입니다.
• 데이터를 저장하고있는 각 노드를 연결시켜 만든 선형 자료구조이며, 가변 길이의 크기를 가집니다.
• 삽입/삭제하는 과정에서 기존의 연결을 끊고, 새로운 연결을 맺는 과정만 하면 되므로 O(1)의 시간복잡도를 가집니다.