ArrayList

• ArrayList

 

원소를 추가할때 배열에 남은 공간이 없으면?

크기를 일정 배수로 늘린 배열 새로운 배열을 만들어 기존 배열의 원소를 옮긴다

(자바에서 ArrayList는 1.5배, Vector는 2배 증가시킨다)

중간 원소 삽입/삭제 연산은 기존 배열과 동일 == 느리다

랜덤 액세스는 O(1)번 만에 가능하다

 

구현 코드

import java.util.Arrays;

public class MyArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private int size = 0;
    private Object[] data;


    //생성할떄 크기를 지정받으면 해당 크기만큼, 아니면 기본 크기인 10으로 생성한다
    public MyArrayList(int initalCapacity){
        data = new Object[initalCapacity];
    }

    public MyArrayList(){
        this(DEFAULT_CAPACITY);
    }

    public int size(){
        return size;
    }

    public void add(E element){
        if (size == data.length){
            growCapacity();
            data[size++] = element;
        }
    }

    private void growCapacity(){
        // 기존 length의 1.5배를 한 배열에 data 배열을 복사한다
        int newCapacity = data.length + (data.length >> 1);
        data = Arrays.copyOf(data, newCapacity);
    }

    public E get(int idx){
        //현재 size의 범위를 벗어나면 오류를 내고 아니면 해당 인덱스 데이터 리턴
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx
            + ", Size " + size);
        return (E) data[idx];
    }

    public void set(int idx, E element){
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx
                    + ", Size " + size);
        data[idx] = element;
    }

    //삽입 연산시 뒤로 한칸씩 밀어주는 연산하고 해당 idx에 원소 삽입
    // 1. 크기 확인 2. 들어갈 인덱스 확인
    public void insert(int idx, E element){
        //0~size 크기까지 추가 가능하다
        if (idx < 0 || idx > size){
            throw new IndexOutOfBoundsException("Index: " + idx
                    + ", Size " + size);
        }
        if (size == data.length) growCapacity();
        // 전체가 10개, 넣으려는 인덱스가 3이면 3~9번 까지는 뒤로 밀어줘야한다
        int copyLength = size - idx;
        // copyLength 갯수 원소를 data[idx] 부터 뒤로 하나씩 이동시킨다
        System.arraycopy(data, idx, data, idx+1, copyLength);
        // 해당 idx에 원소를 삽입하고 전체 크기를 1늘려준다
        data[idx] = element;
        size++;
    }

    public void delete(int idx){
    	// 0~ size-1까지 현재 있는 원소들인지 확인
        if (idx < 0 || idx >= size){
            throw new IndexOutOfBoundsException("Index: " + idx
                    + ", Size " + size);
        }
        int copyLength = size - idx-1;
        // 여기선 index 뒤에 원소들을 한칸씩 앞으로 당겨준다
        System.arraycopy(data, idx+1, data, idx, copyLength);
        size--;
    }
}