Array(배열)와 List(리스트)

Array(배열)

---

 

Array(배열)이란?

---

• 여러 데이터를 그룹으로 관리하기 위하여 사용하는 자료구조
• 데이터들은 메모리 상에 연속적(논리적인 저장 순서와 물리적 저장 순서가 같음)으로 배치됨
  즉, 연속된 메모리 공간에 순서대로 저장된 데이터 그룹을 배열이라고 함
• 배열 내의 각 원소들은 유일무이한 고유의 인덱스 번호를 가지고 있음
  -> 원소의 인덱스 번호를 통해 해당 원소에 접근할 수 있음
• 처음 배열을 생성할 때 배열의 크기를 정해줌(pre-allocation).
  이 크기는 고정적이기 때문에 데이터를 몇 개를 집어넣느냐와 상관없이 처음 생성할 때 크기를 그대로 유지
• Cache Hit Ratio가 높음
  (※ Cache Hit Ratio: CPU가 요청한 데이터가 캐시 메모리에 있는 경우 캐시 적중(Cache Hit)라고 하며, 이 적중률을 Cache Hit Ratio라고 함)

 

배열의 장점

---

• 인덱스를 통해 특정 요소에 빠르게 접근할 수 있음
• 데이터를 연속적으로 관리하기 때문에 메모리 관리에 용이함
• 다차원 데이터를 다룰 때 용이함

 

배열의 단점

---

• 배열을 만들 때 정해놓은 크기를 변경하기 힘들다
• 데이터를 넣을 필요가 없어도 크기가 줄어들지 않기 때문에 메모리가 낭비될 수 있음
• 메모리 상의 연속된 구간에 배열을 할당해야 하기 때문에 할당에 제약이 생길 수 있음

 

 

 

List(리스트)

---

 

List(리스트)란?

---

• 순서가 있는 엘리먼트들의 모임
• 크기가 가변적이다. 때문에 배열처럼 고정적인 인덱스가 있는 데이터의 모임은 아님
  하지만 빈 공간을 허용하지 않는다는, 즉 빈틈없는 데이터 적재가 가능하다는 큰 장점이 있음
• 인덱스가 없는 것은 아니나, 배열에서처럼 유일무이하거나 고정적인 것은 아니며 순서를 확인하는 정도
• 불연속적으로 메모리 공간을 차지하기 때문에 인덱스가 아니라 포인터(다른 변수의 주소를 가지고 있는 변수)를 통해 원소에 접근
  또한, 이로 인하여 순차성 보장이 되지 않아 spatical locality(공간적 locality, 최근 참조된 메모리 주소와 가까운 메모리 주소가 계속 참조될 가능성이 높은 성질) 또한 보장되지 않기 때문에 Cache Hit Ratio가 낮음

 

리스트의 장점

---

• 동적으로 크기가 조절됨
• 메모리 관리와 재사용이 편리함
• 포인터를 통해 데이터의 위치를 가리키기 때문에 추가 삭제가 용이함

 

리스트의 단점

---

• 포인터 또한 값을 저장해놓는 변수이기 때문에 추가적인 메모리를 필요로 함
• 빈 엘리먼트를 허용하지 않기 때문에 검색 성능이 좋지 않음
• 인덱스의 중요도가 떨어지기 때문에 순차 탐색에 불리함

 

 

 

배열과 리스트 비교

---

 

 

 

참고

---

https://choheeis.github.io/newblog//articles/2020-12/data-structure-array

[자료구조] 1. Array(배열) | choheeis

https://github.com/Songwonseok/CS-Study/blob/main/DataStructure/Array&ArrayList&LinkedList.mdhttps://github.com/Songwonseok/CS-Study/blob/main/DataStructure/Array&ArrayList&LinkedList.md

GitHub - Songwonseok/CS-Study: 면접 대비 CS 스터디(+알고리즘)