Data Structure - 01

Introduction

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)

Array 정의

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

Array 특징

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

Array 내부 구조

• Array는 순서가 있다보니 당연히 index를 지정할 수 있다.
• Array가 순차적으로 데이터를 저장할 수 밖에 없는 이유는 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• 데이터에 순서가 있기 때문에
  1) indexing을 통해 특정 요소를 array(list)로부터 읽어 들이는 것이 가능하고,
  2) Slicing을 통해 요소의 특정 부분, 즉 n번 째 index부터 m번 째 index까지 따로 분리해 조작하는 것이 가능하다.

단점

앞서 본 것과 같이 Array는 메모리의 실제 주소도 순차적으로 되어 있다.
그렇기 때문에 indexing이 가능하다는 장점이 있지만, 반대로 아래와 같은 단점이 존재한다.

1) Removing or Adding Elements

• 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제되는 경우, 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삭제된 요소로부터 뒤에 있는 모든 요소들을 앞으로 한칸 씩 이동시켜줘야 한다.
• 다시 말해서, 배열을 통해 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다는 것이다.
• 요소를 삭제하는 과정이 코드 상에서는 한 줄이지만, 실제 메모리 상 이루어지는 작업은 훨씬 커지는 것이다. (expensive operation)
• 중간에 요소가 추가되는 경우도 마찬가지로, 특정 위치에 새롭게 요소가 추가될 경우 그 뒤의 요소들이 하나씩 밀리게 된다.
• 그렇기 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

2) Array Resizing

• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당합니다. (pre-allocation)
• 메모리를 pre-allocation함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장하는 것인데, 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요하게 된다.
• 추가적으로 할당한 메모리 또한 순차적이어야 하며, 이에 따라 resizing 또한 상대적으로 오래 걸리는 operation이 된다.
  
• 때문에 Array는 사이즈 예측이 잘 안되는 데이터를 다루기에 적절하지 않다.
• 일반적으로 대부분의 언어에서는 배열의 메모리 pre-allocation과 resizing을 자동으로 실행한다. 하지만 이러한 점을 알고 있어야 사이즈가 급격하게, 빈번하게 늘어날 확률이 있는 데이터는 array가 아닌 더 적합한 자료구조를 선택할 수 있다.

사용하기 좋은 시점

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

2. Tuple

Tuple 정의

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

Tuple Is Not For Every Language!
: Python 은 tuple이 있고 JavaScript는 없다. 그렇다고 Python > JavaScript 는 아니며, JavaScript에서는 tuple을 굳이 따로 만들지 않았을 뿐이다. Tuple은 List와 비슷하기 때문에 굳이 제공하지 않는 언어도 많으며, JavaScript의 경우 그냥 array를 사용해도 상관없다.

장점

• Tuple은 간단한 값을 빨리 표현하고 싶을 때 많이 사용한다.
• 예를 들어 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우 (ex. 지도 좌표)
  -아래는 Tuple을 사용하는 경우와 class/object를 사용하는 경우의 비교이다.

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

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

단점

• Tuple의 단점은 데이터가 무슨 의미인지 명확하지 않다는 것이다.
• 데이터의 의미를 문맥을 보고 가정해야 한다.
  • 예를 들어 객체의 경우 key-value 쌍으로 이루어진 데이터이기 때문에 무슨 데이터인지 파악이 쉽지만, Tuple의 경우 괄호 안에 데이터만 담겨있기 때문에 문맥에 맞게 의미를 추측해야 한다.
• 그렇기 때문에 Tuple은 소규모 데이터를 다루기에 적합하다. (이러한 단점을 극복하기 위해 Python에 Named Tuple이란 것도 존재한다.)

사용하기 좋은 시점

• Array(List)를 쓰기에는 간단한 데이터들을 표현할 때 사용한다.
  • Tuple이 Array(List)보다 더 가볍고 메모리를 덜 사용하기 때문에다.
  • 예를 들어 좌표 데이터:

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