1. Data Structure

자료 구조란?

• 데이터에 편하게 접근할 수 있도록 데이터를 저장하거나 조직하는 방법

• 각각의 환경에 적합한 자료 구조가 있으므로, 각 상황에 맞는 올바른 자료 구조를 선택하고 사용하는 것이 중요

• 사용 언어(JS, Python) 별로 지원하는 양상이 다르며, 사용 방법을 익히는 것 외에도 각 자료 구조의 컨셉을 이해하여 적절한 선택을 진행해야 함

  코딩은 알고리즘과 자료구조, 이 두가지로 이루어진다.
  - 리누스 토르발즈

분류

• 단순 구조 : 프로그래밍에서 사용되는 기본 데이터 타입
  (interger, float, string, boolean)

• 비단순구조 : 단순한 데이터를 저장하는 구조가 아닌 여러 데이터를 목적에 맞게 저장하는 자료 구조

  • 선형구조 : 저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues)
  • 비선형구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m

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

• Array(List in python), Tuple, Set, Dictionary, Stack&Queue, Tree

2. Array(List)

정의

• JS에서는 Array, Python에서는 List
  • 일반적으로 Python에서는 Array보다 List가 더 많이 사용되고 대부분 큰 차이가 없어 List를 사용해도 무방함
  • 기능적으로는 Array와 List는 거의 동일하며 메모리 효율면에서 Array가 유리하지만 사용하기에는 List가 훨씬 편함
    (Python에서 Array를 사용하기 위해서는 Array 모듈을 import해서 사용해야 함

특징

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

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

  • 순서가 없더라도 서로 연결된 데이터를 저장할 때 일반적으로 사용

• 삽입 순서대로 저장(새로 삽입되는 요소는 array의 새로운 꼬리가 됨)되며, 이미 생성된 리스트의 수정 및 동일한 값의 여러번 삽입이 가능

내부 구조

• Array 내의 element에는 순서가 있는데 이를 index라고 하며, 맨 앞의 index번호는 0.

• -[index]의 형태도 가능하며, -1은 맨 마지막 요소를 의미함

  왜 Array가 순차적으로 데이터를 저장할 수 밖에 없을까?

• 실제 메모리 상에서 데이터가 순차적으로 저장되기 때문임

  • 데이터에 순서가 있기 때문에
    1) index가 존재하며 : 0부터 시작하는 index
    2) indexing : index를 사용해 특정 요소를 array로 부터 읽어들이는 것이 가능
    3) slicing : 요소이 특정 부분을 분리하여 조작하는 것이 가능

단점 1. Removing or Adding Elements

• 순차적으로 담긴 데이터에서 중간의 요소가 삭제되는 경우, 뒤의 요소들은 앞으로 한칸씩 이동되어야 함

  • 이 말의 뜻은 array에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느려질 수 있다는 것을 의미

• 요소를 삭제하는 과정은 코드 상에서는 겨우 한 줄이지만, 실제 메모리상 작업은 훨씬 커지게 되며, 이는 중간에 요소를 추가하는 경우에도 동일한 의미를 가짐

• 즉, Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않음

단점 2. Array Resizing

• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생서될 때 어느 정도 메모리를 미리 할당
  (pre-allocation)

  • 메모리를 미리 pre-allocation함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장

• 하지만 요소들이 처음 할당한 메모리 이상으로 많아지면 그 이상으로 할당해야 하며(resizing) 추가적으로 할당된 메모리 또한 순차적이어야 함

• 배열을 resizing하기 위해 만약 100개의 메모리 공간이 다 할당되어 100개의 공간을 추가해야 하는 경우,
  1) 200개 크기의 메모리 생성
  2) 기존 100개 복사
  3) 101번부터 데이터가 순차적으로 추가

• 따라서, Array는 사이즈 예측이 잘 되지 않는 데이터를 다루기에는 적절치 않음

언제 사용해야 할까

• 순차적인 데이터를 저장할 때
• 다차원 데이터를 다룰 때
• 어떠한 특정 요소를 빠르게 읽어야 할 때
• 데이터의 사이즈가 급격히 변하지 않을 때
• 요소가 자주 삭제되거나 추가되지 않을 때

3. Tuple

Tuple이란?

• List와 마찬가지로 순차적으로 저장할 수 있는 자료 구조나,

  • 한 번 정의되고 나면 수정이 불가능하며, 2~3개 정도의 소규모 데이터를 저장할 때 주로 사용

장점

• 간단한 값을 빨리 표현하고 싶을 때 많이 사용
  (ex. 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우)

단점

• 데이터가 무슨 의미인지 명확하지 않아 데이터의 의미를 문맥을 보고 가정해야 함

  • 괄호 안에 데이터만 담겨 있기 때문에 문맥에 맞게 의미를 추출해야 함

언제 사용해야할까

• Array를 쓰기에는 간단한 데이터를 표현할 때 사용

  • Tuple이 Array보다 더 가볍고 메모리를 적게 차지 함