[자료구조/Java] ArrayList

이전에 정적배열 Array에 대해 포스팅을 했었습니다. 이때, 정적배열의 단점은 최초에 선언한 사이즈를 나중에 변경이 불가능하다는 것이었죠.

이를 기억하면서 동적 배열을 알아보도록 하겠습니다.

 

 

동적배열 Dynamic Array

동적배열은 정적배열과 달리 배열의 크기가 가변적입니다. 다시 말해, 공간이 더 필요하면 늘릴 수 있다는 겁니다.

크기가 가변적인 동적배열은 여러 종류가 존재하지만, 대표적으로 ArrayList와 LinkedList가 존재합니다.

 

 

 

 

ArrayList

ArrayList는 배열을 동적으로 변화시키는 자료구조로써, List 인터페이스를 구현한 클래스입니다.

ArrayList의 선언과 사용

ArrayList<Character> arr = new ArrayList<>();

ArrayList를 사용하기 위해 ArrayList<타입> 변수명 = new ArrayList<>()의 형식으로 선언합니다.

⚙️컬렉션에서는 primitive 타입을 사용할 수 없다.
켈렉션에서는 변수의 타입이 사용자의 필요에 따라 정해짐으로, 일반(Generic)타입으로 설계되어 있다. 따라서 Integer, Double과 같은 Wrapper 클래스 객체를 사용해야만 한다.

기본적으로 메모리 상에서는 객체를 담을 수 있는 크기가 10인 배열이 생성됩니다. 데이터를 추가하게 되면 0번 인덱스부터 추가되며, 10을 초과하면 용량이 자동으로 증가됩니다.

 

 

ArrayList의 데이터 추가 및 삭제

ArrayList에서 중간 원소를 제거하게 되면, 제거된 원소의 뒷 원소들을 쉬프트(shift)하게 됩니다. 또한, 중간에 원소가 추가되면, 추가된 위치 뒤의 원소들이 모두 n번만큼 쉬프트(shift)하게 됩니다. 따라서 최악의 경우, 추가 또는 삭제에 O(n)만큼의 시간이 걸리게 되는거죠.

맨 마지막에 객체를 추가하는 경우, 그리고 인덱스를 이용해서 데이터를 탐색하는 일이 잦은 경우엔 적합한 자료구조입니다.