[Java-자료구조] ArrayList 사용과 구현

ArrayList

•  List 인터페이스를 상속받은 클래스
• 일반적인 배열과 동일하게 연속적인 공간을 사용하고 인덱스 또한 0부터 시작된다.
• 인덱스를 통한 임의접근이 가능하다
• 객체가 추가되면서 현재 가용량(capacity)을 넘어선다면 자동으로 크기가 늘어나는 특징을 가진다. (가변적)
• List이기에 데이터 순서가 있으며 동일 데이터에 대한 중복 저장을 허용한다.

 

ArrayList

0

1

2

3

4

멤버변수: capacity(용량), size(들어있는 element 개수)

 

ArrayList 사용법

import java.util.ArrayList;

자바는 java.util.ArrayList Class를 통해 ArrayList를 제공하고 있다.

 

ArrayList 선언

ArrayList al = new ArrayList(); // 타입 미설정(Object)으로 가능은 하나 보통 type을 설정해줌.
ArrayList<Integer> ex1 = new ArrayList<>();  // Primitive type이 아닌 Wrapper Class사용.
ArrayList<Integer> ex2 = new ArrayList<>(5); // 초기 Capacity 설정
ArrayList<Subject> ex3 = new ArrayList<>(); // 일반적인 객체도 가능.
ArrayList<Integer> ex4 = new ArrayList<>(Arrays.asList(1,2,3))// capacity가 아닌 element들 넣기

다양한 방식으로 ArrayList의 생성아 가능하다.

 

ArrayList 메서드

 

데이터 추가

arrayList.add(Object element); // 맨 뒤에 element 추가
arrayList.add(int index, Object element); // 특정 index위치에 element 추가

 

데이터 삭제

arrayList.remove(int index); // 특정 index에 위치한 element 제거
arrayList.remove(Object element); // 특정 element를 제거
arrayList.clear(); // 모든 ArrayList 내부에 있는 element 제거

 

데이터 수정

arrayList.set(int index, Object element) // 특정 index에 있는 data를 새로운 data로 변경

 

데이터 검색

arrayList.contains(Object element); // 특정 element의 존재여부 확인
arrayList.indexOf(Object element); // 특정 element의 index 위치 반환
arrayList.get(int index) // 특정 index에 있는 element 반환
arrayList.isEmpty() // 비어있는지 확인

 

misc

arrayList.size(); // element의 개수 반환
arrayList.toArray(); // array로 변경해서 반환
arrayList.toArray(Object[] a); // runtime에서의 Type을 반영하여 array로 변경하여 반환
arrayList.clone(); // 현재 arrayList에 대해 swallow copy한 객체를 반환

---

ArrayList 장단점

장점

• 구조가 단순하며 데이터에 대한 접근이 쉽고 빠르다.

단점

• 크기가 변경되는 경우 새로운 배열을 생성하고 데이터를 복사해야 하기에 느리다.
• 끝이 아닌 index에 대한 요소의 추가나 삭제에 대해서는 많은 데이터를 옮겨야 한다.

---

구현

List 인터페이스

/**
 * 자바 List Interface<br>
 * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현합니다.
 *
 * @param <E> the type of elements in this list
 */

public interface List<E> {
    /**
     * 리스트에 요소를 추가
     *
     * @param element 리스트에 추가할 요소
     * @return  리스트에서 중복을 허용하지 않은 경우 리스트에 이미 중복되는
     *          요소가 있는 경우 {@code false}를 반환하고, 중복되는 원소가
     *          없을 경우 {@code true}를 반환
     */
    boolean add(E element);

    /**
     * 리스트에 요소를 특정 위치에 추가합니다.
     * 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
     *
     * @param index  리스트에 추가할 특정 위치
     * @param element 리스트에 추가할 요소
     */
    void add(int index, E element);

    /**
     * 리스트의 index 위치의 요소를 제거합니다.
     *
     * @param index 리스트에서 삭제할 요소의 위치
     * @return 삭제한 요소를 반환
     */
    E remove(int index);

    /**
     * 리스트에서 특정 요소를 삭제합니다.
     * 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
     *
     * @param element 리스트에서 삭제할 요소
     * @return 리스트에서 삭제할 요소가 없거나 삭제 실패시 {@return false}
     *         삭제에 성공할 경우 {@return true}
     */
    boolean remove(Object element);

    /**
     * 리스트에서 index 위치의 요소를 반환합니다.
     *
     * @param index 리스트에서 접근할 위치
     * @return 해당 index의 요소
     */
    E get(int index);

