[자료구조] ArrayList VS LinkedList

 

ArrayList

자바의 java.util 패키지에 포함되어 있는 컬렉션 프레임워크의 일부입니다. 이는 동적 배열의 개념을 구현한 것으로, 배열과 비슷하지만 크기가 자동으로 조정되는 특징을 가지고 있습니다.

 

 

특징

1. 동적 크기 조정: ArrayList는 필요에 따라 크기가 자동으로 조정됩니다. 즉, 요소를 추가하면 ArrayList는 내부적으로 더 큰 크기의 배열을 생성하여 요소를 복사합니다. 이는 고정된 크기를 가진 배열과 대비됩니다.
2. 제네릭 지원: ArrayList는 제네릭을 지원하여, 다양한 타입의 객체를 저장할 수 있습니다. 이를 통해 타입 안정성을 보장하며, 런타임에 타입 캐스팅 오류를 방지할 수 있습니다.
3. 순차 접근 및 무작위 접근: ArrayList는 인덱스를 통한 빠른 무작위 접근을 지원합니다. 하지만 내부 배열의 크기 재조정이 필요한 경우, 성능 저하가 발생할 수 있습니다.
4. API 메소드: ArrayList는 add(), remove(), get(), size() 등 다양한 메소드를 제공하여, 리스트의 관리를 용이하게 합니다.

**Static Array의 한계**

데이터 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적입니다. 하지만 선언 시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있습니다. 그렇다고 매번 크기가 엄청 큰 배열은 선언한다면 그만큼 메모리 비효율이 발생하게 됩니다. 이런 문제점을 해결할 수 있는 것이 바로 Dynamic Array입니다.

 

**Dynamic Array**

동적 배열은 데이터 구조의 일종으로, 고정된 크기를 가진 일반 배열의 한계를 극복하기 위해 고안되었습니다. 동적 배열은 배열의 크기를 자동으로 조정할 수 있는 능력이 있어, 프로그램 실행 중에도 저장 공간의 크기를 동적으로 변경할 수 있습니다.

 

*특징

1. 자동 크기 조정: 동적 배열은 요소가 추가될 때 내부적으로 더 많은 요소를 저장할 수 있도록 크기를 자동으로 조절합니다. 이는 일반적으로 기존 배열보다 더 큰 새로운 배열을 생성(reSize)하고, 기존 요소들을 새 배열로 복사하는 방식으로 이루어집니다.

2. 효율적인 메모리 사용: 초기에 작은 크기로 시작하여 필요에 따라 크기를 조정함으로써, 고정된 크기의 배열에서 발생할 수 있는 메모리 낭비를 줄일 수 있습니다.

3. 접근성: 동적 배열은 인덱스를 통해 빠른 접근이 가능합니다. 특정 위치의 요소에 접근하거나 수정하는 데 걸리는 시간은 일반적으로 상수 시간(O(1))입니다.

 

*작동 원리

동적 배열은 초기에 설정된 특정 용량을 가지고 시작합니다. 요소가 추가되어 이 용량을 초과하는 경우, 동적 배열은 보통 현재 용량의 1.5배에서 2배 사이로 새로운 배열의 크기를 증가시킵니다. 새로운 크기의 배열이 생성되고, 기존 요소들이 새 배열로 복사된 다음, 추가된 요소가 삽입됩니다. 이 과정은 자동으로 이루어지므로 사용자는 배열의 크기를 신경 쓸 필요가 없습니다.

시간 복잡도

1. 임의 접근(Random Access): get(int index)와 같은 메소드로 특정 인덱스의 요소에 접근하는 경우, 시간 복잡도는 O(1)입니다. 이는 내부 배열의 인덱스를 통해 직접 접근하기 때문에 발생하는 성능입니다.
2. 끝에 추가/삭제(Addition/Removal at the End): add(E element) 메소드로 리스트의 끝에 요소를 추가하는 경우, 일반적으로 시간 복잡도는 O(1)입니다. 하지만 내부 배열의 크기를 조정해야 할 때(즉, 현재 배열이 가득 찼을 때)는 새로운 배열을 생성하고 기존 요소들을 복사해야 하므로, 그 경우에는 O(n)의 시간이 걸립니다. 그러나 이는 평균적으로 분할 상환 시간 복잡도(amortized time complexity)가 O(1)이 됩니다. remove(int index) 메소드로 리스트의 끝 요소를 삭제하는 경우도 마찬가지입니다.
3. 중간에 추가/삭제(Addition/Removal in the Middle): 리스트의 중간에 요소를 추가하거나 삭제하는 경우, 해당 요소 뒤의 모든 요소들을 이동시켜야 하므로 시간 복잡도는 O(n)입니다. 여기서 n은 리스트의 크기입니다.

 

