[Data Structure] 자료구조, Array

자료구조

• 데이터를 편리하고 효율적으로 접근하고 조작하기 위한 방법.
• 각각의 자료구조가 갖는 장점과 한계들이 있기 때문에, 본질과 컨셉을 잘 이해하고 상황에 따라 올바르게 선택하고 사용해야 함.
• 데이터와 시스템의 상황에 맞는 적절한 자료구조를 사용하는 것이 시스템의 성능 등에 매우 큰 영향을 미침.

자료구조의 분류

• 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

Array(List)

• 대표적으로 배열(Array) 또는 파이썬은 List.

주요 특징

1) 장점

• 순차적으로 데이터를 삽입 및 저장. (실제 물리적으로 데이터가 저장됨)
• 그래서 구현과 접근이 쉽다.

2) 단점

• 중간요소를 추가, 삭제하고 나면 삭제된 요소로부터 뒤에 있는 모든 요소들을 앞으로 한 칸씩 이동시켜야 함. 실제 메모리 상에 하는 작업이 많기 때문에 Expensive한 Operation이 된다.
  
• 그래서 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절치 않음.
• Resizing
  • 배열은 메모리에 순차적으로 채워지기 때문에, Size를 Pre-allocation 해두는데,
    더 필요한 경우 추가 할당하기 위해 Resizing해야 됨.
  • 추가 메모리 할당을 위해서 resizing하는 operation은 매우 Heavy함.
  • 사이즈 예측이 잘 안 되는 데이터를 다루기에는 적절치 않음.

3) 언제 사용해야 할까?

• 순차열적 데이터를 저장할 때 (값보다는 순서가 중요한 데이터, 주식가격)
• 다차원 데이터를 다룰 때
• 어떤 특정요소에 빠르게 접근하는 게 좋을 때.
• 데이터의 사이즈 변나 요소의 이동이 급격하지 않을 때