[ Algorithm ] 핵심 자료구조

1. 배열(Array)가장 기본적인 자료구조이며 여러개의 변수를 담는 공간으로 이해할 수 있다.배열은 인덱스(Index)가 존재하고 인덱스는 0부터 시작한다.특정한 인덱스에 직접적으로 접근이 가능하고 수행시간은 O(1)을 가진다. 장점: 캐시(cache) 히트 적중률이 높고 조회가 빠르다.단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이며 데이터의 추가 및 삭제에 한계가 있다. 캐시히트 적중률이란?CPU(클라이언트)에서 요청한 데이터가 캐시에 존재하여 이를 이행할 수 있을때 캐시 히트(Hit)라고 한다. Memory address0x00000x00040x0008Index012Value103070 2. 연결리스트(Linked List)연결 리스트는 메인 메모리상에서 주소가 연속적이지 않으며 배열과 다..

2023.06.26