[선형 데이터 구조] 배열리스트(ArrayList)

ArrayList 란?

리스트는 배열의 특별한 유형이라고 할 수 있다. 그 중 ArrayList는 배열의 상위호환 버전 정도로 이해하면 된다. 기존의 배열만으로는 자료를 담고 관리하는데 약간 불편함이 있어서 나온 것이 ArrayList 이다.

배열은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조이다.

배열의 이러한 특성은 특정 상황에서 큰 장점이 된다. 예를 들어, 데이터의 크기가 미리 알려져 있고 변하지 않는 경우, 또는 빠른 랜덤 접근이 필요한 경우에 배열은 매우 효과적이다. 그러나 배열의 크기를 변경하기 어렵다는 점은 동적인 데이터 처리에 제한이 될 수 있다.

리스트는 데이터 요소들을 논리적 순서에 따라 저장하여 배열보다 더 유연한 자료구조이다.

ArrayList는 내부적으로 배열을 사용하여 구현되며, 다음과 같은 특징을 가진다.

동적 크기 조정: 필요에 따라 크기를 자동으로 조정할 수 있다.
인덱스 기반 접근: 배열과 마찬가지로 인덱스를 통한 빠른 접근이 가능하다.
삽입/삭제의 비효율성: 중간에 요소를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 한다.

ArrayList의 이러한 특성으로 인해 데이터의 크기가 자주 변하는 경우에 유용하다.

배열과 리스트는 각각의 장단점으로 인해 다양한 알고리즘과 응용 프로그램에서 중요한 역할을 한다. 예를 들어, 배열은 정렬 알고리즘, 행렬 연산, 해시 테이블의 구현 등에 널리 사용된다. 리스트는 스택, 큐, 그래프의 인접 리스트 표현 등에 활용된다.

프로그래밍 언어에 따라 배열과 리스트의 구현과 사용 방법이 다를 수 있다. 예를 들어, C언어에서는 정적 배열과 동적 할당을 통한 배열 사용이 일반적이며, 연결 리스트는 개발자가 직접 구현해야 한다. 반면 Java나 Python과 같은 고수준 언어에서는 동적 배열(ArrayList)과 연결 리스트(LinkedList)를 기본 라이브러리로 제공한다.

배열과 리스트는 각각 고유한 특성과 장단점을 가지고 있어, 상황에 따라 적절히 선택하여 사용하기 위해서는 각 구조의 특성을 잘 이해하고, 문제의 요구사항에 맞게 적절한 구조를 선택해야 한다. 예를 들어, 데이터의 크기가 고정되어 있고 빈번한 검색이 필요한 경우에는 배열이 적합할 수 있다. 반면, 데이터의 크기가 고정되어 있지 않은 경우에는 ArrayList가 더 효율적일 수 있다.

또한, 배열과 리스트는 더 복잡한 자료구조의 기반이 되기도 한다. 예를 들어, 스택과 큐는 배열이나 연결 리스트를 사용하여 구현할 수 있으며, 그래프의 인접 행렬 표현은 2차원 배열을, 인접 리스트 표현은 ArrayList를 사용한다. 따라서 이 두 기본 구조에 대한 깊이 있는 이해는 더 고급 자료구조와 알고리즘을 학습하는 데 필수적이다.

시간복잡도

원소 찾기	O(1)
마지막 노드에 원소 추가/삭제	O(1) or O(N)
마지막 노드 이외의 위치에 원소 추가/삭제하기	O(N)
List의 크기 구하기	O(N)