자료구조 - Array List

Array List

---

• Array List는 자바에서 가장 흔히 볼 수 있는 JCF입니다. 필자는 지금까지 List를 선언할 때 아무 생각 없이 Array List만을 사용하곤 했었습니다. 또한 자바에서 Array List는 내부적으로 Object[] 배열을 두고 사용합니다.

 

💡 시간 복잡도

• 탐색
  • 내부적으로 Object[] 배열로 구현이 되어있기 때문에 인덱스를 통해 접근이 가능합니다. 따라서 O(1)의 시간 복잡도를 가집니다.
• 삽입
  • 배열의 첫 번째와 중간에 추가하고자 하는 경우 N개의 데이터를 재 정렬해야 하기 때문에 O(n) 만큼의 시간 복잡도를 가질 것으로 예상되며, 마지막에 추가하고자 하는 경우 O(1) 만큼의 시간 복잡도를 가지지 않을까 싶습니다.
• 삭제
  • 배열의 첫 요소와 중간 요소를 삭제하는 경우 N개의 데이터를 재정렬해야하기 때문에 O(n) 만큼의 시간 복잡도를 가질 것으로 예상이 되며, 마지막 요소를 삭제하는 경우에는 O(1)만큼의 시간 복잡도를 가지지 않을까 싶습니다.
• 수정
  • 인덱스를 통해 접근이 가능하니 O(1) 만큼의 시간 복잡도를 가지게됩니다.

 

Array List 구현

---

💡 구현하고자하는 메서드

• 아래의 메서드는 기본적으로 구현하고자 하는 메서드입니다.

public interface List<E> {

    /**
     * 배열의 마지막에 요소를 추가합니다.
     */
    void add(E value);

    /**
     * 배열의 특정 인덱스에 요소를 추가합니다.
     */
    void add(int index, E value);

    /**
     * 배열의 특정 인덱스의 요소를 삭제합니다.
     */
    void remove(int index);

    /**
     * 배열의 특정 요소를 삭제합니다.
     */
    void remove(E value);

    /**
     * 배열의 특정 요소를 반환합니다.
     */
    E get(int index);

    /**
     * 배열의 특정 인덱스에 있는 요소를 찾아 요소를 변경합니다.
     */
    void set(int index, E value);

    /**
     * 배열의 특정 요소가 있는지 확인합니다.
     */
    boolean contains(E value);

    /**
     * 배열의 특정 요소가 위치한 인덱스를 반환합니다.
     */
    int indexOf(E value);

    /**
     * 배열의 개수를 반환합니다.
     */
    int size();

    /**
     * 배열이 비워있는지 확인합니다.
     */
    boolean isEmpty();

    /**
     * 배열의 모든 요소를 삭제합니다.
     */
    void clear();
}

 

💡 기본 필드와 생성자

• Array List는 Obect[] 배열을 사용한다고 하였습니다. 그렇기 때문에 생성자를 통해 빈 배열을 가지는 생성자와, 용량을 설정할 수 있는 생성자를 가지고 있습니다. 

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

    private static final int DEFAULT_CAPACITY = 10; // 기본 크기
    private static final Object[] EMPTY_ARRAY = {}; // 빈 배열
    private int size;                               // 데이터의 개수
    private Object[] elements;                      // 데이터를 담을 배열

    public ArrayList() {
        this.elements = EMPTY_ARRAY;
    }

    public ArrayList(int capacity) {
        this.elements = new Object[capacity];
    }
}

 

💡 add 함수

@Override
public void add(E value) {
    addLast(value);
}

