#.2 ArrayList

자료구조

Haksae 2022. 3. 9. 04:10

ArrayList(배열)

*Array와 ArrayList는 거의 비슷하나 약간의 차이가 있다. 가장 큰 차이점은 길이를 조정할 수 있는가이다.
Array는 고정 길이지만, ArrayList는 가변 길이이다.

가장 기본적인 자료구조로서, 같은 자료형의 변수들을 모아서데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
컴퓨터의 실제 메모리 공간을 연속적으로 사용하기에, 컴퓨터가 연산을 하기 쉬운 구조를 가지고 있음. (논리적 저장 순서와 물리적 저장 순서가 일치한다.)

장점
- 검색 속도가 그 어떤 자료구조보다 빠르다
  - 인덱스를 통한 데이터 접근은 Random Access 방식
  - 시간 복잡도 O(1)
- 캐시 히트의 가능성이 높다. (데이터가 군집되어 있기 때문)
단점
- 한번 고정적으로 선언된 배열은 크기 변경이 어렵다. (정적 언어에서는 배열의 크기 변경이 자유롭지만, 원래는 까다롭다)
- 데이터의 삽입과 삭제가 느리다.
  - 데이터를 삭제하면 공백을 없애기 위하여, 다른 데이터들이 이동해야한다.
  - 시간 복잡도는 O(N)

참고자료