데이터 구조 Data Structure - #1 Intro, Array & Tuple

데이터 구조란? What is Data Structure?

• 자료 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법.
• 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료구조를 선택하고 사용하는 것이 중요!
• 자료구조는 언어별로 지원하는 양상이 다름

Data structure 의 개념 필요성

상황과 문맥에 맞게 데이트럴 담을 수 있는 적절한 도구를 선택하는 것은 중요하다. 예를들어 화장품을 담기위해 캐리어를 사용하는 것은 큰 수고를 불러오는 것처럼 데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼치기 때문이다.

자료구조의 분류

• 일반적으로 가장 자주 사용되는 자료구조로
  : Array, Tuple, Set, Dictionary, Stack & Queue, Tree

Array

• 자바스크립트에서는 Array 파이선에서는 List
• Array는 가장 기초적이고 단순하면서도 가장 자주 사용되는 자료구조이다.

특징

• Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점이다.
• 자료구조에 저장하는 데이터는 일반적으로 element요소라고 함
• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용.
• 삽입 순서대로 저장
• 이미 생성된 리스트 수정 가능(mutable)
• 동일한 값도 여러번 삽입 가능
• 다중 차원 배열 Multi-dimensional Array
  ex)

Array 내부 구조

• Array에는 index가 존재한다.
• index는 0부터 시작하지만 마이너스 부호를 가질 수 도 있다. 마이너스 index는 맨 마지막 요소부터 시작한다. 예를들어 -1은 맨 마지막 요소이다.

Array가 순차적으로 데이터를 저장할 수 밖에 없는 이유는?

실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문!

정리 : Array는 index가 존재하며 index를 사용해 특정 요소를 읽어들이는 것이 가능하고 요소의 특정 부분을 slicing 따로 분리해 조작하는 것이 가능하다.

Array가 순차적으로 존재하기 때문에 중간 요소를 삭제할 경우 뒤에 있는 요소들이 모두 앞으로 한칸씩 이동한다. 이는 데이터 상에서 무겁게 작동되며 중간에 요소를 추가하는 것 또한 마찬가지이다.

따라서 Array에는 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절치않다.

Array Resizing

Array는 배열 메모리가 순차적으로 채워지기 때문에 처음 생성될 때 어느정도 메모리를 미리 할당한다.

이를 pre-allocation이라고 한다.
메모리를 pre-allocation함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수있다. 하지만 이후 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요하고 메모리를 더 할당해야한다.

앞서 말했듯이 배열을 조작할 때 데이터상에서는 무겁게 작동되기 때문에 상대적으로 오래걸리기 마련이다.

과정을 살펴보면...
ex) 100개의 메모리 공간이 다 찼다! 100개 더 추가해야해!
200개 크기의 메모리를 생성 -> 기존의 100개 복사 -> 101번 부터 데이터가 순차적으로 추가...

때문에 Array는 예측이 잘 안되는 데이터를 다루기에 적절치않다.
사이즈가 급격하게 늘어날 확률이 높을 때는 array말고 더 적합한 자료구조를 찾는 것이 좋다.

Array 사용의 적절한 예시

• 순차열적인 데이터 저장 ex) 주식가격(어제와 오늘의 2만원이 다름>>값보다는 순서), 날짜별로 체크하는 인바디 수치...
• 다차원 데이터
• 특정한 요소를 빠르게 읽어야 할 때(index사용으로 곧바로 읽을 수 있음
• 데이터 사이즈가 급변하지 않을 때
• 요소의 삭제, 추가가 되지 않을 때

Tuple

• tuple이란 python에 존재하는 list와 마찬가지로 데이터를 순차적으로 저장할 수 있는 자료구조이다.
• 하지만 list와 다르게 한번 정의되고 나면 수정 불가능(immutable)
• 2-3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 사용
• 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 때 자주 쓰임

Tuple의 장,단점

장점 : 간단한 값을 빨리 표현하고 싶을 때, 함수의 리턴값을 한 개 이상 리턴하고 싶을 때(ex.지도 좌표)
단점 : 데이터가 무슨 의미인지 명확하지 않음, 데이터의 의미를 문맥을 보고 가정해야함.

따라서 소규모 데이터를 다루기에 적합하다.

Tuple 사용의 적절한 예시

• array(list)를 쓰기에는 간단한 데이터들을 표현할 때
• tuple이 array(list)보다 더 가볍고 메모리도 적게 먹음