자바[JAVA] 자료구조 구현 2 - ArrayList

ArrayList

 

ArrayList 는 List Interface 를 implements 하는 클래스입니다. 하지만 다른 List 자료구조들과 달리 배열에 기반을 두고 사용합니다.(다른 자료구조들은 주소를 통해 구현됩니다.)

 

또한 모든 자료구조는 '동적 할당' 을 전제로 합니다. 만약 ArrayList 를 사용하는데 리스트가 꽉찼다면 리스트의 길이를 늘려줘야 합니다. 이때 크기는 현재 크기의 2배씩 늘립니다.

 

 

ArrayList 구현 메소드

 

2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 1 - List Interface

에서 구현한 메소드들을 포함하여

toArray() 와 clone() 을 추가해서 작성했습니다.

해당 메소드들에 대한 설명은 코드 주석으로 작성했습니다. 

 

 

 

ArrayList 구현

import Interfaces.List;
import java.lang.Object;
import java.util.Arrays;

public class ArrayList<E> implements List<E> , Cloneable{

    private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
    private static final Object[] EMPTY_ARRAY = {}; // 빈 배열

    private int size; // 요소 개수

    Object[] array; // 요소를 담을 배열

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

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

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

        // if array's capacity is 0
        // set the array to the new array have DEFAULT_CAPACITY
        if (Arrays.equals(array, EMPTY_ARRAY)){
            array = new Object[DEFAULT_CAPACITY];
            return;
        }

        // full
        // resize the capacity of array to 2 times of the original capacity
        if(size == array_capacity){
            int new_capacity = array_capacity * 2;

            // copy
            array = Arrays.copyOf(array, new_capacity);
            return;
        }

        // when the size of array is under than the half of capacity
        // resize the capacity of array to half of the original capacity
        if(size < (array_capacity / 2)){
            int new_capacity = array_capacity / 2;

            // copy
            array = Arrays.copyOf(array, new_capacity);
            return;
        }
    }

    @Override
    public boolean add(E e) {

        // 기본 add() 는 addLast() 이다.
        addLast(e);
        return true;
    }

    public void addLast(E e){

        // 꽉차있다면 용적 재할당
        if (size == array.length)
            resize();

        array[size] = e;
        size++;
    }

    @Override
    public void add(int index, E e) {

        // index 가 유효값을 벗어나면 예외 출력
        if(index > size || index < 0)
            throw new IndexOutOfBoundsException();

        // index 가 size 이면 가장 마지막에 넣는다는 의미이니 addLast() 호출
        if(index == size) {
            addLast(e);
            return;
        }

        // 꽉차있다면 용적 재할당
        if (size == array.length)
            resize();

        // 빈 공간이 없어야 하니 뒤로 미는 동작 수행
        for(int i=size; i>index; i--){
            array[i] = array[i-1];
        }

        // 요소의 개수 증가
        size++;
        array[index] = e;
    }

    public void addFirst(E e){
        add(0, e);
    }

    @Override
    public boolean remove(Object o) {

        // 해당 요소가 있는지 확인한다.
        int index = indexOf(o);

        // index 가 -1 이면 없다는 의미이니 false 를 반환한다.
        if(index == -1)
            return false;

        // index 의 값을 지우는 것이니 remove(index) 를 사용한다.
        remove(index);
        return true;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E remove(int index) {

        // 범위 벗어나는 경우 예외 발생
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // 요소 반환을 위한 삭제된 요소 임시 저장
        Object deleteElement = array[index];

        // 삭제한 요소 뒤에 있는 모든 요소들을 한 칸씩 당겨옴
        for(int i=index; i<size-1; i++){
            array[i] = array[i+1];
        }

        // 요소의 개수 줄임
        size--;
        // 용적 재할당, 요소 삭제로 인해 요소의 개수가 용적의 절반 이하가 될 수 있음
        resize();
        // 삭제된 요소 반환
        return (E) deleteElement;
    }

    @Override
    public boolean contains(Object o) {

        // indexOf() 를 통해 수행할 수 있다.
        return indexOf(o) != -1;
    }

    @Override
    public int size() {
        // 요소 개수 반환
        return size;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {

        // 범위 벗어나는 경우 예외 발생
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // Object 타입에서 E 타입으로 캐스팅 후 반환
        // 타입 오류의 가능성 때문에 @SuppressWarning 을 적어준다.
        return (E) array[index];
    }

    @Override
    public void set(int index, E e) {

        // 범위 벗어나는 경우 예외 발생
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // 해당 위치 요소 교체
        array[index] = e;
    }

    @Override
    public boolean isEmpty() {
        // 요소의 개수가 0 이면 true 반환
        return size == 0;
    }

    @Override
    public int indexOf(Object o) {

        // 정렬되어있지 않은 배열이므로 선형으로 탐색한다.
        for(int i=0; i<size; i++){
            if(array[i] == o)
                return i;
        }

        // 만약 찾지 못한경우 -1 을 반환한다.
        return -1;
    }

    public int LastindexOf(Object o){

        // indexOf() 와 달리 뒤에서부터 탐색을 진행한다.
        for(int i=size-1; i>-1; i--){
            if(array[i] == o)
                return i;
        }

        // 찾지 못한 경우 -1 을 반환한다.
        return -1;
    }

    @Override
    public void clear() {

        // 모든 공간을 null 처리 해준다.
        for(int i=0; i<size; i++){
            array[i] = null;
        }

        // 요소의 개수를 0개로 하고 용적을 재할당 받는다.
        // size 가 0 이니 DEFAULT_CAPACITY 인 10 으로 할당받는다.
        size = 0;
        resize();
    }

    // 객체의 복사를 위한 메소드
    @Override
    public ArrayList<?> clone() {
        try {

            // Object.clone() 을 이용하여 ArrayList 의 clone 을 만들어준다.
            ArrayList<?> cloneList = (ArrayList<?>) super.clone();
            // TODO: copy mutable state here, so the clone can't change the internals of the original

            // clone 에 저장되어있는 배열들은 얕은 복사가 되니
            // 깊은 복사를 위해 새롭게 배열을 생성해준 후 복사해준다.
            cloneList.array = new Object[size];
            cloneList.array = Arrays.copyOf(array, size);

            return cloneList;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }

    // array 복사
    public Object[] toArray(){
        return Arrays.copyOf(array, size);
    }
    
    // array 를 얻을 때,
    // E 타입의 부모 타입이나, Wrapper 타입으로 변환 할 때 쓰는 메소드
    // ex) ArrayList<int> list = new ArrayList<>();
    //      Integer[] array = new Integer[10];
    //      array = list.toArray(array);
    // int 타입 배열을 Integer 타입 배열로 바꿔서 얻을 수 있다.
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a){
        if(a.length < size){
            // 원본 배열, 복사할 길이, 배열의 요소를 어떤 타입으로 할 건지 정하는 타입
            return (T[]) Arrays.copyOf(array, size, a.getClass());
        }
        
        // 원본 배열, 원본 배열 복사 시작 위치, 복사할 배열, 복사할 배열 시작 위치, 복사할 요소 수
        System.arraycopy(array, 0, a, 0, size);
        return a;
    }
}