    /**
     * 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
     *
     * @param index 값을 수정할 위치
     * @param element 새로 대체할 값
     */
    void set(int index, E element);

    /**
     * 특정 요소가 리스트에 있는지 확인합니다
     *
     * @param element
     * @return 리스트에 특정 요소가 존재하는 경우 {@code true}
     *          존재하지 않는 경우 {@code false}
     */
    boolean contains(Object element);

    /**
     * 리스트에 특정 요소가 위치한 위치를 반환합니다
     *
     * @param element
     * @return 리스트에 처음으로 element와 일치하는 index를 반환하고 없다면 -1를 반환
     *
     */
    int indexOf(Object element);

    /**
     * 리스트에 들어있는 요소의 개수를 반환합니다.
     *
     * @return 리스트에 들어있는 요소의 수 를 반환
     */
    int size();

    /**
     * 리스트가 비어있는지 여부를 반환합니다
     *
     * @return 리스트에 요소가 없는 경우 {@code false} 요소가 있는 경우 {@code true}
     */
    boolean isEmpty();

    /**
     * 리스트를 비웁니다.
     */
    public void clear();
}

 

ArrayList

import java.lang.reflect.Array;

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

    int capacity;
    private E[] array;
    int size;

    ArrayList(){
        capacity = 10;
        array = (E[])new Object[capacity];
        size = 0;
    }

    ArrayList(int capacity){
        this.capacity = capacity;
        array = (E[])new Object[capacity];
        size = 0;
    }

    public void expand(){  // 확장시 현재 capacity를 2배로 증가
        capacity *= 2;
        E[] tmp = array;
        array = (E[])new Object[capacity]; // 단점!! 확장시 새로운 배열 생성해서 복사
        copy(tmp, array); 
    }

    public void copy(E[] origin, E[] target){
        for(int i = 0; i < origin.length; i++){
            target[i] = origin[i];
            origin[i]= null;
        }
    }

    public void addFirst(E element){
        if(size >= capacity){
            expand();
        }
        for(int i = size-1; i >= 0; i--){
            array[i+1] = array[i];
        }
        array[0] = element;
        size++;
    }

    public void addLast(E element){
        if(size >= capacity){
            expand();
        }
        array[size++] = element;
    }

    @Override
    public boolean add(E element) {
        addLast(element);
        return true;
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }else if(size >= capacity){
            expand();
        }
        if (size == 0) {
            addFirst(element);
            return;
        }else if(size == capacity - 1){
            addLast(element);
            return;
        }else {
            for (int i = size - 1; i >= index; i--) {
                array[i + 1] = array[i];
            }
            array[index] = element;
            size++;
        }
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        E data = array[index];
        for(int i = index + 1; i < size; i++){
            array[i-1] = array[i];
        }
        array[size-1] = null;
        size--;
        return data;
    }

    @Override
    public boolean remove(Object element) { 
        int idx = indexOf(element);
        if(idx == -1){
            return false;
        }
        remove(idx);
        return true;
    }

    @Override
    public E get(int index) { // 임의 접근
        return array[index];
    }

    @Override
    public void set(int index, E element) {
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        array[index] = element;
    }

    @Override
    public boolean contains(Object element) {
        boolean isExist = indexOf(element) != -1 ? true : false;
        return isExist;
    }

    @Override
    public int indexOf(Object element) {
        int idx = -1;
        for(int i = 0; i < size ; i++){
            if(array[i].equals(element)){
                idx = i;
                break;
            }
        }
        return idx;
    }

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

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

    @Override
    public void clear() {
        for(int i = 0; i < size; i++){
            array[i] = null;
        }
        size = 0;
    }

    public ArrayList<? super E> clone() throws CloneNotSupportedException{
        ArrayList<? super E> clone = (ArrayList<? super E>) super.clone();
        clone.array = (E[]) new Object[capacity];
        for(int i = 0; i < size; i++){
            clone.array[i] = this.array[i];
        }
        return clone;
    }

    public Object[] toArray(){
        Object[] result = new Object[size];
        for(int i = 0; i < size; i++){
            result[i] = array[i];
        }
        return result;
    }

    public <E> E[] toArray(E[] a){
        if(a.length < size){
            a = (E[]) Array.newInstance(a.getClass().getComponentType(),size);
        }
        Object[] result = a;
        for(int i = 0; i < size; i++){
            result[i] = array[i];
        }
        return a;
    }
}