[면접을 위한 CS 전공지식 노트][자료구조] Array(배열)와 ArrayList

0.  개요

 JAVA에서는 배열을 직접 사용할 수도 있고, 배열을 사용하기 쉽게 구현해놓은 ArrayList가 존재한다. 자료구조를 공부하면서 이 부분에 대해서 정리하여 기록하고자 이 글을 작성한다.

 

1.  Array

 배열이라는 자료구조의 특징을 살펴보면, 

1. 선형적인 자료구조이다.

2. 데이터를 일렬로 늘여놓은 형태이다.

3. 물리적으로도 데이터가 메모리에 연속적으로 저장된다는 특징을 가지고 있다.

4. 같은 데이터 타입만을 저장할 수 있다. -> 다른 데이터 타입을 저장하고자 한다면 class 선언을 하여 객체를 이용하여 사용할 수 있다.

등을 이야기 해볼 수 있겠다.

 

 Java를 이용해 프로그래밍을 하는 경우 종종 배열을 직접 사용하는 경우도 있지만, 대부분의 경우 배열을 사용하기 쉽게 구현해놓은 ArrayList를 많이 사용하게 된다. 그렇기 때문에 Array의 특징은 모두 ArrayList가 가지고 있으며, 이에 대해서 좀 더 자세히 정리해보고자 한다.

 

2.  ArrayList

 일단 ArrayList는 배열이 가지고 있는 특징을 모두 가지고 있지만, 가장 큰 차이점은 List의 size가 꽉 찬상태에서 새로운 element가 추가되면 크기를 동적으로 늘려준다는 것이다. 실제로 물리적으로는 새로운 사이즈의 메모리를 할당받아서 거기에 다시 저장하는 것이지만, 사용자는 배열의 크기와 상관없이 엘리먼트를 추가, 삭제 할 수 있다.

 

 ArrayList에 대해서 좀 더 자세히 이해하기 위해서 핵심적인 메서드를 중심으로 실제로 자료구조를 구현해보았다.

 

List의 기능 명세한 인터페이스

public interface IList<T> {
    /**
     * 엘리먼트 추가
     * @param t
     */
    void add(T t);

    /**
     * 엘리먼트 삽입
     * @param index
     * @param t
     */
    void insert(int index, T t);

    /**
     * 엘리먼트 전부 삭제
     */
    void clear();

    /**
     * 해당 엘리먼트 삭제
     * @param t
     * @return
     */
    boolean delete(T t);

    /**
     * 인덱스를 이용한 엘리먼트 삭제
     * @param index
     * @return
     */
    boolean deleteByIndex(int index);

    /**
     * 인덱스에 해당하는 엘리먼트 가져오기
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 해당 엘리먼트의 인덱스 가져오기
     * @param t
     * @return
     */
    int indexOf(T t);

    /**
     * 비어있는지 확인
     * @return
     */
    boolean isEmpty();

    /**
     * 해당 엘리먼트가 포함되어 있는지 확인
     * @param t
     * @return
     */
    boolean contains(T t);

    /**
     * 현재 사이즈 가져오기
     * @return
     */
    int size();
}

 

List 인터페이스 명세를 바탕으로 구현한 구현체

public class MyArrayList<T> implements IList<T> {
    /**
     * 처음 배열이 선언될 경우 default size
     */
    private static final int DEFAULT_SIZE = 50;

    /**
     * 배열의 실제 사이즈
     */
    private int size;

    /**
     * 엘리먼트들이 저장될 배열
     */
    private T[] elements;

    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(elements, this.size * 2);
        }
        this.elements[this.size++] = t;
    }

    @Override
    public void insert(int index, T t) {
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(elements, this.size * 2);
        }
        for (int i = this.size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        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 (t.equals(this.elements[i])) {
                for (int j = i; j < this.size - 1; i++) {
                    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) {
            return false;
        }
        for (int i = index; i < this.size - 1; i++) {
            this.elements[i] = this.elements[i + 1];
        }
        this.size--;
        return true;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        }
        return 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.  시간복잡도

 이전에 시간복잡도 정리글에서 배열은 아래와 같은 시간 복잡도를 보여주었다.

 

시간 복잡도

자료구조	접근	탐색	삽입	삭제	비고
배열	O(1)	O(n)	O(n)	O(n)	인덱스를 통한 랜덤 액세스

1) 접근

 접근을 할 경우에는 인덱스를 통한 랜덤액세스를 통해 한 번의 탐색으로 데이터를 가져올 수 있으므로 시간 복잡도는 O(1).

 

