배열

• 연속된 메모리 주소를 할당받게 된다.
• index를 통해서 임의적으로 접근이 가능하다.
• 메모리 할당/해제 속도가 비교적 빠르다.
• 데이터 검색시 순차 탐색 또는 이진 탐색 등 다양한 방법으로 검색할 수 있다.

단방향 연결리스트

• 각 데이터가 노드 라는 단위로 구성되며 각 노드는 다음 데이터의 위치를 가지고 있다.
• 데이터 추가/삭제 시 메모리 할당/해제가 자유롭게 이루어진다.
• 메모리 할당/해제 속도가 비교적 느리다.
• 데이터 검색시 순차탐색만 가능하다.

CPU 캐싱의 관점에서

캐시 적중률

배열

• 연속된 메모리 공간에 데이터를 저장하기 때문에 캐시 적중률 가능성이 높다.
• 특히, 데이터 접근 패턴이 순차적일 경우 캐시 적중률이 더욱 높아진다.

단방향 연결리스트

• 데이터가 비연속적인 메모리 공간에 저장되어 있기 때문에 캐시 적중률이 낮을 가능성이 높습니다.
• 특히, 데이터 접근 패턴이 불규칙적일 경우 캐시 적중률이 더욱 낮아진다.

캐시 미스