Data Structure (자료 구조)

• 자료 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법이다.
• 자료 구조의 종류에는 여러가지가 있다. 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고, 상황에 맞게 올바른 자료구조를 선택하고 사용하는 것이 중요하다.
• 자료구조는 언어별로 (ex. Javascript, Python등)지원하는 양상이 다르다.
• 각 자료 구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료 구조를 선택하는 것이 중요하다.

Why Data Structure?

• 자료구조는 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말한다. 화장품을 담기 위해 캐리어를 사용하는 것은 큰 수고를 불러오는 것처럼 말이다. 데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼친다.

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

일반적으로 많이 사용되는 자료구조

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

Array(List)

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

Array 특징

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

• Array의 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점이다.
• 자료구조에 저장하는 데이터는 일반적으로 요소라고 한다.
• Array는 주로 서로 연결된 데이터들을 순차적으로 저장 할 때 사용한다.
• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용된다.
• 삽입(insertion)순서대로 저장된다.
• 이미 생성된 리스트도 수정이 가능하다.
• 동일한 값도 여러번 삽입이 가능하다.
• Multi-dimentional Array(다중차원배열)
  - Array의 요소가 array가 될 수 있다.
  • A = [[11,12,13], [21,22,23], [31,32,33]]

Array 내부 구조

• Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것이다.
• 순서가 있다보니 당연히 순차적으로 번호를 지정할 수 있다.
• Index는 0부터 시작한다. index는 마이너스 부호를 가질 수도있다. 예를들어, -1은 맨 마지막 요소이다.

그렇다면 왜 Array가 순차적으로 데이터를 저장 할 수 밖에 없는가.

• 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• 데이터에 순서가 있기 때문이다.
  - index가 존재한다. (0부터 시작하는 index)
  • indexing : index를 사용해 특정 요소를 array(list)로 부터 읽어 들이는 것이 가능하다.
  • Slicing : 요소의 특정 부분을 따로 분리해 조작하는 것이 가능하다.

Array 단점

1. Removing or Adding Elements

• 중간의 특정 요소를 삭제해야 하는 경우를 보자.
• 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제 되는 경우에, 항상 메모리가 순차적으로 이어져 있어야 하기 때문에, 삭제된 요소로 부터 뒤에있는 모든 요소들을 앞으로 한칸씩 이동 시켜주어야 한다.
• 이것은 배열에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다는 뜻이다.
• 그렇게 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

2. Array Resizing

• Resizing이란, 말 그대로 사이즈를 다시 조정한 다는 뜻이다.
• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당한다. 이를 Pre-Allocation이라고 한다.
• 하지만 요소들이 처음 할당한 메모리 이상으로 많아진다면 Resizing이 필요하다. 즉, 메모리를 더 할당 해야 한다. 그리고 추가적으로 항당된 메모리 또한 순차적이어야 한다. 따라서 배열의 Resizing은 상대적으로 오래 걸리는 Operation이다.

예를들어, 100개의 메모리 공간이 다 차서 100개를 추가해야되는 경우

• 200개 크기의 메모리를 생성 후 -> 기존 100개를 복사하고 -> 다음 101번 부터 데이터가 순차적으로 추가된다.

• 그러므로 Array는 사이즈 예측이 잘 안되는 데이터를 다루기에는 적절하지 않다.

그렇다면 언제 Array를 사용하면 좋을까

• 순차열적인 데이터를 저장할때 (ex. 주식가격)
• 다차원 데이터를 다룰때
• 어떤 특정 요소를 빠르게 읽어야 할때 (index를 통해 바로 읽을수 있다.)
• 데이터의 사이즈가 급변하게 자주 변하지 않을 때
• 요소가 자주 삭제 되거나 추가되지 않을 때

Tuple

Tuple이란

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

Tuple의 장점

• tuple은 간단한 값을 빨리 표현하고 싶을 때 많이 사용한다. 예를 들면, 함수에서 리턴 값을 한 개 이상 리턴 하고 싶을 경우

Tuple의 단점

• Tuple의 단점은 데이터가 무슨 의미인지 명확하지 않다는 것이다. 데이터의 의미를 문맥을 보고 가정해야 한다. 그렇기 때문에 Tuple은 소규모 데이터를 다루기에 적합하다. (이러한 단점을 극복하기 위해 Named Tuple이란 것도 존재 한다.)

그렇다면 언제 사용하면 좋을까?

• Array(list)를 쓰기에는 간단한 데이터들을 표형할 때 사용한다.
• Tuple이 Array(List)보다 더 가볍고 메모리를 더 적게 먹는다.
  예를들어, 좌표 데이터 :

coordinations = [ (1, 2), (3, 4), (5, 6)]