2) 탐색

 인덱스가 아닌 순회를 하면서 값을 탐색할 경우에 Target으로하는 엘리먼트가 맨 뒤에 있을 경우 최대 n번의 탐색이 필요할 수 있으므로 시간 복잡도는 O(n).

 

3) 삽입

 배열 같은 경우 삽입을 하기 위해서는 삽입하려는 인덱스 다음부터 엘리먼트를 한칸씩 뒤로 움직여줘야 하는 작업이 필요하다. 그렇기 때문에 맨 앞에 엘리먼트를 삽입할 경우 모든 엘리먼트를 한 칸씩 뒤로 움직여 줘야하므로 시간복잡도는 O(n).

 

4) 삭제

 삭제 같은 경우도 삽입과 마찬가지로 해당 엘리먼트를 삭제한 뒤, 빈 공간을 매꿔주기 위해서 엘리먼트들을 앞으로 한칸씩 움직여 줘야한다. 그렇기 때문에 맨 앞의 엘리먼트를 삭제한다고 했을 때 모든 엘리먼트를 앞으로 1칸씩 움직여 줘야하기 때문에 시간복잡도는 O(n).

 

4.  ArrayList와 LinkedList의 비교

 Java에서는 배열을 기반으로 한 ArrayList 뿐만 아니라 LinkedList도 존재한다. 그 둘은 각각 장단점이 존재하는데 그 부분도 이 글에서 정리하고자 한다.

 ArrayList 같은 경우 메모리공간을 연속적으로 사용하지만, LinkedList 같은 경우는 메모리공간에 연속적으로 저장하는 것이 아닌 분산된 구조이다. 즉, 아래의 그림과 같은 형태가 된다.

 

 LinkedList는 각각의 노드들이 있고, 노드들은 data와 다음 노드를 가리키는 주소를 가지고 있다. 그렇기 때문에 여기서 발생하는 두 타입의 장단점이 존재한다.

 

1) 탐색, 순차적인 추가

 탐색 같은 경우, 연속적인 메모리를 가지고 있는 ArrayList가 빠르다. 인덱스로 접근할 수 도 있고, 연속된 메모리 구조를 가지고 있기 때문에 순회하는 속도도 LinkedList보다 빠르다.

 순차적인 추가 같은 경우도 ArrayList가 빠르다. size를 통한 인덱스 접근을 통해 후위에 데이터를 추가하면 되기 때문에 빠르다. 반면 LinkedList는 맨 뒤 노드를 찾으려고 한다면 모든 노드를 순회해야한다. (이중 연결리스트 같은 경우에는 tail로 찾을 수 있긴 하다.)

 

2) 삽입, 삭제

 삽입 삭제 같은 경우는 LinkedList가 더 빠르다. ArrayList 같은 경우 삽입, 삭제가 발생할 시 엘리먼트를 이동시켜주어야 하는 작업이 발생하지만, LinkedList 같은 경우는 연결만 끊어 주고 새로운 연결을 해주면 되기 때문에 삽입, 삭제에서는 LinkedList가 빠르다.

 

 

5. 정리

1. 배열은 선형적인 자료구조, 연속된 자료형태를 가지고 있음, 물리적으로도 연속적으로 메모리에 저장,할당된 크기 만큼의 엘리먼트를 넣을 수 있다.

2. Java에서는 배열을 구현해놓은 ArrayList가 존재한다. 배열과 흡사한 특징은 가지고 있으며, 엘리먼트가 늘어남에 따라 배열의 크기가 꽉찬 상태에서 새로운 엘리먼트의 추가가 필요할 경우 새로운 크기의 메모리를 할당받아서 새로 저장된다. 즉, ArrayList를 사용하면 개발자는 배열의 크기조절을 따로 컨트롤 하지 않아도 된다.

3. 배열의 시간복잡도는 인덱스를 통한 접근은 O(1), 탐색, 삽입, 삭제는 O(n)의 시간복잡도가 발생.

4. Java에서는 ArrayList 뿐만아니라 LinkedList도 존재한다. 접근, 순차적인추가에서는 ArrayList를 사용하는 것이 성능이 좋고,  삽입,삭제에서는 LinkedList를 사용하는 것이 성능이 좋다.

 

참조

면접을 위한 CS 전공지식 노트

야놀자 테크스쿨 패스트캠퍼스 온라인 강의 - 자료구조/알고리즘