Introduction

What is Data Structure? 🤷🏻‍♂️

Data Structure(자료구조)란

• 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법
• 자료 구조의 종류에는 여러 종류가 있지만, 모든 목적에 부합하는 자료구조는 없다.
• 각 자료구조가 갖는 장점과 한계를 이해하여 상황에 맞는 올바른 자료구조를 선택하고 사용하는것이 중요하다.
• 자료구조는 언어별로 지원하는 양상이 다르다. (JS, Python...)
• 언어별로 지원하는 자료구조의 양상이 다르더라도 개념을 올바르게 이해한다면 해당 언어에 맞추어서 사용하기만 하면 된다.

데이터에 맞는 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼친다.

"코딩은 알고리즘과 자료구조, 이 두 가지로 이루어진다."
- Linus Torvalds

자료 구조의 분류

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

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

• Array(JavaScript), List(Python)
• Tuple
• Set
• Object(JS), Dictionary(Python)
• Stack & Queue
• Tree

Array(List)

Definition

• 자바스크립트에서는 Array(배열), 파이썬에서는 List 라고 부른다.
• Array(list)는 가장 기초적이고 단순하면서 가장 자주 사용되는 자료 구조이다.

  엄밀히 말하면 Array와 List는 다르다. 기능적으로는 거의 동일하지만 메모리 효율면에서는 Array가 유리하다.
  하지만 사용하기에는 List가 훨씬 편하다. (파이썬에서 Array를 쓰려면 따로 import Array해서 써야한다.)
  👉🏻파이썬에서 Array와 List의 차이

특징

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

• Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점이다.
• 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.
• Array는 주로 서로 연결된 데이터들을 순차적으로 저장할 때 사용한다.
• 순서가 상관없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용한다.

기타 특징

• 삽입 순서대로 저장된다. (새로 삽입되는 요소는 array의 마지막 요소가 된다.
• 자바스크립트에서는 Array.unshift("element to put in")과 같은 방식으로 배열의 앞에 넣어줄 수도 있다.
• 이미 생성된 리스트도 수정 가능하다.(mutable)
• 동일한 값도 여러번 삽입 가능하다. (중복 가능)
• element가 또 다른 array라면 다중차원 배열(Multi-dimensional Array)라고 한다.
  

Array 내부 구조

• Array의 구조는 위와 같고 데이터를 순차적으로 저장한다.
• 순서가 있기 때문에 Index번호로 각 순서에 해당하는 값을 찾아낼 수 있다.
• Index번호는 0부터 시작하고 마지막 요소는 -1이다.(끝에서 2번째 요소는 -2)

Array가 순차적으로 데이터를 저장하는 이유.

• 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• 데이터에 순서가 있기 때문에 index가 존재하고 그 index로 특정 요소를 읽는 것이 가능하고 index 번호를 이용하여 원하는 부분만 자르는 slicing도 할 수 있다.

Array의 단점

Array의 가장 큰 특징은 순서가 있다는 것이다.

Removing or Adding Elements

하지만 Array의 중간에 있는 요소를 삭제하려면 삭제된 공간으로부터 뒤에 있는 요소들을 모두 한칸씩 앞으로 당겨주어야 한다. (항상 메모리가 순차적으로 이어져야 하기 때문에)

• 위의 과정을 거치기 때문에 배열에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다.
• 실제 메모리 상에서 이루어지는 작업은 훨씬 커지게 된다.(expensive operation)
• 중간에 요소가 추가되는 과정도 동일하다.
• 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

Array Resizing

• Array의 사이즈를 다시 조정한다는 의미이다.
• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당한다.(pre-allocation)
• 처음 할당한 메모리 이상으로 많은 요소를 채우기 위해서는 resizing이 필요하다. (메모리 추가 할당)
• 추가적으로 할당된 메모리도 순차적이어야 한다.
• 배열의 resizing은 상대적으로 오래걸리는 operation이다.

예) 100개의 메모리 공간이 다 차서 100개를 추가해야하는 경우
1. 200개의 메모리를 생성
2. 기존 100개를 복사
3. 101번째부터 데이터가 순차적으로 추가

• resizing을 할 때는 위와 같은 과정을 거치기 때문에 사이즈 예측이 잘 안 되는 데이터를 다루기에는 적절하지 않다.
• 일반적으로 대부분의 프로그래밍 언어에서는 배열의 메모리 pre-allocation과 resizing을 자동으로 실행한다. 하지만 사이즈가 자주 늘어날 확률이 있는 데이터는 array 말고 더 적합한 자료구조를 선택해야 한다.

언제 사용하면 좋을까? 👀

• 순차열적인 데이터를 저장할 때 (주식 가격 : 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다 순서가 중요한 데이터)
• 다차원 데이터를 다룰 때 (Multi-dimensional Array)
• 어떠한 특정 요소를 빠르게 읽어야 할 때 (indexing)
• 데이터의 사이즈가 급격하게 자주 변하지 않을 때
• 요소가 자주 삭제 되거나 추가되지 않을 때

Tuple

Definition

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

python
>>> my_tuple = (1,"2",3.0)
>>> my_tuple
(1, '2', 3.0)
>>> for i in my_tuple:
...     print(i)
...
1
2
3.0
>>> my_tuple[0]
1
>>> my_tuple[1]
'2'
>>> my_tuple[2]
3.0
>>> my_tuple[0] = 9
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>>

Tuple Is Not For Every Language!
: Python 은 tuple이 있고 JavaScript는 없습니다. 그렇다고 Python > JavaScript 는 아닙니다! 다만 JavaScript에서는 tuple을 굳이 따로 안만든것 뿐입니다. Tuple은 list와 너무 비슷하기 때문에 굳이 제공하지 않는 언어도 많습니다. JavaScript에서는 그냥 array를 사용해도 상관없습니다.

Tuple의 장점

• Tuple은 간단한 값을 빨리 표현하고 싶을 때 많이 사용한다.
• 지도 좌표와 같은 여러 리턴값이 필요할 때

Python
// Tuple을 사용하는 경우
[(1,2), (2,4)] // Array(List) 안의 Tuple

// Tuple을 안 쓰는 경우에는 class를 생성해야함
class cord:
	def __init__(self, x, y):
		self.x = x
		self.y = y

Tuple의 단점

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

언제 사용해야 할까? 🤔

• 간단한 데이터를 표현할 때
  • 튜플이 리스트(배열)보다 더 가볍고 메모리를 더 적게 사용한다.