자료구조 배열 리스트 (ArrayList) 자바로 구현

1. 개요

자료구조인 배열 리스트를 자바로 구현하고, 메소드별 시간복잡도를 확인해본다.

 

우선 배열 리스트의 장단점을, 연결 리스트와 비교하며 확인해보자

 

장점

• 배열로 구현되어 있으므로, 인덱스 번호로 접근이 가능하고, 탐색시간이 아주 짧다. (연결 리스트의 경우, 원하는 데이터를 찾을 때까지, 포인터를 타고 이동하면서 찾아야 한다.)

단점

• 생성할 때, 크기를 정하고 생성해야 하는데, 크기가 작으면 데이터가 꽉 찼을 때, 다시 생성해줘야 하고, 크기가 크면 남는 공간만큼 메모리의 낭비가 생긴다
• 효율적으로 관리하기 위해, 연속적으로 데이터를 넣어줘야 하는데, 데이터의 추가와 삭제가 있을 경우, 데이터를 밀고 당겨야 하는 작업이 필요하고, 시간이 오래 걸린다. (배열의 크기가 50이고, 40개의 데이터가 차있다. 11번에 데이터를 넣으려면, 11번의 데이터를 유지하기 위해, 11번은 12번으로, 12번은 13번으로 뒤에 있는 데이터를 모두 한칸씩 밀어줘야 한다. 반대로 11번을 삭제할 경우, 11번의 자리가 비면 메모리 낭비가 생기기 때문에, 12번을 11번으로, 13번을 12번으로 뒤에 있는 모든 데이터를 한칸씩 당겨줘야 한다.)

 

2. 구현

package Structure;

public interface IList<T> {

    void add(T t);

    void insert(int index, T t);

    void clear();

    boolean delete(T t);

    boolean deleteByIndex(int index);

    T get(int index);

    int indexOf(T t);

    boolean isEmpty();

    boolean contains(T t);

    int size();
}

 

package Structure;

import java.util.Arrays;

public class MyArrayList<T> implements IList<T>{
    private static final int DEFAULT_SIZE = 50;

    private T[] elements; // Array T 선언
    private int size;

    public MyArrayList() {
        this.size = 0;
        this.elements = (T[]) new Object[DEFAULT_SIZE];
    }

