Data Structure

📌 What You Will Learn
✔️Data Structure의 개념 필요성, 그리고 다양한 종류의 자료구조에 대해 이해한다.
✔️Array의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.
✔️Tuple의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.

Data Structure(자료 구조)란?

• 자료구조 : 데이터에 편하게 접근하고 조작하기 위한 데이터를 저장하거나 조작하는 방법을 말한다.
• 각각의 자료구조가 가진 장점과 한계를 이해하고 상황에 맞게 자료 구조를 선택하고 사용하는 것이 중요하다.
• 각 언어마다 가진 자료구조의 종류와 사용법이 다르기 때문에, 자료구조의 본질을 이해하는 것이 중요하다.

왜 자료구조를 사용하는가?

• 자료구조란 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말한다.
• 데이터에 맞는 적절한 자료 구조를 사용하는 것은 매우 중요하면서 전체 개발 시스템에 많은 영향을 끼친다.

자료 구조의 분류

• Primitive Data Structure(단순 구조)
  프로그래밍에서 사용되는 기본 데이터 타입

• None-Primitive Data Structure(비 단순 구조)
  단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조
  - Linear Data Structure(선형 구조)
     저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues)
  - Non-Linear Data Structure(비선형 구조)
     데이터 항목 사이의 관계가 1:n 또는 n:m (ex. Graphs, Trees )

자주 사용 되는 자료 구조

• Array(Python에서는 List)
• Tuple
• Set
• Dictionary
• Stack & Queue
• Tree

1.Array(List)

JavaScript에서는 Array, Python에서는 List

Array 특징

순차적으로 데이터를 저장하는 자료구조

• 순차적(ordered)으로 데이터를 저장한다.
• 자료구조에 저장하는 데이터를 일반적으로 요소(element)라고 한다.
• 주로 서로 연결된 데이터들을 순차적으로 저장할때 사용한다.

기타 특징

• 삽입(insertion) 순서대로 저장된다. (새로 삽입되는 요소는 array의 새로운 꼬리가 된다.)
• 이미 생성된 리스트도 수정 가능(mutable).
• 동일한 값도 여러번 삽입 가능.
• Multi-dimentional Array(다중차원 배열)
  Array의 요소가 array가 될 수 있다. 다중차원(multi-dimentional) array라고 한다.
  일반적으로 2D (2차원) array가 많이 사용된다.

Array 내부 구조

• 순차적으로 데이터를 저장하기 때문에 순차적으로 번호를 지정할 수 있다. (이 번호를 Index라고 한다)
• Index는 0부터 시작
  Index는 마이너스 부호를 가질 수도 있다. 마이너스 Index는 맨 마지막 요소부터 시작. (맨 마지막 요소는 -1)

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

• 물리적으로 데이터가 순차적으로 저장되기 때문
• 데이터에 순서가 있기 때문에
  Index가 존재: 0부터 시작하는 index
  Indexing: Index를 사용해 특정 요소를 array(list)로 부터 읽어 오는 것이 가능
  Slicing: 요소의 특정 부분을 따로 분리해 조작하는 것이 가능

단점

1. Removing or Adding Elements

• 순차적으로 담겨있는 데이터 중 중간 요소가 삭제 되는 경우에, 삭제 된 요소부터 뒤에 있는 모든 요소들은 앞으로 한칸씩 이동 해야 한다. (이 때문에, 배열에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다)
• 요소 삭제 과정이 코드에서는 한 줄이지만 실제 메모리에서의 작업(operation)은 훨씬 크다 -> expenxive operation
• 중간에 요소가 추가 되는 경우도 그 뒤의 요소들이 하나씩 밀리게 된다.

📌 그렇기 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

2. Array Resizing

• Resizing은 말 그대로 사이즈를 다시 조정한다는 뜻
• 메모리가 순차적으로 채워지기 때문에 배열이 생성될 때 메모리를 미리 할당 (pre-allocation)
• 요소가 처름 할당한 메모리 이상으로 많아지면 resizing이 필요 (메모리를 더 할당 해야 함)
• 추가적으로 할당된 메모리도 순차적이어야 한다.

- resizing은 상대적으로 오래 걸리는 operation
처음 배열에 100개의 메모리 공간을 만든 후, 100개의 메모리 공간이 다 차서 100개를 추가해야 되는 경우
200개 크기의 메모리를 생성 - 기존 100개의 메모리 복사 - 다음 101번 부터 데이터를 순차적으로 추가

• 그렇기 때문에 사이즈 예측이 잘 되지 않는 데이터를 다루기에 Array는 적절하지 않다.
• 일반적으로 대부분의 언어에서는 배열의 메모리 pre-allocation과 resizing을 자동으로 실행한다.
  하지만 사이즈가 급격하게 자주 늘어날 확률이 있는 데이터는 array 대신 더 적합한 자료구조를 선택해야 한다.

언제 사용하면 좋을까요?

• 순차적인 데이터를 저장할 때
  (ex. 주식 가격 / 어제의 금액과 오늘의 금액이 다름 - 값보다는 순서가 중요한 데이터)
• 다차원의 데이터를 다룰 때
  (Multi-dimensional Array)
• 특정 요소를 빠르게 읽어야 할 때
  (Index를 사용해 바로 읽을 수 있기 때문)
• 데이터의 사이즈가 급변하게 자주 변하지 않을 때
• 요소가 자주 삭제되거나 추가되지 않을 때