자료구조: ch3) 순차적 자료구조: 배열과 리스트

배열

• 정의와 동시에 길이를 지정. 바꿀 수 없음.
• 여러 데이터를 하나의 이름으로 그루핑해서 관리하기 위한 자료구조
• index는 값에 대한 유일무이한 식별자(주민번호라 생각하면 편함) (리스트에서 인덱스는 몇 번째 데이터 인가 정도의 의미만 갖는다.)
• 논리적 저장 순서 = 물리적 저장순서
• 배열은 길이를 바꿀 수 없다. 가변 배열과 같이 길이가 변경 가능한 배열의 경우,

1. 기존의 배열은 그대로 냅둠.
2. 새로운 길이로 지정된 배열을 따로 할당 (메모리가 있는지 탐색 필요)
3. 데이터의 복사를 진행하고, 기존 배열을 삭제
   ->한계 해결 방안: linked list

리스트

• 배열이 갖고 있는 index라는 장점을 버림 but 빈틈없는 데이터의 적재가 가능
• 빈 엘리먼트는 허용 X
• 데이터 갯수가 확실히 정해졌고, 자주 사용된다면 array가 더 효율적.
• 용량(capacity) 자동조절 (Dynamic array)
  -> 파이썬에서 append를 할 때, 리스트의 용량이 자동조절되면서 새로운 엘리먼트가 추가된다.
• 리스트의 대표적 기능

1. 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능 (insert,del,pop...)
2. 리스트에 데이터가 있는지 체크하는 기능
3. 리스트의 모든 데이터에 접근하는 기능
   

(cf) C언어는 리스트 지원 X 배열 지원 O / Python은 리스트 지원 O 배열 지원 X

배열은 삭제된 데이터의 빈 공간을 그대로 남겨둔다 but 리스트는 빈공간을 채운다.

Reference
https://wayhome25.github.io/cs/2017/04/17/cs-18-1/