배열과 연결 리스트

여러분, 자료구조의 출발점인 배열부터 시작해볼게요.

배열이 왜 가장 기본적인 자료구조인지, 그 원리를 알아야 다른 구조도 이해할 수 있어요.

슬라이드 위쪽 에이 패널, 메모리 레이아웃을 보세요. =10]

파란 칸 5개가 빈틈 없이 나란히 있죠. 10, 25, 37, 42, 58이에요.

이게 배열의 핵심입니다. 연속된 메모리 공간에 데이터를 빈틈 없이 나열하는 거예요.

각 칸 아래 주소를 보세요. 영엑스1000, 영엑스1004, 영엑스1008 순서로 올라가죠.

초록색 플러스 4비 화살표가 보이시죠? 정수 하나가 4바이트니까 주소도 4씩 증가합니다.

이 규칙적인 간격이 배열의 가장 강력한 무기를 만들어요.

비 패널의 주황색 공식 박스를 보세요. 주소 계산 공식이 있습니다.

에이디알 오브 에이알알 아이 이퀄 베이스 플러스 아이 곱하기 사이즈오브 엘리먼트.

예를 들어 에이알알 3은 영엑스1000 플러스 3 곱하기 4, 영엑스100씨가 되고 값 42에요.

CPU가 이 계산을 한 번에 수행하니까 접근 시간이 항상 오원이에요.

배열 크기가 5개든 5백만 개든 한 번의 산술로 끝납니다.

이제 씨 패널의 캐시 친화성을 보세요. 연속 메모리니까 CPU 캐시에 한 번에 올라갑니다.

64바이트 캐시 라인에 정수 16개가 한꺼번에 적재돼요.

첫 원소를 읽으면 주변 15개도 이미 캐시에 있으니 반복 접근이 엄청 빨라요.

이게 배열이 다른 자료구조보다 순회가 빠른 핵심 이유입니다.

디 패널을 보세요. 인덱스가 왜 0부터 시작하는지 나와 있어요.

에이알알 0이면 베이스 플러스 0 곱하기 4, 즉 베이스 주소 그 자체예요.

만약 1부터 시작하면 매번 아이 빼기 1을 계산해야 해서 뺄셈이 한 번 추가됩니다.

다익스트라가 이 점을 지적했고, 대부분의 언어가 0-based 인덱싱을 채택했어요.

정리하면, 배열은 연속 메모리 플러스 산술 한 번으로 오원 접근하는 가장 기본적인 구조예요.