ArrayList vs LinkedList vs Array

각 자료구조의 구현 및 저장 방식

Arrray

기본 배열 자료구조로, 고정된 크기의 연속된 메모리 공간에 요소를 저장합니다.

크기가 변경되지 않습니다.

ArrayList

내부적으로 배열을 사용하여 요소를 저장합니다.

배열은 고정된 크기를 가지며, 요소를 추가할 때 배열 크기를 늘리는 작업이 필요할 때 재할당 됩니다.

내부적으로 배열을 사용하므로, 연속된 메모리 공간에 요소를 저장합니다.

LinkedList

노드 간의 링크를 사용하여 요소를 저장합니다.

각 노드는 자신의 데이터와 다음 노드를 참조하는 링크를 가지고 있습니다.

각 노드가 독립적인 메모리 공간을 가집니다.

각 자료구조의 장단점

Array

• 장점 : 크기가 고정되어 있어 메모리 관리가 쉽고, 인덱스 접근이 빠릅니다.
• 단점 : 크기가 한정되어 있고, 삽입 및 삭제에 제약이 있습니다.

ArrayList

• 장점 : 빠른 인덱스 기반 접근과 탐색이 가능합니다.
• 단점 : 삽입 및 삭제 시 재할당과 복사 작업이 필요하며 비효율적일 수 있습니다.

LinkedList

• 장점 : 삽입 및 삭제 작업이 배열보다 효율적 입니다.
• 단점 : 인덱스 접근이 느리며, 각 노드의 메모리 오버헤드가 있을 수 있습니다.

각 자료구조 핸들링 시간 복잡도

Arrary

• 삽입/삭제(중간, 마지막) : O(N)
• 탐색 : O(1)

ArrayList

• 삽입/삭제(첫번째 제외) : O(N)
• 탐색(인덱스 접근) : O(1)

LinkedList

• 삽입/삭제(첫번째 포함) : O(1)
• 탐색 : O(n)

ArrayList의 탐색은 LinkedList에 비해 왜 빠른가?

ArrayList는 내부적으로 배열로 구성되어 있기 때문에, 인덱스 기반의 데이터 접근이 빠릅니다. 즉, 인덱스로 직접 해당 위치의 값을 찾아오기 때문입니다.

반면 LinkedList는 링크를 따라가며 탐색해야 하므로 인덱스 접근이 느립니다.

어떤 상황에서 어떤 자료구조를 사용해야할까?

Array

• 크기가 고정되어야 하거나 크기 변경이 적은 경우
• 요소 접근이 빈번하며 크기가 작은 경우

ArrayList

• 요소 접근이 빈번한 경우
• 크기 변경이 드물거나 미리 예측 가능한 경우

LinkedList

• 삽입/삭제가 빈번한 경우
• 삽입/삭제가 리스트 중간에 이루어질 때

각 자료구조 별 성능 향상 법

Array

크기가 고정적이기 때문에 크기 변경이 필요한 경우 새로운 배열을 생성하고 기존 데이터를 복사해야 합니다.

따라서 크기 변경이 빈번한 경우 ArrayList나 LinkedList를 고려해야 합니다.

ArrayList

초기에 적절한 크기로 생성하면 재할당 횟수를 줄일 수 있습니다.

요소를 삭제할 때, 대신에 해당 위치의 요소를 null로 설정하여 메모리 누수를 방지할 수 있습니다.

LinkedList

맨 앞이나 맨 뒤에 삽입/삭제할 때는 빠르지만, 리스트 중간에서는 검색이 필요하므로 가능하면 양 끝에서 작업하는 것이 좋습니다.

ArrayList의 자세한 내부 구현 방식

ArrayList는 내부적으로 배열을 사용하여 요소를 저장합니다.

배열의 크기는 초기에 작은 값으로 시작하며, 요소를 추가할 때마다 배열의 크기가 늘어나는 동적 배열(dynamic array)의 형태를 가지고 있습니다.

기본적으로 ArrayList는 초기 크기를 10으로 설정하며, 요소를 추가할 때마다 크기를 늘릴때 약 1.5배 정도로 크기를 늘립니다.

크기를 늘릴 때는 새로운 배열을 더 큰 크기로 생성하고, 기존 데이터를 새 배열로 복사합니다. 이후로는 새로운 배열에 추가적인 요소를 저장하게 됩니다.

즉, 배열의 크기를 동적으로 조절하면서 데이터를 관리하는게 핵심 동작 원리입니다.

ArrrayList의 메모리 공간 낭비 극단적인 예시

1. ArrayList 할당, 기본 크기는 10
2. 10개의 데이터를 추가 후, 1개의 데이터를 추가로 넣으면 크기가 늘어난다.
3. 데이터를 1개 삭제한다.

데이터를 삭제해도 배열의 크기는 줄지 않는다. 따라서 10개의 데이터가 남아있지만, 배열 크기는 여전히 늘어난 크기를 유지한다.

즉, 위의 이유로 인해 메모리 공간이 낭비될 수 있습니다.

불필요한 메모리 공간 해결 방법

• trimToSize() : 이 메서드를 호출하면, 현재 요소의 수에 맞게 배열 크기를 조정할 수 있습니다. 하지만 내부적으로 다시 배열 생성 후 복사하는 과정을 거치므로 O(N) 시간 복잡도가 발생합니다.