[자료구조/JAVA] 동적 배열(Dynamic Array) 구현

배열과 동적 배열

 

 

 

배열 : 미리 정해진 크기의 메모리 공간을 할당 받은 뒤 사용한다. 따라서 메모리 공간을 초과하면 오버플로우가 발생한다.

 

동적 배열 : 동적인 크기의 배열을 사용하기 위해서 유동적으로 배열의 크기를 조절하는 아이디어. 배열에 Overflow가 발생하면 배열 크기를 2배로 확장한다, 배열의 3/4가 비어 있다면 배열 크기를 1/2로 축소한다. Java에서 제공하는 대표적인 클래스로 ArrayList가 있다.

 

https://en.wikipedia.org/wiki/Dynamic_array

 

ArrayList의 특징

 

동적 크기 조정: Element의 추가나 삭제에 따라 크기가 자동으로 조정된다.

인덱스 기반 접근: 배열과 유사하게 인덱스를 사용하여 Element에 접근할 수 있다.

제네릭 지원: 제네릭을 사용하여 다양한 타입의 Element를 저장할 수 있다.

순서 보장: Element의 순서가 유지된다.

 

해당 특징을 바탕으로 직접 동적 배열을 구현해보도록 하자.

 

---

동적 배열 구현

 

class MyDynamicArray <E> {
    private E elements[];
    private int size;
    public MyDynamicArray(){
        elements = (E[]) new Object[1];
        size = 0;
    }


