Storing Elements in a Row

Backing Array


ArrayStack은 확보한 물리적 칸 수와 실제 원소 수를 따로 관리한다. 할당된 칸이라고 해서 모두 공개된 List 원소는 아니다.

a.length메모리에 확보한 전체 칸 수다.
n현재 List에 들어 있는 원소 수다.
유효한 ia.length(확보한 칸 수)가 아니라 0 ≤ i < n으로 정한다.

n은 List의 경계이고 a.length는 저장 공간의 경계다

a.length와 n을 따로 바꾸면 확보된 칸, 원소가 있는 칸, 아직 쓰지 않는 칸의 경계가 분리되어 보인다.

할당된 물리적 칸논리적 원소사용하지 않는 칸
a.length = 6할당된 칸 전체
n = 4논리적 원소
빈 칸 = 2아직 사용하지 않는 칸
초록 실선은 공개된 List 원소, 파란 점선은 메모리에 있지만 아직 List 원소가 아닌 칸이다.

n은 List의 경계이고 a.length는 저장 공간의 경계다. 두 값 사이의 칸은 존재하지만 get과 set의 대상은 아니다.

get과 set은 i < n인 칸 하나만 읽거나 바꾼다

같은 물리적 칸도 i < n일 때만 공개 연산이 허용된다. set은 값을 바꿔도 n과 a.length를 바꾸지 않는다.

연산
허용되는 접근

0 ≤ 2 < 4는 참이다.

a[2]에서 e를 읽는다.

초록 막대는 경계 검사를 통과한 접근, 빨간 막대는 거부된 접근이다.

get과 set은 경계 검사 뒤 정확히 한 칸만 읽거나 바꾼다. 사용하지 않는 칸을 선택하면 실제 칸이 보여도 IndexError가 된다.