[Java] 컬렉션 프레임워크 와 배열, 리스트

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 한다.
자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.

배열

배열에서 인덱스 사용하면 매우 빠르게 자료를 찾을 수 있다.

데이터를 넣거나 뺄때 처음부터 찾는게 아니라 인덱스 번째의 주소 값을 정확하게 입력하여 찾아가면 바로 찾을 수 있고, 그렇기 때문에 인덱스를 이용하면 빠르게 찾을 수 있음

배열을 찾는 공식은 다음과 같다

배열의 시작 참조 + (자료의 크기 * 인덱스 위치)

만약 arr이라는 배열의 3번째 값을 찾는다고 했을때 공식을 적용하면 다음과 같다.
(배열은 0번째 부터 시작이기 때문에 3번째가 곧 2번째 인덱스)

arr[2] = x100(참조주소 예시) + (4byte(int) * 2) = 108

결론적으로 참조주소 x108에 arr배열의 3번째 값이 들어있는 것이다.
그렇기 때문에 한번의 연산으로 주소값을 찾아줄 수 있음으로 배열의 탐색 속도바 매우 빠르다는 것이다.

배열내부에 있는 값을 찾는것을 검색이라고 하며, 인덱스로 찾는것이 아니라 배열 내부에 있는 값을 찾아야 하기 때문에, 하나하나 찾아봐야한다.

결국 값을 찾기위해 배열의 크기만큼의 반복이 필요하다

빅오(O) 표기법

알고리즘의 성능을 분석할때 사용하는 수학적 표현 방식.

데이터 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다.

• O(1) : 상수 시간, 입력 데이터의 크기에 관계없이 알고리즘의 실행시간이 일정하다

• O(N) : 선형 시간 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.

• O(N^) : 제곱 시간, 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.

• (log N) : 로그 시간, 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.

• O(N log N) : 선형 로그 시간, 많은 효율적인 정렬 알고리즘들

빅오 표기법은 데이터 양 증가에 따른 성능의 변화 추세를 비교하기 위한 표기법

배열의 특징

데이터 추가의 방식 3가지

• 배열의 맨 첫번째에 추가
• 배열의 중간에 추가
• 배열의 마지막에 추가

맨 첫번째에 추가
배열의 맨 첫번째에 추가하는 행위는 맨 처음 배열을 찾는 시간 O(1)
이후 모든 배열이 한칸씩 뒤로 밀리기 때문에 O(n)의 시간복잡도를 가짐

중간은 O(n/2) 정도 걸리지만 평균연산을 제외하고 결론적으로 O(n) 으로 표기

마지막 배열에 추가는 이동하지 않고 배열의 길이를 사용하여 마지막 인덱스를 구하고 인덱스에 바로 접근하는 로직이 가능하기 때문에 O(n)의 복잡도를 가지기 때문에 가장 효율적이다.

배열은 가장 기본적인 자료 구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다.
하지만 이런 배열에는 큰 단점이 있다.

바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점이다.

예를 들어서 이벤트를 하는데, 누구나 이벤트에 참여할 수 있고, 이벤트가 끝나면 추첨을 통해서 당첨자를 정한다고 가 정해보자.

이때 이벤트에 참여하는 사용자를 배열에 보관한다고 가정하자.
사용자들은 실시간으로 계속 추가된다. 이때 넉넉하게 길이가 1000인 배열을 사용했는데, 예상보다 이벤트 참여자가 많아서 1000명을 넘게 된다면 더 많은 사용자 가 이벤트에 참여하지 못하는 문제가 발생한다.

그렇다고 처음부터 너무 많은 배열을 확보하면 메모리가 많이 낭비된다. 배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료 구조 가 있다면 편리할 것이다.

직접 구현하는 배열 리스트

제네릭을 사용해서 배열을 생성할때 new E[] 이런게 안되는 이유는, 제네릭을 사용해도 제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 생성자를 통해 필요한 타입의 객체를 생성하려 해도 타입 정보가 사라지기 때문에, 컴파일 오류가 발생한다. 이것이 자바의 제네릭의 한계이며 배열을 구현할 때도, new Object[]를 사용하는 이유가 이것 때문이다. 생성하지 못하기 때문에 모든 객체를 담을 수 있는 Object로 선언 후에, 제네릭으로 다운 캐스팅 해주는 것이다.

코드를 보면 내부에는 Obejct 배열로 존재하지만 get, set을 할때 제네릭 타입 변수로 다운 캐스팅 해서 반환하기 때문에 결국에는 타입 변수 배열로 사용할 수 있는 것이다.

package collection.array;  

import java.util.Arrays;  

public class MyArrayListV4<E> {  

    private static final int DEFAULT_CAPACITY = 5;  

    private Object[] elementData;  
    private int size = 0;  

    public MyArrayListV4() {  
        this.elementData = new Object[DEFAULT_CAPACITY];  
    }  

    public MyArrayListV4(final int initialCapacity) {  
        this.elementData = new Object[initialCapacity];  
    }  

