자료 구조에서 Array VS List

[Array (배열)]

배열이란, 같은 특성을 갖는 원소들이 순서대로 구성된 집합으로 #선형 자료 구조이다.
메모리 상에 연속적으로 데이터가 저장된 #연접 리스트(순차 리스트)에 해당하며
순차적으로 저장된 데이터를 #Index를 사용하여 관리한다.

[특징]

#1. 데이터를 index로 관리한다.
> 데이터에 접근이 빈번할 경우, 효율이 높다.
> 연속적인 만큼 인덱스를 통해 random access가 가능하다.

#2. 연속된 메모리의 공간으로 이루어져 있다.
> 논리적 저장 순서(#Index)와 물리적 저장 순서(메모리 주소)가 일치한다.

#3. 고정된 크기를 갖는다.
> ex) 생성할 때 배열 크기를 10으로 지정하여 생성하고,
해당 배열에 실제 데이터 5개를 넣어도 메모리에서 차지하는 크기는 10 이다.
-> 할당되지 않은 공간으로 인해 데이터 낭비가 발생할 수 있음.

#4. #Cache Hit Rate가 높다.

> ** Cache Hit Rate **
CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우를 말한다.
메모리의 특성 중 '참조 지역성 원리' 라는 것이 있는데,
동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스 되는 특성으로,
배열은 메모리 상 연속적으로 데이터가 저장되어 있어,
공간 지역성이 좋아 높은 #Cache Hit Rate를 가짐

[List(리스트)]

#자료 구조의 관점으로 보면 배열 또한 리스트에 포함되지만,
#프로그래밍 언어의 관점으로 보면 리스트란,
배열이 가진 인덱스 관리의 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 인터페이스 이다.

리스트는 LinkedList, ArrayList 등의 #선형 자료 구조를 구현할 때 사용되는 #추상 자료형 이다.
하지만 데이터가 메모리 상에 연속적으로 저장되진 않기 때문에 #순차 리스트가 아닌 #연결 리스트라 불린다

즉 보통의 Array와 List의 차이를 묻는 것은,
"리스트는 선형 자료 구조를 구현할 때 사용되는 인터페이스" 보다는
"리스트는 LinkedList처럼 모습이 확정된 자료 구조"라고 생각하고 대답하는 것이 낫다.

[특징]

#1. 데이터를 인덱스로 관리하지 않는다.

#2. 불연속적으로 메모리 공간을 차지
> 실제 메모리 주소 랜덤
ex) int형 자료가 배열 혹은 리스트로 저장되어 있다고 가정.
배열의 각 원소 주소는 100, 104, 108, 112 => 연속적인 주소.
리스트의 각 원소 주소 100, 204, 308, 412 => 비 연속적 주소

#3. 크기가 가변적이다.

#4. #Cache Hit Rate가 낮다.

** Cache Hit Rate **
CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우를 말한다.
메모리의 특성 중 '참조 지역성 원리' 라는 것이 있는데,
동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스 되는 특성으로,
List는 메모리 상 불연속적으로 데이터가 저장되어 있어,
공간 지역성이 좋지 못해 낮은 #Cache Hit Rate를 가짐

5. 메모리의 재사용이 편리하다.
-> Garbage Collector에 의해 메모리가 관리되어 삭제 후 확보된 공간을 재사용될 수 있다.

[ Array 와 List의 차이점 정리 ]

1. 데이터 관리를 #인덱스로 하느냐, 아니냐
2. 데이터가 메모리 공간에 #규칙적 or #불규칙적으로 위치
3. 크기가 #고정 or #가변
4. Cache Hit Rate가 높다 or 낮다
5. Array : #순차 리스트, List : #연결 리스트

Array VS List

	저장 방식	크기 할당	속도
Array (배열)	정해진 공간이 있고, 그 모든 곳에 인덱스가 존재.	객체 생성 시 크기 할당 필수	추가/삭제 : 느림 데이터 조회 : 빠름
List (리스트)	인덱스가 없고, 앞의 요소가 삭제되면 새로 추가되는 요소가 그 공간에 저장될 수 있음.	객체 생성 시 크기 할당 필요 X 알아서 늘어남.	추가/삭제 : 빠름 데이터조회 : 느림