[Data Structure 세션] 1. intro,Array&Tuple

자료 구조의 분류

Array(List)
1) Array?

• Javascript 에서는 Array, Python에서는 List
• Array는 가장 기초적이고 단순하면서도 가장 자주 사용 되는 자료 구조

2) Array 특징

• 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점
• 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.
• 서로 연결된 데이터들을 순차적으로 저장할 때 사용
• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용
• array가 가장 자주 사용되는 자료구조중 하나인 이유이다.
• 삽입 순서대로 저장
• 이미 생성된 리스트도 수정 가능
• 동일한 값도 여러번 삽입 가능
• multi-dimentional Array(다중차원 배열)
  : Array의 요소가 array가 될 수 있다.주로 2차원 array가 많이 사용 됨

3) Array 내부 구조

• 순차적으로 번호를 지정이 가능하다. (index)
• index는 0부터 시작한다.
• index -1값은 배열의 맨 마지막 요소이다.

4) Array는 왜 데이터를 순차적으로 저장할까?

• 실제 메모리 상에서, 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• indexing : index를 사용해 특정 요소를 array로 부터 읽어 들이는 것이 가능
• slicing : 요소의 특정 부분, 즉 n번째 부터 m번째 까지 따로 분리해 조작하는 것이 가능

Array 단점

1) Removing or Adding Elements

• 중간의 특정 요소를 삭제해야 하는 경우를 가정했을 때, 중간의 요소가 삭제 되는 경우, 삭제된 요소로 부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜줘야한다.
• 이 과정은 다른 자료 구조에 비해 느릴 수 있다.
• 요소를 삭제하는 과정이 코드 상에서는 한 줄 이지만 실제 메모리 상에서 이루어지는 작업은 훨씬 커진다.
• 중간에 요소가 추가 되는 경우도 마찬가지
• Array는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절치 않다.

2) Array Resizing

• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당한다.(=pre-allocation)
• 메모리를 pre-allocation함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있다.
• 하지만 요소들이 처음 할당한 메모리 이상으로 많아지면 resizing이 필요
• 즉 메모리를 더 할당해야 한다. 즉, 배열의 resizing은 상대적으로 오래걸리는 operation이다.
• 사이즈 예측이 잘 안되는 데이터를 다루기에 적절치 않다!

3) 언제 사용하면 좋을까?

• 순차열적인 데이터 저장할 때
• 다차원 데이터를 다룰 때 >> Multi-dimensional Array
• 어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
• 데이터의 사이즈가 급변하지 않을 때
• 요소가 자주 삭제, 추가되지 않을 때