    @Override
    public void add(T t) {
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.size * 2);
            // copyOf는 자바에서 제공하는 메소드다. 첫번째 매개변수를 집어넣은 두번째 매개변수 크기의 배열을 만든다.
        }
        this.elements[this.size++] = t;
    }

    @Override
    public void insert(int index, T t) {
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.size * 2);
        }
        for (int i = index; i < this.size; i++) {
            this.elements[i + 1] = this.elements[i];
        }
        this.elements[index] = t;
        this.size++;
    }

    @Override
    public void clear() {
        this.size = 0;
        this.elements = (T[]) new Object[DEFAULT_SIZE];
    }

    @Override
    public boolean delete(T t) {
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) {
                for (int j = i; i < this.size - 1; j++) {
                    this.elements[j] = this.elements[j + 1];
                }
                this.size--;
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean deleteByIndex(int index) {
        if (index < 0 || index > this.size - 1) {
            return false;
        }
        for (int i = index; i < this.size - 1; i++) { // 하나씩 당겨오니 size가 50이고 삭제할 데이터의 인덱스가
            this.elements[i] = this.elements[i + 1]; // 50일 경우, 51을 참조하면 에러가 나니 size - 1 을 한다.
        }
        this.size--;
        return false;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > this.size - 1) {
            throw new IndexOutOfBoundsException();
        }
        return this.elements[index];
    }

    @Override
    public int indexOf(T t) {
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean contains(T t) {
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int size() {
        return this.size;
    }
}

 

3. 설명

자료구조인 ArrayList를 자바로 구현하고, 메소드별 시간복잡도를 확인해본다.

 

3-1. 멤버변수

DEFAULT_SIZE 는 말 그대로 배열을 생성할 때, 기본 사이즈로 쓰기 위해 만든 변수다.

 

size는 지금 들어가 있는 데이터의 수를 나타내는 변수다.

 

T[] elements는 자료구조를 사용할 때, 인수로 들어오는 수에 따라 달라지는 제네릭 변수로 만든 배열이다.

 

 

3-2. 생성자 (constructor)

생성자는 인스턴스가 처음 생길 때, 작동하는 메소드다.

 

처음 생성될 때에는 아무 데이터도 들어있지 않으니 size 는 0이다.

 

그리고 MyArrayList 인스턴스 안에 크기 50의 제네릭 배열의 인스턴스를 생성한다.

 

 

3-3. add

add는 ArrayList의 테일 부분에 데이터를 넣는 메소드다.

 

배열의 인덱스는 0부터 시작이다. size가 1이어도, 그 데이터의 인덱스는 size보다 1 작다.

그러므로, elements[this.size] 에 인수인 t를 집어넣고, 그 연산이 끝나면 size가 증가하도록 후위연산자를

사용했다.

 

하지만 이 과정을 거치기 전에, 선언한 배열이 이미 꽉 찼는지 확인해야한다.

 

데이터의 유무와 관계없이 elements는 50으로 선언했으니 elements의 length 는 50이다.

size가 50과 같다는 말은 ArrayList가 꽉 찼다는 말이다.

 

만약 다 찼다면, Arrays.cofyOf를 사용해서, 원래 있던 내용을 집어넣은, 지금의 사이즈보다 2배 큰 배열을

다시 선언한다.

 

시간복잡도 O(1)

 

 

3-4. Insert

insert는 지정한 인덱스 번호의 위치에 있는 데이터를, t로 바꾸고, 그 뒤에 있는 데이터들을 한칸씩 밀어줘서

원래 데이터를 유지하면서 원하는 위치에 데이터를 집어넣는 메소드다.

 

우선, 배열이 꽉 찼는지 확인한다.

꽉 찼으면 배열 크기를 2배로 만들고, 삽입할 index의 위치부터 데이터의 끝까지 for 문을 돌린다.

 

this.elements[i + 1] = this.elements[i];

는 i보다 1 큰 장소에 i의 데이터를 집어넣어란 말이다. 즉 원하는 위치에 데이터가 들어갈 수 있게 데이터를

다 한칸씩 밀어준다는 말이다.

 

for문이 끝나면 원하는 자리가 비어있으니 거기다 인수인 t를 집어넣는다.

 

시간복잡도 O(N)

 

3-5. clear

clear는 배열을 초기화하는 메소드다.

 

작업은 생성자와 같다.

size를 0으로 만들고, 빈 크기 50의 제네릭 배열을 생성한다.

 

시간복잡도 O(1)

 

 

3-6. delete

인수로 들어온 데이터와 같은 데이터가 ArrayList 내에 있으면 삭제하는 메소드다.

 

for문으로 배열 내부를 다 돌면서 그 내용과 t가 같은지 뒤져보는데, 만약 같은 게 있으면 

그 인덱스부터 시작해서 for문을 돌면서, 데이터를 당겨오면서 원래 있던 자리에 있던 데이터를 삭제한다.

 

끝나면 사이즈를 1 줄이고 삭제에 성공했다는 true를 반환한다.

 

만약 같은 데이터가 없다면 실패했다는 false를 반환하고 끝난다.

 

 

3-7. deleteByIndex

 

인덱스 번호에 있는 데이터를 삭제하는 메소드다.

 

만약 인수가 음수거나, 지금 사이즈-1 보다 크면 false를 반환한다.

지금 사이즈-1 인 이유는, 삭제하는 과정에서 앞의 데이터를 당겨와야 하는데, size와 같으면 마지막에 당겨올

데이터가 없으니 IndexOutOfBoundsException 에러가 발생한다.

 

인덱스가 제대로 들어왔다면 인덱스부터 시작하는 for문을 돌려서 그 데이터가 사라지도록, 데이터를 하나씩

당겨오고 끝나면 사이즈를 줄이고 삭제에 성공했다는 true를 반환하고 끝난다.

 

O(N)

 

 

3-8. T get

T get은 인덱스 번호에 있는 데이터를 반환하는 메소드다.

 

여기서도 If문이 size-1인 이유는, 배열의 인덱스는 0부터 시작하니 사이즈와 인덱스가 같다면 에러가 발생하게

한다.

 

그리고 인수로 온 인덱스 번호의 데이터를 반환한다.

 

O(1)

 

3-9. indexOf

인수로 들어온 데이터 t와 같은 데이터의 인덱스를 반환한다.

 

for문으로 처음부터 데이터가 있는 마지막 배열까지 뒤져보고, 만약 t와 같은 게 있다면 그 인덱스를 반환하고,

 

없다면 인덱스에 존재하지 않는 -1을 반환한다.

 

O(N)

 

 

3-10. isEmpty

ArrayList가 비었나 확인하는 메소드다.

 

boolean이니 사이즈가 0이 맞으면 true고, 아니면 false니 데이터가 있다는 말이다.

 

O(1)

 

 

3-11. contains

인수로 들어온 t와 같은 데이터가 ArrayList 내에 있나 확인하는 메소드다.

 

배열 처음부터 데이터가 있는 배열 끝까지 뒤져보고, 같은 게 있으면 true, 없으면 false를 반환한다.

 

O(N)

 

 

3-12. size

ArrayList의 사이즈를 반환한다.

걍 원래 쓰던 멤버변수인 size를 반환하면 된다.

 

O(1)

 

4. 시간복잡도 정리

 

add (데이터가 있는 마지막 데이터 뒤에 추가) O(1)

insert (인덱스 번호에 삽입) O(N)

clear (ArrayList 초기화) O(1)

delete (인수와 같은 데이터 있으면 삭제) O(N)

deleteByIndex (인덱스 번호에 있는 데이터 삭제) O(N)

get (인덱스 번호에 있는 데이터 가져오기) O(1)

indexOf (인수와 같은 데이터의 인덱스 반환) O(N)

isEmpty (ArrayList의 크기 반환) O(1)

contains (인수로 들어온 데이터가 배열에 있나 확인) O(N)

size (배열의 크기 반환) O(1)