List - ArrayList

List

List 는 Collection Framework 의 자료 구조중 하나로, 순서가 있으며, 중복을 허용한다.

 

 

List 특징과 한계점

앞서, 배열은 크기가 정적으로 고정된다. 는 내용을 학습했다.

List는 이러한 한계점을 극복. 크기가 동적으로 변동된다.

public class 내맘대로ArrayList{
	
    private static final int DEFAULT_CAPA = 10;	// 배열의 길이
	private Obejct[] elementData;
    private int size;	// 배열에 담긴 자료 수
   	
    
    private void grow(){
    	/*
        	1. 기존 크기 * 2 배값 구하기
            2. 새로운 배열 생성[2배 크기]
            3. 새로운 배열에 기존 배열 복사
        */
    }
}

단순한 자료 구조인 배열을 멤버로 갖는 ArrayList 클래스를 작성하고, 해당 배열을 컨트롤하는 메서드를 만들어주면 된다.

한 번 만들어두면 계속해서 재사용도 가능하다. (하지만 이미 Collection 에 다 구현 돼 있으니 갖다 쓰면 된다.)

 

ArrayList에 관한 문서를 아주 살짝 뜯어봤을 때, ArrayList는 이렇게 돌아간다.

[배열]

- 처음 용량(배열길이)을 정할 때, 초기값이나, 생성자를 통해 값을 정할 수 있다.

- size 는 배열에 담긴 요소의 숫자를 나타낸다. 동시에, 이후 담길 아이템의 index 값을 뜻하기도 한다.

 

** 참고
int size 의 사용 목적
1. 배열 정보를 쉽게 얻기 위함
동작을 수행할 때, 배열의 정보(몇 개의 자료가 들어있고, 비어있는 위치는 어디인지 등)는 반드시 필요하다.
이 때, 동작을 수행할 때마다 배열의 정보를 알아내는 것은 정말 비효율적이다. 간단한 int 값 하나로, 배열에 대한 정보를 쉽게 얻을 수 있기 때문이다.

2. 다양한 메서드에서 활용하기 위함
인스턴스 필드인 size 는 배열의 크기를 늘리거나, 줄이거나, 추가하는 등 다양한 메서드에서 활용 가능하다. 

 

한계점

ArrayList 는 메서드를 통해 배열의 정적 길이라는 한계점을 극복한다.

그러나, 여전히 배열이 갖는 한계점들을 다수 갖고 있다.

 

앞서, ArrayList 는 순서와 중복이 보장된다고 했다.

즉. 위의 그림에서 알 수 있듯, 데이터의 순서, 인덱스를 통해 마지막에 빠른 데이터의 추가가 가능하다.

 

반면, 처음, 중간 등에 자료를 추가하기 위해선 데이터의 shift()연산이 필요하며, O(n) 작업이 발생하게 된다.

 

정리

ArrayList
순서	보장
중복	허용
데이터 조작
추가
처음	O(n)
중간	O(n/2) -> O(n)
끝	O(1)
제거
처음	O(n)
중간	O(n/2) -> O(n)
끝	O(1)

 

배열에서 마지막에 값을 추가하거나 제거할 때, 굉장히 좋은 성능을 발휘하는 것을 알 수 있었다.

반면, 배열의 중간에서 연산이 발생할 경우, 많은 연산이 발생한다.

이러한 한계점을 극복하는 방법은 없을까?

있다. 다음엔 LinkedList 에 대해 학습 해보자.