# 배열 (Array & ArrayList)

정의

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

논리적 저장순서와 물리적 저장순서가 일치합니다.
데이터를 삽입하여 모든 공간이 꽉 차게 되면 새로운 메모리 공간을 할당받아 옮겨야 합니다.

# 데이터 접근 속도

인덱스를 사용하여 빠르게 접근하므로 시간 복잡도는 O(1)입니다.
Random Access(직접 접근)가 가능하며, 저장된 순서대로 검색해야하는 순차 접근과 반대의 개념입니다.

# 데이터 삽입&삭제 속도

데이터를 삽입 및 삭제 할 때, 이후의 데이터를 Shift해야 하므로 추가 과정이 필요하고 O(N)의 시간이 걸립니다.

# 메모리 할당

메모리에는 Array가 선언되자 마자 Compile time에 할당됩니다.
정적 메모리 할당이라고 합니다.

# 배열은 이때 사용해야해!

배열은 인덱스에 해당하는 원소를 빠르게 접근하거나 간단하게 데이터를 적재할 때 사용합니다.
index가 존재하기 때문에 위치를 바로 알 수 있어 검색이 빈번하게 발생할 때 사용합니다.

# 배열은 이때 사용하면 안돼!

계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합 합니다.
데이터의 삽입과 삭제가 빈번할 때도 비효율적입니다.
(이거 다 해결한게 LinkedList)

# 자바에서의 Array

int[] odds = {1, 3, 5, 7, 9};
String[] weeks = {"월", "화", "수", "목", "금", "토", "일"};

배열의 길이가 고정되어 있습니다.
자주 만나는 오류는 ArrayIndexOutOfBoundsException로 배열 밖의 범위를 참조했을 때 발생합니다.

# 자바에서의 ArrayList

같은 표현이에요!

ArrayList == Dynamic Array

import java.util.ArrayList;

public class Sample {
    public static void main(String[] args) {
        // 배열 만들기
        ArrayList<String> array = new ArrayList<>();
        
        // 삽입하기
        array.add("138");
        array.add("129");
        array.add("142");
        
        // 추출하기
        array.get(1);
        
        // 배열의 크기 가져오기
        array.size();

        // 해당 항목이 있는지 확인하기
        array.contains("142");
        
        // 삭제하기
        array.remove("129"); // 객체로 삭제
        array.remove(0); // 인덱스로 삭제
    }
}

저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량이 늘어납니다.
인덱스를 가지고 있어 데이터 검색에 적합하고 속도가 빠르며(O(1)), 삽입 삭제 시의 속도는 느립니다.(O(n))
동기화를 지원하지 않아 Vector보다 빠릅니다.

# ArrayList 동기화 시키기

List list = Collections.synchronizedList(new ArrayList(...));

# Array를 ArrayList로 변경하기

import java.util.ArrayList;
import java.util.Arrays;

public class Sample {
    public static void main(String[] args) {
        String[] data = {"138", "129", "142"};
        ArrayList<String> pitches = new ArrayList<>(Arrays.asList(data));
        ArrayList<String> pitches = new ArrayList<>(Arrays.asList("138", "129", "142"));
    }
}

# ArrayList를 정렬하기

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Sample {
    public static void main(String[] args) {
        ArrayList<String> pitches = new ArrayList<>(Arrays.asList("138", "129", "142"));
        pitches.sort(Comparator.naturalOrder());  // 오름차순(순방향) 정렬
        pitches.sort(Comparator.reverseOrder());  // 내림차순(역방향) 정렬
    }
}

리스트의 sort 메소드는 Java 8 버전부터 사용가능합니다.

# 참고자료

← 시간복잡도와 공간복잡도 연결 리스트 (Linked List) →