ArrayList

List

리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다.

• 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다.
• 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다.

또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다.

배열 기반 리스트

배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다. 배열 기반 리스트를 사용하면 노드들이 물리적인 메모리 주소상으로 연속되어 저장된다.

구현

아래는 배열 기반 리스트를 간략하게 구현한 Java 코드이다. Java Collection에서는 ArrayList 클래스로 배열 기반 리스트를 제공하고 있다. 배열 중간에 요소를 삽입하거나 삭제 시 O(N)의 시간복잡도가 발생한다. 반면에 get, set, 마지막에 요소 추가는 O(1)이다.

package DataStructure.ArrayList;
import java.util.Arrays;

public class ArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10; //기본 용량
    private Object[] elementData;
    private int size; //배열 크기, 마지막 원소 인덱스 + 1 = size

    public ArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    //배열 크기 조절
    private void reSize() {
        int capacity = elementData.length;

        //용량이 꽉 찬 경우, 용량을 50% 늘려줌
        if (size == capacity) {
            int newCapacity = capacity + (capacity >> 1);
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        //크기가 용량의 절반보다 작은경우, 용량을 50% 줄여줌
        else if ((capacity >> 1) > size) {
            int halfCapacity = capacity >> 1;
            elementData = Arrays.copyOf(elementData, Math.max(halfCapacity, DEFAULT_CAPACITY));
        }
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
    }

    /***
     * @param index - 0 ~ size-1
     * @return - index 위치의 요소
     */
    public E get(int index) {
        rangeCheck(index);
        return (E) elementData[index];
    }

    /***
     * 마지막 위치에 e 삽입
     * @param e - 삽입할 요소
     */
    public void add(E e) {
        reSize();
        elementData[size++] = e;
    }

    /***
     * @param index - 삽입 위치, 0 ~ size
     * @param e - 삽입할 요소
     */
    public void insert(int index, E e) {
        //맨 뒤에 삽입
        if(index == size) {
            add(e);
        }
        else {
            rangeCheck(index);
            reSize();
            for (int i = size; i > index; i--) {
                elementData[i] = elementData[i - 1];
            }
            elementData[index] = e;
            size++;
        }
    }

    /***
     * @param index - 삭제 위치, 0 ~ size - 1
     * @return - 삭제된 요소
     */
    public E remove(int index) {
        rangeCheck(index);

        E element = (E) elementData[index];

        //요소 제거 (명시적으로 요소를 null로 처리해야 GC가 수거)
        elementData[index] = null;
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
        elementData[size - 1] = null;
        size--;
        reSize();
        return element;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(get(i)).append(' ');
        }
        return sb.toString();
    }
}