자료구조(Data Structure)

자료구조

 - 데이터의 집합

 - 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조

 - Code상 효율적으로 데이터를 처리하기위해 데이터의 특성에 따라, 체계적으로 데이터를 구조화

 - 상황별 어떤 자료구조를 사용하냐에 따라 코드 효율이 달라진다.

 

1. 배열(Array)

 - 여려개의 데이터를 하나의 변수에 관리(연관 데이터를 하나의 변수에 관리할 수 있다.)

 - 고정된 크기

 - 물리적으로 연속적으로 배치되어있음.

 - Index로 데이터에 접근(논리적인 순서(Index))는 메모리에 저장되는 원소값의 물리적인 순서(메모리)와 동일

 - 데이터의 삭제, 삽입시 낭비되는 공간이 없으려면 시프트연산이 동반되어야 함

 

2. 리스트(List)

 - 선형 리스트(Linear List), 연결 리스트(Linked List)가 있음

 - 선형 리스트

   물리적으로 연속적으로 빈틈없이 배치되어 있고, 접근속도가 빠르고 간단

 - 연결 리스트

   논리적으로는 순서대로 연결되어 있고, 물리적으로는 순서대로 연결되어있지는 않음.

   연결을 위한 링크를 저장하는 메모리가 추가적으로 필요하므로 순차 리스트에 비해 메모리 효율이 좋지않음.

   연결 정보를 찾는 시간이 필요하므로, 접근 속도가 느리다.

   데이터 삭제, 삽입 시 연결을 재구성해야되는 작업이 필요하다.

   트리를 표현할때 적합

   단일 연결리스트, 이중 연결리스트, 원형 연결리스트가 있다.

 

3. 큐(Queue)

 - 선입선출(FIFO - First In First Out) 형태의 자료구조

 - 큐의 앞과 뒤에서 삽입 삭제가 가능한 Deque가 있음

 

4. 스택(Stack)

 - 후입선출(LIFO - Last In First Out) 형태의 자료구조

 - 구조가 단순하며 데이터의 저장/접근이 빠름

 

5. 해쉬 테이블(Hash Table)

 - Key : Value의 형태로 저장하는 데이터 구조(ex: CPP나 Java의 map, C#의 Dictionary, Json)

 - Key는 중복된 값을 가질 수 없다.

 - 데이터의 저장/접근이 빠름

 - Key값을 저장할 저장공간이 추가로 필요

 - 여러개의 Key에 대한 데이터 위치가 동일할 경우, 충돌에 대한 별도의 조치가 필요

 

6. 트리(Tree)

 - node와 node들을 연결하는 edge로 구성되어잇는 형태

트리 그래프의 형태

 - Root Node : 트리의 최상위 노드

 - Level : 하위로 연결된 Node의 깊이를 나타냄

 - Depth : 트리 자료구조에서 Node가 가지는 최대 Level

 - Parent Node : 어떤 Node를 기준으로 상위의 Node

 - Child Node : 어떤 Node를 기준으로 하위의 Node

 - 이진트리, 이진탐색트리

   이진트리 : Node의 최대 Branch가 2개인 트리

   이진탐색트리 : 이진트리 + 추가조건(ex : 왼쪽 Node는 상위 Node보다 큰 값, 오른쪽 Node는 상위 Node보다 작은값)

 

7. 힙(heap)

 - 데이터의 최소값과 최소값을 빠르게 찾기위해 고안된 완전이진트리(마지막을 제외한 모든 Node에서 자식 Node들이 모두 채워진 이진 트리)

 - 여러개의 값들 중 최대값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조

 -  최대힙과, 최소힙

   최대힙 : 부모Node의 값이 자식Node의 값보다 항상 큼

   최소힙 : 부모Node의 값이 자식Node의 값보다 항상 작음

 - 느슨한 정렬 상태(반정렬 상태)를 유지