배열(Array) & 배열 리스트(ArrayList) & 연결 리스트(LinkedList) & 벡터(Vector)

배열(Array)

배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.

일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 인덱스가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조로, 기본적인 용도 외에 다른 복잡한 자료 구조들을 표현하기 위해서 또는 행렬, 벡터 등을 컴퓨터에서 표현하는 용도 등으로도 사용된다.

배열의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기본 주소 또는 기본 주소라고 한다.

사이즈가 10인 배열 할당 시

장점

1. 인덱스를 통해 접근하기 때문에 시간 복잡도가 O(1)이다.
2. 데이터의 크기가 고정적일 때, 배열을 이용하면 메모리 사용량이나, 처리 속도면에서 좋다.
3. 구현이 쉽다.

단점

1. 크기가 고정적이다.
   • 배열 초기화 시 설정한 크기 안에서만 값을 저장할 수 있다.
2. 삽입/삭제가 오래 걸린다.
   • 실제로 메모리 공간을 삽입/삭제해 배열 사이즈를 변동시킬 경우, 연속적으로 구성되어야 하기 때문에 중간에서 삽입/삭제가 일어나면 이후에 있는 데이터를 뒤로 미루거나 앞으로 당기는 과정이 생겨 느리다.
3. 인덱스를 모르면 값을 찾기 힘들다.

---

배열 리스트(ArrayList)

일반적으로 배열은 length라는 변수만을 제공하는 참조 타입(Reference Type)이다.

이 배열을 기반으로 List라는 인터페이스를 상속해 구현한 것이 배열 리스트(ArrayList)이다.

일반적으로 크기가 유동적이며 빈틈없이 메모리를 사용하는 특성을 가진다.

(하지만, 내부적으로는 배열을 이용하기 때문에, 깊게 보면 배열의 장단점을 그대로 가진다. 사용하는 입장에서 이를 모르게 해 놨을 뿐이다.)

Java 컬렉션 프레임워크 구성도

삽입/삭제가 일어나면 내부적으로 크기를 변경시키는데, 이 변경하는 과정은 배열에서 설명한 것처럼 변경이 일어난 위치 이후의 데이터를 밀거나 당긴다.

ArrayList.java

다음은 Java 11의 ArrayList.java의 일부이다.

    // 기본 사이즈는 10이다.
    private static final int DEFAULT_CAPACITY = 10;
    ...
    // add() 내부 구조
    public boolean add(E e) { // 외부에서 add() 호출
        modCount++;
        add(e, elementData, size); // 내부용 add()로 이동
        return true;
    }

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length) //현재 사이즈가 elementData라는 실제 값이 저장되는 배열 사이즈에 도달하면
            elementData = grow(); //grow()를 통해 elementData 사이즈를 키운다.
        elementData[s] = e;
        size = s + 1;
    }

    private Object[] grow(int minCapacity) { //새로운 사이즈 배열에 기존 값을 복사한다
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1); //최소 현재보다 1 커져야함.
    }

    private int newCapacity(int minCapacity) {
        int oldCapacity = this.elementData.length;
        // 기존 리스트 길이 + (기존리스트길이/2)
        // 길이가 부족할 경우 1.5배 길이를 늘린다
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) { // 늘려도 부족하면 minCapacity만큼 늘림
            if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //기존 데이터가 없을 경우
                return Math.max(10, minCapacity);
            } else if (minCapacity < 0) { // 오버플로우
                throw new OutOfMemoryError();
            } else {
                return minCapacity;
            }
        } else {
            return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
        }
    }

    public void add(int index, E element) { // 중간에 삽입하는 add()
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        // index 이후 데이터가 복사되어, 한 칸 뒤로 밀리는 것을 알 수 있다.
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

---

연결 리스트(LinkedList)

연결 리스트는 달리 노드(Node)와 포인터(Pointer) 개념을 이용해 데이터를 저장한다.

따라서, 배열과 달리 비연속적일 수 있으며, 이에 인덱스 개념이 없다.

장점

1. 크기가 유동적이다.
2. 삽입/삭제가 빠르다.
   • 포인터가 가리키는 주소만 변경하면 되기 때문

단점

1. 데이터 조회 성능이 느리다. 시간 복잡도는 O(N)이다.
   • 첫 데이터(head)부터 포인터를 통해 순차적으로 조회하기 때문
2. 포인터를 활용해 다음 데이터를 가리키므로 추가적인 메모리 공간이 필요하다.
   • Java에서는 Node 클래스 사용

LinkedList.java

다음은 Java 11의 LinkedList.java의 일부이다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

transient Node<E> first; //첫번째 노드
transient Node<E> last; //마지막 노드
...

// add()는 기본적으로 마지막 노드에 연결함
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 중간에 add()할 경우
public void add(int index, E element) {
    checkPositionIndex(index); //정상 index인지 판단

    if (index == size) //index가 size(마지막 노드 + 1)이면 마지막에 저장
        linkLast(element);
    else //index 이전 노드에 현재 element 연결
        linkBefore(element, node(index));
}

//노드 순차 탐색
Node<E> node(int index) {
    // assert isElementIndex(index);

	// 빠르게 찾기 위해 index가 현재 사이즈/2를 기준으로 작은지 큰지 확인
    if (index < (size >> 1)) { //작다면, 앞쪽과 가까우므로 앞쪽부터 탐색
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { //크다면, 뒷쪽과 가까우므로 뒷쪽부터 탐색
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

void linkBefore(E e, Node<E> succ) { //succ : 기존 노드
    // assert succ != null;
    final Node<E> pred = succ.prev; //succ 이전 노드를 pred에 임시 저장
    final Node<E> newNode = new Node<>(pred, e, succ); //pred -> e -> succ 순인 추가될 노드
    succ.prev = newNode; //succ 이전 노드를 추가될 노드로 변경
    if (pred == null) //이전 노드가 없다면 e가 첫 노드임
        first = newNode; 
    else
        pred.next = newNode; //pred의 다음 노드를 추가된 노드로 변경
    size++;
    modCount++;
}

---

벡터(Vector)

C++에서 배열 대신 벡터를 많이 사용한다. (자바에서 ArrayList를 사용하는 이유와 동일하다.)

Java에서 벡터는 과거 컬렉션 프레임워크가 없던 시절 사용하던 레거시 클래스이다.

현재는 재구성되어 컬렉션 프레임워크와 완전히 호환된다.

배열 리스트와의 차이점은 동기화 유무이다. Thread Safe 해 한 번에 한 스레드만 접근 가능하다.

또한, 배열 리스트 경우 size를 1.5배 증가하지만, 벡터의 경우 2배 증가시킨다.

단일 스레드 프로그램이라면 ArrayList를 쓰는 게 바람직하다.

코드의 경우 synchronized 키워드가 붙어있는 점을 제외하고는 대부분 배열 리스트와 비슷하다.

Vector.java

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    
    //capacityIncrement는 Vector초기화 당시 설정한다. default는 0.
    //0보다 작다면 기존 용량만큼 증가한다. (2배)
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

 

---

Ref.

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

https://velog.io/@adam2/Array%EC%99%80-List%EA%B7%B8%EB%A6%AC%EA%B3%A0-Java-List

https://yeolco.tistory.com/94