1. Data Structure(자료구조)란?

• 자료구조는 자료의 표현과 그것과 관련된 연산이다.
• 자료구조는 일련의 자료들을 조직하고 구조화하는 것이다.
• 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이 가능하다.
• 자료구조에 따라 프로그램 실행시간이 달라진다.

2. 자료구조의 분류

• Primitive Data Structure : 프로그래밍에서 사용되는 기본 데이터 타입
• Non-Primitive : 여러 데이터를 목적에 맞게 저장하는 자료 구조.
  • Non-Linear(비선형구조): 자료의 관계가 1:n 또는 n:m
  • Linear(선형구조): 자료의 전후관계가 1:1

3. 자주 사용되는 자료구조들

1. Array or List

• 가장 기초적이고 단순하면서도 가장 자주 사용되는 자료구조이다.
• 특징:
  • 순차적으로 데이터를 저장. WHY? 실제 메모리 상에서 순차적으로 저장되기 때문이다.
  • 순차적으로 들어오기에 index값을 통해 원하는 순서에 있는 값을 바로 꺼내올 수 있다.
  • 이미 생성된 리스트 수정 가능
  • 동일한 값을 여러번 삽입 가능
  • 탐색 속도(O(N))
• 단점:
  • 요소를 삭제하면 삭제된 요소로부터 뒤에 있는 모든 요소를 하나씩 앞으로 이동시켜야해서 속도면에서 느릴 수 있다.
  • 미리 메모리를 할당해야 하는데 메모리 이상으로 요소가 많아지면 resizing 해야한다.

2. Tuple

• List와 마찬가지로 데이터를 순차적으로 저장할 수 있는 자료구조.
• 특징:
  • 수정 불가능
  • 주로 2~3개의 소규모 데이터를 지정할때 쓰인다.
  • 함수에서 리턴 값을 한개 이상 리턴하고 싶을때 자주 쓰인다.
  • List보다 가볍고 메모리를 더 적게 차지한다.

3. Set

• Array나 List와 같은 순열 자료구조이다.
• 특징:
  • 비순차적으로 데이터를 저장. WHY? 들어오는 값을 해쉬화를 통해 해쉬값에 해당하는 공간에 저장한다.
  • 이미 생성된 리스트 수정 가능
  • 동일한 값을 여러번 삽입 불가능, 삽입하면 하나의 값만 저장된다. WHY? 동일한 값을 동일한 해쉬값을 갖기 때문이다.
  • Fast Lookup이 필요할때 주로 쓰인다.
  • 탐색 속도(O(1))

4. Object or Dictionary

• Key-Value 형태의 값을 저장할 수 있는 자료구조
• 특징:
  • 특정 순서대로 데이터를 리턴하지 않는다
  • 수정 가능
  • Key 값 중복 불가능

5. Stack & Queue

• Stack: FILO(First in Last Out) 구조, 최신 내역이 먼저 나와야 하는 경우 또는 함수 호출시 주로 쓰인다
  

• Queue: FIFO(First in First Out) 구조, 맛집 예약 시스템 등에 쓰인다.
  

6. Tree

• 가장 대표적인 유형은 이진 트리 자료구조가 있다.

• 데이터의 저장의 의미 보다는 저장된 데이터를 효과적으로 탐색할 때 사용된다.(탐색 속도가 빠름)

• 탐색 속도: O(log N)