@Override
public void add(int index, E value) {
    if (index < 0 || index > this.size) {
        throw new IndexOutOfBoundsException();
    }
    if (index == this.size) {
        addLast(value);
    } else {
        for (int i = size; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = value;
        size++;
    }
}

private void addFirst(E value) {
    add(0, value);
}

private void addLast(E value) {
    if (this.size == this.elements.length) {
        resize();
    }
    this.elements[size] = value;
    size++;
}

private void resize() {
    int arrayLength = this.elements.length;

    if (arrayLength == 0) {
        elements = new Object[DEFAULT_CAPACITY];
        return;
    }

    if (this.size == arrayLength) {
        int newCapacity = arrayLength * 2;
        elements = Arrays.copyOf(elements, newCapacity);
        return;
    }

    if (this.size < (arrayLength / 2)) {
        int newCapacity = arrayLength / 2;
        elements = Arrays.copyOf(elements, Math.max(newCapacity, DEFAULT_CAPACITY));
        return;
    }
}

 

add(int index, E value) 함수

• 배열의 특정 인덱스에 요소를 추가할 수 있는 메서드입니다.
• 우선 추가하고자 하는 인덱스가 0 미만인지 또는 size를 초과하는지 파악합니다.
• 추가하고자 하는 인덱스가 마지막이라면 addLast 메서드를 호출합니다.
• 추가하고자 하는 인덱스가 0 또는 중간이라면 for 반복자를 반대로 순회하면서 요소를 하나씩 뒤로 옮깁니다. 그러고 난 후 추가하고자 하는 인덱스에 데이터를 삽입합니다.
• 시간 복잡도 부분을 생각하면 처음과 중간에 데이터를 삽입하게 되면 N개의 데이터를 1칸씩 뒤로 밀어야하기 때문에 O(n) 만큼의 시간이 소요하고 마지막에 데이터를 삽입하게 된다면 데이터를 1칸씩 밀지 않아도 되기 때문에 O(1) 만큼의 시간이 걸리게 됩니다.

resize 함수

• 처음 if
  • 현재 배열의 길이를 얻어와서 현재 길이가 0이라면 새로운 배열을 생성합니다.
• 두 번째 if
  • 배열이 꽉 찬 경우 현재 배열의 길이 * 2를 한 다음 Arrays.copyOf 메서드를 사용하여 배열을 복사합니다. 배열의 나머지 빈 공간은 null로 채워집니다.
• 세 번째 if
  • 실질적으로 사용하고 있는 데이터의 개수가 배열의 전체 길이의 절반밖에 되지 않는 경우 나머지 공간은 불필요한 공간이기 때문에 길이를 절반으로 줄여줍니다. 
• Math.max를 사용하는 이유는 기본 크기(10) 미만으로 안떨어지기 위함이라고 참고하는 블로그 분께서 설명을 해주셨습니다. 

 

💡 get, set, contains, indexOf, size, isEmpty 함수

• 다음과 같은 함수들은 간단하니 필요한 부분만 살펴보겠습니다.
• get(탐색)의 경우 인덱스 접근이 가능하니 시간 복잡도는 O(1) 만큼 소요됩니다.
• set(수정)의 경우 인덱스 접근이 가능하니 시간복잡도는 O(1) 만큼 소요됩니다.

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

@Override
public void set(int index, E value) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    this.elements[index] = value;
}

@Override
public boolean contains(E value) {
   return indexOf(value) >= 0;
}

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

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

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

 

💡 remove 함수

@Override
public void remove(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException();
    }
    elements[index] = null;
    for (int i = index; i < size -1; i++) {
        elements[i] = elements[i + 1];
        elements[i + 1] = null;
    }
    size--;
}

@Override
public void remove(E value) {
    int removeIndex = indexOf(value);
    remove(removeIndex);
}

 

remove(int index)

• 배열의 특정 인덱스에 위치한 요소를 삭제하는 메서드입니다. 
• index에 위치한 데이터를 삭제하고 해당 index 이후의 데이터를 한 칸씩 앞으로 당겨오는 것입니다. 
• 첫 요소의 데이터와 중간 요소의 데이터를 삭제한다면 O(n) 만큼의 시간이 소요할 거 같지만 마지막 데이터를 삭제하는 경우에는 O(1) 만큼 소요되지 않을까 싶습니다.

 

 

remove(E value)

• 배열의 특정 데이터를 삭제하는 메서드입니다.
• indexOf 메서드를 사용하여 데이터가 위치한 인덱스를 찾은 다음 기존에 만들어 놓은 remove(index) 메서드를 재활용할 수 있습니다.

 

✔️ 정리

• Array List를 구현함으로써 어떤 구조인지, 시간복잡도는 어떻게 되는지 살펴볼 수 있었습니다.
• 개인적으로 공부하는 글이니 정확하지 않습니다. 

 

 

참고자료)

• https://st-lab.tistory.com/161