원소를 메모리에 일렬로 붙여 놓은 자료구조. 이 한 가지 사실에서 배열의 모든 성질이 따라 나온다. 원소들이 붙어 있으니 시작 주소 + 인덱스 × 원소 크기로 어느 원소든 한 번에 계산할 수 있다. 시작 주소가 1000번이고 int가 4바이트라면 4번 원소는 1016번이다. 대신 붙어 있어야 하니 중간에 하나를 끼우려면 뒤를 전부 밀어야 한다.
연산별 비용과 미는 방향
인덱스로 읽고 쓰는 것은 주소 계산으로 끝나니 O(1)이고, 맨 뒤에 붙이는 것도 밀 게 없으니 O(1)이다. 중간에 넣거나 빼면 뒤의 원소를 전부 한 칸씩 옮겨야 해서 O(N)이고, 값으로 찾는 것도 하나씩 봐야 하니 O(N)이다.
중간에 값을 끼울 때는 뒤에서부터 민다. 앞에서부터 옮기면 아직 옮기지 않은 값을 덮어써서 그 값이 뒤로 죽 복사된다.
for (int i = arrCount; i > index; i--)
arr[i] = arr[i - 1];
arr[index] = val;사소해 보이지만 직접 구현할 때 가장 많이 틀리는 지점이다. 지울 때는 반대로 앞에서부터 당겨온다.
연결 리스트와 갈리는 지점
인덱스로 접근하는 일이 많으면 배열, 중간에서 넣고 빼는 일이 많으면 연결 리스트다. 다만 연결 리스트도 그 자리를 이미 알고 있을 때만 O(1)이라, 실제로는 배열이 유리한 경우가 훨씬 많다.
고정 크기와 동적 배열
배열은 만들 때 크기가 정해진다. 꽉 찬 배열에 더 넣으려면 더 큰 배열을 새로 만들어 통째로 복사해야 한다. 그리고 배열 자체는 몇 칸이 실제로 쓰이는지 모른다. double[5]에 값을 셋만 넣고 length만큼 돌면 뒤의 두 칸이 0.0으로 딸려 나온다. 원소 개수는 따로 세어서 들고 다녀야 한다.
이 두 가지를 대신 해주는 것이 ArrayList 같은 동적 배열이다. 내부는 여전히 배열이라 시간복잡도는 같고, 다만 꽉 차면 알아서 더 큰 배열로 옮겨준다.
list.add(e); // 맨 뒤에 추가
list.remove(index); // 해당 위치 삭제, 뒤가 당겨진다
list.get(index); // O(1)
list.size(); // 실제 원소 수참조로 넘어가는 배열
배열이 참조형이라는 것도 걸린다. 메서드에 배열을 넘기면 같은 배열이 넘어가서, 메서드 안에서 값을 바꾸면 호출한 쪽에서도 바뀐다. 원본을 지키려면 clone()처럼 복사본을 만들어 넘겨야 한다. 얕은 복사와 깊은 복사와 같은 이야기다.