자료 구조(Data Structure)란?
실세계에 존재하는 다양한 자료들을 프로그램이 효율적으로 처리될 수 있도록 컴퓨터상의 자료로 저장하거나 표현하는 기계적인 형태 또는 논리적인 구조
Array(배열)이란?
우선 배열이란 같은 성질을 갖는 항목들의 집합이다.
같은 특성을 갖는 원소들이 순서대로 구성된 집합으로 선형 자료 구조이며,
메모리 상에 연속적으로 데이터가 저장된 연접 리스트(순차 리스트)에 해당한다.
순차적으로 저장된 데이터를 참조하는 데에는 Index가 사용된다.
Array(배열)의 특징
- 고정된 크기를 갖는다.(데이터의 개수가 정해져 있다.)
- 배열의 크기를 10으로 지정한다면, 내부에 데이터가 5개만 있더라도
실제 배열의 크기는 10이다.(메모리가 낭비될 수 있다) - 논리적 저장 순서와 물리적 저장 순서가 일치하다. (메모리 상에 데이터도 순차적으로 저장된다.)
- 추가적으로 소모되는 메모리 양(오버헤드)이 거의 없다. (데이터의 양에 맞게 크기를 정해놓고 사용하기 때문)
- 삽입과 삭제의 경우 O(N)의 시간 복잡도를 갖는다.
- 원소에 접근할 때는 O(1)의 시간 복잡도를 갖는다.
- Cache Hit Rate 가 높다.
Cache Hit Rate?
Cache Hit이란 CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우를 말한다.
이 비율이 높을수록 좋은 성능을 가질 수 있다.
List(리스트)란?
자료 구조의 관점으로 보면 배열 또한 리스트에 포함되지만, 프로그래밍 언어의 관점으로 리스트란 배열이 가지고 있는 인덱스라는 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 인터페이스다.
보통 Array(배열)과 List(리스트)의 차이를 묻는 것은, "리스트는 선형 자료 구조를 구현할 때 사용되는 인터페이스다"라고 하기보단, 리스트를 LinkedList(연결 리스트)처럼 모습이 확정된 자료 구조라고 생각하고 대답하는 것을 요구한다.
List(리스트)의 특징 (LinkedList)
- 배열은 크기가 정해져 있고, 메모리 상에 데이터가 연속적으로 있어야 하기 때문에 메모리의 낭비가 발생할 수 있다.
- 하지만 리스트는 빈 공간을 허용하지 않기 때문에 이러한 메모리의 낭비는 없다.
- 데이터들이 순차적으로 구성된 집합이지만, 일반적으로 데이터가 메모리 상에 연속적으로 있진 않다.(실제 메모리 주소 랜덤 => 따라서 Cache Hit Rate가 낮다.)
- 크기가 가변적이다.
- 원소에 접근할 때 O(N)의 시간 복잡도를 갖는다.
- 삽입과 삭제의 경우 O(N)의 시간 복잡도를 갖는다.
- 삽입, 삭제, 크기 등 해당 리스트를 사용하기 위한 다양한 속성과 메서드가 존재한다.
(기본 동작은 구현할 필요 없다.)
배열 => 메모리 상에 데이터가 연속적으로 저장
리스트 => 메모리 상에 데이터가 비연속적으로 저장
사부작ㅤ사부작