LinkedList

LinkedList는 데이터를 순차적으로 저장하지만, 내부적으로는 각 요소가 다음 또는 이전 요소를 가리키는 포인터(또는 참조)를 통해 서로 연결된 데이터 구조입니다. 삽입과 삭제가 빈번하고, 크기가 미리 예측되지 않거나 변동이 큰 경우에 적합한 데이터 구조입니다. 반면, 임의 접근이나 인덱스를 통한 빠른 접근이 주된 작업인 경우에는 ArrayList가 더 효율적일 수 있습니다.

 

특징

1. 동적 구조: LinkedList는 필요에 따라 메모리를 동적으로 할당하여 요소를 추가하거나 제거할 수 있습니다. 이는 배열과 달리 크기가 고정되지 않았음을 의미합니다.
2. 삽입 및 삭제 효율성: LinkedList는 특정 위치에 있는 요소의 삽입 또는 삭제시 해당 노드의 이전 노드와 다음 노드만을 연결하거나 끊으면 되기 때문에, 이 작업의 시간 복잡도는 O(1)입니다. 다만, 특정 위치를 찾기 위해서는 처음부터 해당 위치까지 순회해야 하므로 최악의 경우 O(n)의 시간이 소요될 수 있습니다.
3. 순차 접근: LinkedList는 인덱스를 통한 빠른 임의 접근(Random Access)이 불가능하며, 특정 요소에 접근하기 위해서는 앞에서부터 순차적으로 탐색해야 합니다. 따라서 임의 접근이 필요한 경우에는 ArrayList에 비해 비효율적일 수 있습니다.
4. 메모리 오버헤드: 각 요소는 데이터와 함꼐 다음 노드(또는 이전 노드)를 가리키는 추가적인 포인터 정보를 저장해야 하므로, LinkedList는 ArrayList보다 더 많은 메모리를 사용할 수 있습니다.
5. 양방향 탐색: 일반적인 LinkedList는 단방향으로만 연결되어 있지만, Java의 LinkedList와 같은 일부 구현체는 양방향 연결 리스트를 사용하여 양방향 모두에서 탐색을 지원합니다.

시간 복잡도

1. 접근(Access): 특정 인덱스의 원소에 접근하는 데 O(n)의 시간이 걸립니다. LinkedList는 인덱스를 통한 직접 접근이 불가능하므로, 원하는 위치까지 순차적으로 탐색해야 합니다.
2. 삽입(insertion): 리스트의 시작이나 끝, 중간에 원소를 삽입하는 데 평균적으로 O(1) (리스트의 시작이나 끝에 삽입할 경우) 또는 O(n) (중간에 삽입할 경우)의 시간이 걸립니다. 특정 위치에 삽입하기 위해서는 그 위치를 찾기 위해 탐색을 해야 하므로, 최악의 경우 O(n)의 시간이 소요됩니다.
3. 삭제(Deletion): 리스트의 시작이나 끝, 또는 중간에서 원소를 삭제하는 데 평균적으로 O(1) (리스트의 시작이나 끝에서 삭제할 경우) 또는 O(n) (중간에서 삭제할 경우)의 시간이 걸립니다. 삭제하고자 하는 원소를 찾기 위해 탐색하는 시간이 포함되기 때문입니다.
4. 탐색(Search): 특정 값이나 조건을 만족하는 원소를 찾는 데 O(n)의 시간이 걸립니다. LinkedList의 모든 원소를 순차적으로 확인해야 하므로, 리스트의 길이에 비례하는 시간이 소요됩니다.

 

 

결론적으로, ArrayList는 요소에 대한 빠른 접근(인덱스를 통한 접근)이 필요할 때 유리합니다. 따라서, 리스트의 크기가 자주 변경되지 않고, 데이터를 읽는 작업이 주된 작업인 경우에 적합합니다. LinkedList는 데이터의 추가나 제거가 빈번히 일어나는 경우에 유리합니다. 특히, 리스트의 시작 부분이나 특정 위치에 대한 추가 및 제거 작업이 주된 작업인 경우에 적합합니다.

 

 

오늘은 ArrayList와 LinkedList에 대해서 알아보았습니다.

CS 기술 관련된 면접 질문&답변도 많은 도움이 되니 함께 보시면 좋아요!

2024.04.09 - [IT] - [기술 면접] CS 기술 면접 질문&답변

[기술 면접] CS 기술 면접 질문&답변