    public int size() {  
        return size;  
    }  

    public void add(E e) {  
        if (size == elementData.length) {  
            grow();  
        }  
        elementData[size] = e;  
        size++;  
    }  

    //코드 추가  
    public void add(int index, E e) {  
        if (size == elementData.length) {  
            grow();  
        }  
        shiftRightFrom(index);  
        elementData[index] = e;  
        size++;  
    }  

    private void grow() {  
        int oldCapacity = elementData.length;  
        int newCapacity = oldCapacity * 2;  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  

    //코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기  
    private void shiftRightFrom(int index) {  
        for (int i = size; i > index; i--) {  
            elementData[i] = elementData[i - 1];  
        }  
    }  

    public E get(int index) {  
        return (E) elementData[index];  
    }  

    public E set(int index, E element) {  
        E oldValue = get(index);  
        elementData[index] = element;  
        return oldValue;  
    }  

    //코드 추가  
    public E remove(int index) {  
        E oldValue = get(index);  
        shiftLeftFrom(index);  
        size--;  
        elementData[size] = null;  
        return oldValue;  
    }  

    //코드 추가, 요소의 index부터 마지막까지 왼쪽으로 밀기  
    private void shiftLeftFrom(int index) {  
        for (int i = index; i < size - 1; i++) {  
            elementData[i] = elementData[i + 1];  
        }  
    }  

    public int indexOf(E o) {  
        for (int i = 0; i < size; i++) {  
            if (o.equals(elementData[i])) {  
                return i;  
            }  
        }  
        return -1;  
    }  

    @Override  
    public String toString() {  
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +  
                size + ", capacity=" + elementData.length;  
    }  
}

노드와 연결

ArrayList의 단점

배열은 배열의 크기를 미리 확보해야 된다. 데이터가 얼마나 추가될 지 예측할 수 없는 경우 나머지 공간은 사용되지 않고 낭비가 된다.

배열의 중간에 데이터를 추가하면 공간 확보를 위해 기존 데이터들을 밀어내야 된다. 그래서 성능이 좋지 못하다. O(n)

낭비되는 메모리 없이 필요한 만큼만 메모리를 확보해서 사용하고, 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조가 있는데 노드를 만들고 각 노드를 연결하는 방식이다.

연결 리스트와 빅오

LinkedList는 get의 복잡도가 높다
index값을 알아도 Node로 연결되어 있고 O(n)으로 사용되기 때문에 시간 복잡도가 좋지 못하다.

add도 O(n)의 복잡도를 가진다. 마지막 노드까지 접근하는데 처음부터 쭉 뒤로 봐야되기 때문.

찾는 로직은 대부분 O(n)의 복잡도를 가진다.

하지만 LinkedList의 맨 첫번째에 추가하는 것은 복잡도가 O(n)이다.

LinkedList는 자체적으로 인덱스를 가지는 배열이 아니다 각 Node들은 자기가 몇번째 인덱스인지 모른다.

만약 첫번째에 값을 넣어준다면 List의 Node first의 값을 새로운 Node로 변경하고 두번째 인자인 Node의 참조를 맨 첫번째에 넣어주면 된다.

ArrayList 와 LinkedList

대부분의 경우에 ArrayList가 빠르지만 배열의 앞에 추가할 일이 빈번하다면 LinkedList를 사용하면 효율적으로 사용이 가능하다.

자바 리스트

Collection -> List -> ArrayList, LinkedList 순으로 존재

Collection은 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다.
데이터를 리스트, 세트, 큐 등의 형태로 사용 가능

List Interface

컬렉션 프레임워크의 일부로, 객체들의 순서가 있는 컬렉션을 나타냄

ArrayList

• 배열을 사용해서 데이터를 관리한다.
• 기본 CAPACITY를 넘어가면 배열을 50% 증가한다.
• 10 15 22 33 49 이런 순으로 증가
• 메모리 고속 복사 연산을 사용한다
  • 배열의 요소 이동은 시스템 레벨에서 최적화 된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 System.arraycopy()를 사용한다.
  • 배열에 첫번째에 추가할 때 보통 shift로 한칸씩 뒤로 밀어버리는데 고속 복사 연산은 시스템 레벨에서 0번째에 추가했을때 나머지 뒤에 부분을 한번에 복사해서 넣어버리기 때문에 일반 한 칸씩 이동하는 방식과다르게 속도가 월등히 빠르다.
  • 정확한 측정은 어렵다. 하드웨어 마다 속도가 다르기 때문에.

    LinkedList

• 자바가 제공하는 LinkedList는 이중 연결 구조를 사용한다. 이 구조는 다음 노드 뿐만 아니라, 이전 노드로도 이동할 수 있다.
• 역방향 조회도 가능하다.
• 인덱스로 조회하는 경우 전체 사이즈에서 절반 이상이라면 뒤에서 부터 찾으면서 성능 최적화가 이루어진다.