IT/CS
[CS/Data Structure] 2. 배열과 연결리스트 (Array & Linked List)
배열 배열의 특징 대표적인 선형 자료구조 가장 기본적인 자료구조 메모리에 연속적으로 데이터를 저장하는 자료구조로, 논리적 저장순서와 = 물리적 저장순서(일치) 탐색 O(1), 삽입/삭제 O(N) → 접근이 용이하며 데이터 삽입및 삭제가 어렵다. → 논리적 저장순서 = 물리적 저장순서이기에, 인덱스로 해당 원소에 접근할 수 있으므로 탐색시 O(1)로 접근 가능하다 ⇒ 즉, Random Access 가 가능하다는 장점이 있다 크기 고정적 Cache locality(정의 링크) 가 좋아 Cache Hit 가능성이 크다. 연결리스트 연결리스트의 특징 배열과 동일한 선형 데이터 자료구조이나, 연속적인 메모리 위치에 저장되지 않는다. (메모리가 불연속적으로 배치된 선형 자료구조) 연결 리스트에서 서로 연결된 원소(..
