자바 ArrayList 구현

bbangho·2023년 5월 2일

java Collections Framework

목록 보기

3/9

첫번째 시간에 만든 List interface를 구현하는 방법으로 진행할 것이다.
java에서 제공하고 있는 ArrayList는 추가된 기능이 너무나도 많다. 그래서 최소한의 필수적인 메소드와 전체적인 구조를 살펴보기 위한 목적으로 글을 쓸것이다.

ArrayList

컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스일 것이다.
List는 데이터의 저장순서가 유지되고 중복을 허용한다.

ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다.
Vector는 호환성을 위해 남겨두었다. (IPv6 라우터에 IPv4기능을 넣는것 처럼 Daul Stack 컴퓨터공학을 배우면서 개념들이 일맥상통한다)

null값을 들어가는 것을 방지하기위해 List를 선언할 때 관례로 새로운 ArrayList를 넣는다고 한다.
List a = new ArrayList();

ArrayList는 Object[] 배열을 두고 사용한다. 또한 모든 자료구조는 '동적 할당' 을 전제로 한다.

데이터의 개수를 알 수 없는데 배열을 쓰고 싶다면 이러한 자료구조를 선택하면 된다.

그리고 리스트 계열 자료구조는 데이터 사이에 빈 공간을 허락하지 않는다.

구현

<필수 목록>

클래스 및 생성자 구성
resize 메소드 구현
add 메소드 구현
get, set, indexOf, contains 메소드 구현
remove 메소드 구현
size, isEmpty, clear 메소드 구현

클래스 및 생성자 구성

import interface_form.List;


public class ArrayList<E> implements List<E>{
    private static final int DEFAULT_CAPACITY = 10; // 최소 용적 크기
    private static final Object[] EMPTY_ARRAY = {};

    private int size; // element 수

    Object[] array; // element 담을 배열

    // 생성자 1 (초기 공간 할당 X)
    public ArrayList(){
        this.array = EMPTY_ARRAY;
        this.size = 0;
    }

    // 생성자 2 (초기 공간 할당)
    public ArrayList(int capacity){
        this.array = new Object[capacity];
        this.size = 0;
    }
}

DEFAULT_CAPACITY : 최소 용적 크기이다.
EMPTY_ARRAY : 빈 배열을 선언해 두었다. 초기 공간을 할당하지 않았을 경우 사용하게된다.
size : element 수이다.
array : element 담을 배열이다.

확실히 해두고 갈 것은 size가 가르키는 의미이다.
element를 넣고 뺄때 헷갈릴 수 있다.

생성자들은 초기에 공간을 할당한것과 공간을 할당하지 않은것 두개로 나누었다.

resize 메소드 구현

 private void resize(){
        // 용적
        int array_capacity = array.length;

        // array capacity가 0인경우
        if(Arrays.equals(array, EMPTY_ARRAY)){
            array = new Object[DEFAULT_CAPACITY];
            return;
        }

        // 용량이 꽉 찰 경우
        if(size == array_capacity){
            array = Arrays.copyOf(array, array_capacity * 2);
            return;
        }


        // 용량의 절반 미만으로 element가 차지하고 있을 경우 최적화를 해보자
        if(size < (array_capacity/ 2)){
            array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, array_capacity/2));
            return;
        }
    }

모든 자료구조는 동적할당이 된다는 것을 기억하는가?
그것을 위한 용적크기를 재조정하는 함수이다. 용적이 더 필요하다면 배열의 크기를 늘려주고 용적에 비해 들어 요소가 적다면 크기를 절반으로 줄여준다.

array capacity가 0일경우
용량이 꽉 찰 경우
용량의 절반 미만으로 element가 차지하고 있을 경우

add 메소드 구현

위의 그림은 java 공식문서의 ArrayList의 Method Summary를 가져온 것이다. 둘다 add 라고 간략하게 나와있지만 Insert와 Append 미묘한 차이가 보이는가??

List 인터페이스에서 add의 의미는 끝에 value를 추가하는것이다.

	@Override
    public boolean add(E value){
        addLast(value);
        return true;
    }
    
    @Override
    public void add(int index, E element) {
        // 영역을 벗어날 경우 예외 발생
        if(index > size || index < 0){
            throw new IndexOutOfBoundsException();
        }
        //인덱스랑 사이즈와 같다면
        if(index == size){
            addLast(element);
        }
        else{

            // 체크1 꽉차있는지
            if(size == array.length){
                resize();
            }

            //index기준으로 뒤에 있는 요소들 한칸씩 뒤로 밀기.
            for(int i = size; i > index; i--){
                array[i] = array[i-1];
            }

            array[index] = element;
            size++;
        }
    }
    
    public void addFirst(E value){
        add(0, value);
    }

    
    public void addLast(E value){
        if(size == array.length){
            resize();
        }

        array[size++] = value;
        // 넣고 올린다.
    }

addFrist , addLast는 모두 index를 이용한 add로 구현할 수 있다.

중간에 삽입해야 할 경우 index 위치부터 끝까지 뒤로 한칸씩 밀어야하고 중요한것은 뒤에서부터 한칸씩 가져가야 한다는 것이다.

get, set, indexOf, contains 메소드 구현

	@Override
    public E get(int index) {
        if(index >= size || index < 0){
            throw new IndexOutOfBoundsException();
        }

        return (E) array[index];
    }
    
    @Override
    public E set(int index, E value) {
        if(index >= size || index < 0){
            throw new IndexOutOfBoundsException();
        }
        E rv = get(index);
        array[index] = value;
        return rv;
    }
    
    @Override
    public boolean contains(Object value) {
        if(indexof(value) > -1){
            return true;
        }
        return false;
    }

    @Override
    public int indexof(Object value) {
        for(int i = 0; i < size; i++){
            if(array[i].equals(value)){
                return i;
            }
        }
        return -1;
    }

코드를 보면 이해가 될것이다.

remove 메소드 구현

remove 메소드는 생각해야 할 것이 있다. 삭제해야 할 것이 마지막 인덱스에 있다면 삭제하고 끝날것이다. 하지만 삭제해야 할 것이 중간에 있다면 list인터페이스를 구현한 자료구조들은 중간에 빈공간을 허용하지 않아서 자리를 한칸씩 움직여야 한다.

	@Override
   public E remove(int index) {
       if(index > size || index < 0){
           throw new IndexOutOfBoundsException();
       }

       E r = (E) array[index];
       array[index] = null;

       for(int i = index + 1; i < size; i++){
           array[i -1] = array[i];
           array[i] = null;
       }
       size--;
       resize();
       return r;


   }

   @Override
   public boolean remove(Object value) {
       int index = indexof(value);

       if(index == -1){
           return false;
       }

       remove(index);
       return true;
   }

한칸씩 당겨주는 작업을 한 것이다. 천천히 읽어보면 이해가 될것이다.

size, isEmpty, clear 메소드 구현

	@Override
   public int size() {
       return size;
   }
   
   @Override
   public boolean isEmpty() {
       return size == 0;
   }
   
    @Override
   public void clear() {
       for(int i = 0; i < size; i++){
           array[i] = null;
       }
       size = 0;
       resize();
   }