가변 배열(ArrayList)

특징

• 배열의 장점인 index 조회를 사용하기 위해 크기 고정의 약점을 극복한 자료 구조
• 크기 제한에 걸릴 때, 메모리 공간 확보 + 기존 데이터 이관 작업을 별도로 해줄 필요 없음

구현

package arraylist.implementation;

import java.util.ListIterator;

public class ArrayList {
    // private 은 비공개 접근자
    private int size = 0;
    private Object[] elementData = new Object[100];

    public boolean addFirst(Object element) {
        return add(0, element);
    }
    public boolean addLast(Object element) {
        elementData[size] = element;
        size++;
        return true;
    }
    public boolean add(int index, Object element) {
        for (int i = size - 1; i >= index; i--) {
            // 맨 마지막 요소부터 index 요소까지 한 칸씩 뒤로 이동
            elementData[i + 1] = elementData[i];
        }
        elementData[index] = element;
        size++;
        return true;
    }
    public Object remove(int index) {
        // 삭제할 요소를 미리 removed 변수에 저장
        Object removed = elementData[index];
        for (int i = index + 1; i <= size - 1; i++) {
            // 삭제할 요소 다음 요소부터 한 칸씩 당긴다
            elementData[i - 1] = elementData[i];
        }
        size--;
        // 마지막 위치의 요소를 명시적으로 삭제
        elementData[size] = null;
        return removed;
    }
    public Object removeFirst() {
        return remove(0);
    }
    public Object removeLast() {
        return remove(size - 1);
    }
    public Object get(int index) {
        // Random Access
        return elementData[index];
    }
    public String toString() {
        String str = "[";
        for (int i = 0; i < size; i++) {
            str += elementData[i];
            if (i < size - 1) {
                str += ",";
            }
        }
        return str + "]";
    }
    public int size() {
        return size;
    }
    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals((elementData[i]))) {
                return i;
            }
        }
        return -1;
    }
    public ListIterator listIterator() {
        return new ListIterator();
    }
    class ListIterator {
        private int nextIndex = 0;

        public boolean hasNext() {
            return nextIndex < size;
        }
        public boolean hasPrevious() {
            // 먼저 1 감소시키고 참조하므로 최소 1이상일 때만 true
            return nextIndex > 0;
        }
        // 순차적으로 다음 노드 반환
        public Object next() {
//            Object returnData =  elementData[nextIndex];
//            nextIndex++;
//            return returnData;
            return elementData[nextIndex++];
        }
        // 순차적으로 이전 노드 반환
        public Object previous() {
            // next를 계속하면 리스트 범위를 벗어나는 index를 가리키게 된다
            // previous 동작 시 정상 동작 가능하도록 먼저 index를 감소시키고 참조한다.
            return elementData[--nextIndex];
        }
        public void add(Object element) {
            // 그냥 add는 이 메소드 이름과 충돌하기 때문에 ArrayList.this를 사용해 누구의 메소드를 사용하는지 명시적으로 표시
            ArrayList.this.add(nextIndex++, element);
        }
        // 현재 요소를 삭제
        public void remove() {
            ArrayList.this.remove(nextIndex-1);
            nextIndex--;
        }
    }
}