[CS] Array와 List의 차이

 

[자료구조] Array(배열) vs List(리스트)

(출처는 위 글임을 밝힌다.)

---

0. 결론

---

Array는 메모리 상에 데이터가 연속적으로 저장되고,
List는 메모리 상에 데이터가 비연속적으로 저장된다.

 

Array와 List의 차이를 묻는 것은 Array와 LinkedList의 차이를 묻는 것이 일반적이다.
Array와 List, 둘 모두 선형 자료구조*로 동일한 용도로 사용하기에, 둘의 차이를 모르고 사용하는 경우가 많지만, 프로그래밍의 성능을 높이기 위해선 적절한 자료구조를 사용하는 것이 좋다.

선형 자료구조: 원소들을 순서대로 나열한 집합
순차 리스트: 원소들이 실제 메모리 상 시작 위치부터 끝 위치까지 순차적으로 저장된 것
연결 리스트: 데이터가 메모리 상에 연속적으로 저장되지는 않지만, 서로 연결된 선형 자료구조

---

1. 배열과 리스트의 차이

---

구분	배열	리스트
크기	고정된 크기를 가짐 (선언 시 크기 지정, 변형 불가)	배열 크기가 고정되지 않음 (가변적)
저장 순서	논리적 / 물리적 저장 순서 일치	실제 메모리 주소는 랜덤
기억 장소	미리 확보해야 함	미리 확보하지 않아도 됨
삽입 / 삭제 시간복잡도	O(N)	O(N)
원소 접근 시간복잡도	O(1)	O(N)
장점	-  Cache Hit Rate가 높음 - 추가 사용하는 메모리(오버헤드) X	- 빈틈없는 데이터의 적재   (이러한 메모리의 낭비는 없음)
단점	- 배열 안 빈 데이터가 있을 수 있음   (메모리가 낭비될 수 있음)	- Cache Hit Rate가 낮음

Cache Hit: CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우
Cache Hit Rate: 배열은 메모리 상 연속적으로 데이터가 저장, 공간 지역성*이 좋아 높은 Cache Hit Rate를 가짐.

참조 지역성 원리: 동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스되는 특성, 지역성의 원리라고도 함.
1. 공간 지역성(Spacial Locality): 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성
2. 시간 지역성(Temporal Locality): 최근에 참조된 주소는 빠른 시간 내에 다시 참조되는 특성
3. 순차 지역성(Sequential Locality): 데이터가 순차적으로 액세스되는 특성, 공간 지역성에 편입되어 설명되기도 함.

---

2. 배열(Array)

---

---

 

원소 확인 및 변경

아래 배열에서 인덱스 3에 있는 7이란 데이터를 8로 변경한다고 하면,
배열은 메모리 상에 일렬로 나열되어있으니 배열 시작주소 + 3으로 O(1)만에 찾아서 변경할 수 있다.

원소 삽입 및 삭제

아래 배열에서 인덱스 3에 있는 7이란 데이터를 삭제한다고 하면, 인덱스 3에 있는 데이터를 삭제하여도,
배열은 메모리 상에 일렬로 나열되어있어야 하기 때문에 우측에 있는 데이터들이 한칸씩 땡겨진다.
따라서 삭제의 시간 복잡도는 O(N)이 되며, 삭제 연산을 위한 함수가 없으니 직접 구현해야 한다.

(삽입도 마찬가지이다.)

삽입과 삭제의 평균 연산 횟수를 N/2라고 했는데, 사실 인덱스 3의 위치에 삽입, 삭제를 한다면  "길이인 7 빼기 현재 인덱스 3의 순서 4를 빼서 뒤에 있는 3개만 땡기거나 밀면 되는 거 아니야? 7,8,9 인덱스에는 데이터 없잖아."라고 생각할 수 있다. 뒤에 7, 8, 9인덱스에 데이터가 있는지 없는지는 조상님이 알려주지 않는다.
즉 7, 8, 9에 데이터가 있는지 없는지 확인은 해야 하기 때문에 결국 길이가 아닌 크기로 계산하는 것이다.

---

3. 리스트(List)

---

---

원소 확인 및 변경

'소'를 '닭'으로 바꾸는 경우, 순차 접근 방식을 사용하기 때문에 처음부터 순차적으로 탐색해서 '소'를 찾아야 한다.
'소'가 있는 곳을 찾는 데에 평균적으로 O(N)의 시간 복잡도를 가지며, '닭'으로 변경하는 동작은 O(1)의 시간 복잡도이다.
결과적으로 O(N)의 시간 복잡도로 '소'의 데이터를 확인 및 변경할 수 있는 것이다.

원소 삽입 및 삭제

'소'를 삭제하는 경우, '소'가 있는 곳을 찾는 데에 O(N)의 시간 복잡도, '개'가 가리킬 다음 주소를 '양'으로 바꾸는 데 O(1),
결과적으로 O(N)의 시간 복잡도로 '소'의 데이터를 삭제할 수 있다. 또한, 리스트의 크기가 4로 줄었다(크기가 가변적). 

삽입도 마찬가지로 찾을 때 O(N), '양'이 '뱀'의 주소를 가리키도록 하는 데 O(1), 결과적으로 O(N)의 시간 복잡도를 갖는다.

---

ArrayList와 List의 차이

[C#] ArrayList와 List의 차이