면접 주제로 자주 나오는 Data Structure에 관해 매주 월요일, 5주에 걸쳐 자료 정리를 진행한다.

의의 :

데이터에 편리하게 접근, 조작하기 위해 데이터를 저장하거나 조직하는 방법
상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조

종류 :

종류가 많기때문에 각각의 자료구조의 장단점을 파악해서 상황에 따라 선택사용
언어별로 지원하는 양상이 다름

분류

단순구조 : 기본 데이터 타입
비단순구조 : 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조

선형구조 : 저장되는 자료의 전후 관계가 1:1
비선형구조 : 데이터 항목 사이의 관계가 1:N

1. Array(List)

정의 :

Array - Javascript / List - Python

가장 기초적이고 자주 사용되는 자료 구조

특징 :

1) 순차적으로 데이터를 저장한다.
2) 저장되는 데이터는 element라고 한다.
3) 데이터를 순차적으로 저장할 때 사용
4) 순서 상관없이 서로 연결된 데이터 저장시에도 사용
5) 가장 자주 사용됨
6) 삽입 순서대로 저장됨
7) 수정이 가능함
8) 동일한 값도 여러번 삽입 가능
9) multi-dimentional array(다중차원 배열) = array요소가 array가 될 수 있음

내부 구조 :

1) index 0부터 시작 / 마이너스 부호를 가질 경우(-1) 맨 마지막 요소

단점 :

1) Removing or Adding Elements

정보가 삭제되거나 추가될 경우 그 뒤의 요소들을 모두 앞으로 또는 뒤로 옮겨야 하므로 속도가 느림 => 정보가 자주 삭제 또는 추가되는 데이터를 담기에는 적절하지 않음.

2) Array Resizing

순차적으로 배열을 저장한다는 기능때문에 배열이 모두 담기기 전에 미리 어느정도의 메모리를 할당하게 됨. 기존의 메모리가 다 차서 또 다른 메모리를 추가해야 되는 경우, 그 두 배정도의 메모리를 생성한 후 기존의 메모리를 복사하고 그 바로 다음번째 데이터부터 순차적으로 추가됨. (일반적으로 대부분의 언어는 pre-allocation과 resizing을 자동으로 실행함)

• 사이즈 예측이 어려운 데이터에는 적절하지 않음

활용 :

• 주식과 같이 순차열적인 데이터를 저장
• 다차원 데이터를 다룰 때
• Index를 통해 원하는 지점으로 바로 갈 수 있으므로 특정 요소를 빠르게 읽어야 할 때 유용
• 데이터의 사이즈가 일정한 작업 / 요소의 추가, 삭제가 자주 일어나지 않는 작업

2. Tuple

정의 :

• list와 같이 데이터를 순차적으로 저장할 수 있는 순열 자료 구조
• 한번 정의되면 수정할 수 없음
• 2-3개 정도의 소규모 데이터를 저장할 때 많이 사용
• Javascript에는 없으므로 JS는 Array(List)을 사용

장점 :

• 간단한 값을 빨리 표현하고 싶을 때 많이 사용 (ex) 지도 좌표)

단점 :

• 데이터가 무슨 의미인지 명확하지 않으므로 문맥을 보고 가정해야 함
• 그렇기에 소규모 데이터를 이루기에 적합함

활용 :

Tuple이 Array(List)보다 더 가볍기에 좌표 데이터와 같이 간단한 데이터를 표현할 때 사용.