    public boolean isEmpty(){
        return size == 0;
    }
    
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] != null) {
                sb.append(elements[i]);
                if (i < elements.length - 1 && elements[i + 1] != null) {
                    sb.append(", ");
                }
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

 

우선 동적 배열의 클래스를 정의한다. 내부에는 Element들을 담을 배열과 동적 배열의 사이즈를 넣을 속성을 만든다.

초기 배열의 크기는 1로 설정했으며, toString 메서드를 정의하여 배열의 내용을 반환하도록 만들어주었다.

동적 배열이 비어있는지를 확인하는 isEmpty 메서드를 함께 만들어주었다.

 

 

---

인덱스로 조회하기

public E get(int k){
    if(size == 0){
        throw new NoSuchElementException();
    }
    return elements[k];
}

 

인덱스를 통해서 배열의 원소를 반환하는 메서드이다. 만약 원소가 존재하지 않으면 Exception을 반환한다.

 

 

 

---

배열 크기 조절 메서드

private void resize(int newSize){
    // 기존의 배열은 가비지 컬렉션에 의해서 처리된다.
    Object[] newList = new Object[newSize];
    for(int i = 0; i < size; i++){
        newList[i] = elements[i];
    }
    elements = (E[]) newList;
}

 

배열의 크기를 조절하는 내부적인 메서드이다.

해당 메서드가 호출되면, 새로운 사이즈의 배열이 생성되고, 해당 배열로 기존 배열의 Element들이 복제된다. 그리고 새로운 배열이 기존 배열을 대체하게 된다.

기존 배열은 JVM의 가비지 컬렉션에 의해서 메모리상에서 제거된다.

 

 

    private void resize(int newSize){
//        Object[] newList = new Object[newSize];
//        for(int i = 0; i < size; i++){
//            newList[i] = elements[i];
//        }
//        elements = (E[]) newList;

        Object[] newList = Arrays.copyOf(elements, newSize);
        elements = (E[]) newList;
    }

 

해당 코드는 Arrays 클래스에서 제공하는 copyOf() 메서드를 활용하여 간단하게 줄일 수 있다.

---

동적 배열에 원소 추가

public void add(E element){
    if(size == elements.length){
        resize(2 * elements.length);
    }
    elements[size++] = element;
}

public void add(int k, E element){
    if(size == elements.length){
        resize(2 * elements.length);
    }

    // K번째 이후 원소는 한 칸 씩 뒤로 이동
    for(int i = size - 1; i >= k; i--){
        elements[i+1] = elements[i];
    }
    elements[k] = element;
    size++;
}

 

원소를 추가하는 메서드로 맨 끝에 추가하는 메서드와, 특정 인덱스에 추가하는 메서드 두 가지를 만들어 주었다.

먼저 두 가지 경우 모두 추가하기 전, 배열의 크기를 확인하여 만약 배열이 꽉 차있다면, 배열의 크기를 2배로 늘려준다.

 

그 다음 맨 끝에 추가하는 경우 끝에 원소를 추가한 이후 사이즈를 증가시킨다.

특정 인덱스에 원소를 추가하는 경우, 해당 인덱스에 원소를 삽입하기 이전에 해당 인덱스를 포함한 이후의 원소들의 인덱스를 1씩 중가시켜 한 칸씩 뒤로 이동시킨 후 원소를 추가시킨다. 그리고 사이즈를 증가시킨다.

 

 

 

---

동적 배열에 원소 제거

public E delete(int k){
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    else{
        E item = elements[k];

        // 삭제된 인덱스 기준 뒤의 아이템들을 한 칸씩 앞으로 이동
        for(int i = k; i < size - 1; i++){
            elements[i] = elements[i + 1];
        }
        elements[size - 1] = null;


        if(size > 0 && size == elements.length / 4){
            resize(elements.length / 2);
        }
        return item;
    }
}

 

이번에는 특정 인덱스의 원소를 제거시키는 메서드를 만들어보자.  만약 배열이 비어있을 경우에는 예외를 반환시킨다.

그 이후, 삭제할 인덱스를 기준으로 뒤의 아이템들을 한 칸씩 앞으로 이동시킨 후, 사이즈를 줄인다.

해당 과정을 통해 해당 인덱스의 원소를 삭제한 이후, 원소들의 수가 배열의 크기의 1/4일 경우, 크기를 1/2로 줄인다.

 

 

 

전체 코드

class MyDynamicArray <E> {
    private E elements[];
    private int size;
    public MyDynamicArray(){
        elements = (E[]) new Object[1];
        size = 0;
    }

    public E get(int k){
        if(size == 0){
            throw new NoSuchElementException();
        }
        return elements[k];
    }

    public void add(E element){
        if(size == elements.length){
            resize(2 * elements.length);
        }
        elements[size++] = element;
    }

    public void add(int k, E element){
        if(size == elements.length){
            resize(2 * elements.length);
        }

        // K번째 이후 원소는 한 칸 씩 뒤로 이동
        for(int i = size - 1; i >= k; i--){
            elements[i+1] = elements[i];
        }
        elements[k] = element;
        size++;
    }

    public E remove(int k){
        if(isEmpty()){
            throw new NoSuchElementException();
        }
        else{
            E item = elements[k];

            // 삭제된 인덱스 기준 뒤의 아이템들을 한 칸씩 앞으로 이동
            for(int i = k; i < size - 1; i++){
                elements[i] = elements[i + 1];
            }
            elements[size - 1] = null;

            if(size > 0 && size == elements.length / 4){
                resize(elements.length / 2);
            }
            return item;
        }
    }

    public boolean isEmpty(){
        return size == 0;
    }

    private void resize(int newSize){
//        Object[] newList = new Object[newSize];
//        for(int i = 0; i < size; i++){
//            newList[i] = elements[i];
//        }
//        elements = (E[]) newList;

        Object[] newList = Arrays.copyOf(elements, newSize);
        elements = (E[]) newList;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] != null) {
                sb.append(elements[i]);
                if (i < elements.length - 1 && elements[i + 1] != null) {
                    sb.append(", ");
                }
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

---

사용 예시

 

직접 작성한 동적 배열 사용

public static void main(String[] args) {
    MyDynamicArray list = new MyDynamicArray<Integer>();
    list.add(1);
    list.add(2);
    list.add(4);
    System.out.println(list); // [1, 2, 4]
    System.out.println(list.get(1)); // 2
    list.add(3, 2);
    System.out.println(list); // [1, 2, 3, 4]
    list.remove(0);	
    System.out.println(list); // [2, 3, 4]

}

 

 

ArrayList 사용

public static void main(String[] args) {
    List list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(4);
    System.out.println(list); // [1, 2, 4]
    System.out.println(list.get(1)); // 2
    list.add(3, 2);
    System.out.println(list); // [1, 2, 3, 4]
    list.remove(0);	
    System.out.println(list); // [2, 3, 4]

}