3.3 배열
배열은 같은 자료형의 다중 원소 집합을 표현합니다. 배열의 API(Application Programming Interface)는 다음과 같습니다.
• k번째 위치에 원소 삽입하기 상수 시간 O(1)에 k번째 위치에 값을 저장합니다. arr[k]에 값을 저장하기만 하면 됩니다.
• k번째 위치에서 값 읽기 상수 시간 O(1)에 k번째 위치에 저장된 값에 접근합니다. arr[k]에서 값을 읽기만 하면 됩니다.
• k번째 위치에 저장된 값 대체하기 상수 시간 O(1)에 k번째 위치에 저장된 값을 새 값으로 대체합니다.
배열은 고정된 크기라서 배열의 크기보다 많은 값을 저장할 수 없습니다. 더 많은 값을 저장하려면 값을 저장할 수 있는 충분한 공간이 있는 새 배열을 생성해 이전 배열에서 새 배열로 값을 복사합니다. 그런데 재할당과 복사 연산은 느립니다. 처음부터 더 큰 배열을 할당하는 방법이 있지만, 메모리가 낭비됩니다. 이 문제의 해결책이 연결 리스트입니다.