[자료구조] 리스트(1).순차리스트(ArrayList)

리스트란?

일상 생활 속 "위시 리스트", "버킷 리스트" 등 리스트가 담긴 단어를 종종 사용한다.

위시리스트는 자신이 원하는 것을 목록으로 작성해둔 것이고, 

버킷 리스트는 자신이 해보고자 하는 것들을 목록으로 작성해둔 것이다.

자료구조의 리스트 또한 데이트의 목록을 의미한다.

 

리스트는 순차리스트(ArrayList)와 연결리스트(LinkedList) 2가지로 나뉘게 된다.

순차리스트(ArrayList)

순차리스트는 데이터들이 순서대로 메모리에 저장되는 자료구조이다.

즉, 논리적인 순서와 물리적인 순서가 동일한 구현 방식을 갖는다.

배열을 이용해 리스트를 구현한 것으로, 접근이 빠르다는 장점이 있다.

하지만 값을 추가하고 삭제하는데 있어서는 느리다는 단점 또한 존재한다.

삽입(add)

ArrayList의 내부로 들어가보면 add 함수는 다음과 같이 구현되어있다.

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

두번째 add 함수의 파라미터로는 (E e, object[] elementData, int s)를 받는데,

각각 다음과 같은 데이터이다.

• E e: 추가하고자 하는 데이터
• Object[] elementData: 데이터를 추가할 배열
• int s: 추가하고자 하는 인덱스

if문을 확인해보면 추가하고자 하는 인덱스랑 배열의 길이랑 같을 때 grow() 함수를 실행시키는데, 이에 대해 알아보면 다음과 같다.

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

현재 ArrayList가 비어있는지 확인한 후, 비어있다면, Default_CAPACITY와 minCapacity 중 큰 값으로 새로운 Object 배열을 생성한다.

비어있지 않은 경우, ArraysSupport.newLength 함수를 통해 새로운 크기의 배열을 복사해준다.

 

결론적으로는, 배열의 용량이 부족하다면 용량을 증가시킨 후 원하는 위치에 값을 넣을 수 있도록 구현되어있다.

삭제

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

/**
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
 
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

/**
 * Removes all of the elements from this list.  The list will
 * be empty after this call returns.
 */

우선 내장되있는 remove(Object o) 함수를 보면, 삭제하고자 하는 데이터를 찾으면 found를 빠져나오고, 못찾았다면 false를 반환하는 것을 알 수 있다. 

삭제할 값을 찾았다면 fastRemove 함수가 실행된다.

이 함수는 중간에 값을 삭제하는 경우, array 배열을 앞으로 한칸씩 옮겨주기 위해 System.arraycopy를 호출하여 array 배열을 바꿔주고 있다.

이후 마지막에 배열의 값을 null로 변경해준다.

 

이 외에도 다양한 ArrayList의 기능들이 있지만, 여기서는 add/remove에 대해서만 알아보도록 한다.