자료구조 개념과 종류

자료구조 정의

 데이터를 효율적으로 다루기 위해 데이터를 저장하는 방법

 

 

자료구조의 알고리즘 선택

 일반적으로 자료구조가 선택되면 어떤 알고리즘을 적용할지 상대적으로 명확해짐

 반대로 특정 연산에는 특정 알고리즘이 필요하고 큰 시너지 성능을 발휘할 때 자료구조를 역선택하게 됨

 

 

자료구조의 단위와 종류

자료구조의 기초 단위

행렬, 레코드, 유니온, 참조

 

자료구조의 분류

자료형에 따른 분류

- 단순 구조 : 정수, 실수, 문자, 문자열

- 선형 구조 : 1:1의 자료간 관계

- 비선형 구조 : 1:N 또는 N:M의 자료간 관계

- 파일 구조 : 순차 파일, 색인 파일, 직접 파일

 

구현에 따른 분류

- 배열(Array) : 가장 일반적이며 메모리 상 같은 타입의 자료가 연속적으로 저장 관리

- 튜플(Tuple) : 둘 이상의 자료형을 묶음으로 저장 관리

- 연결 리스트(Linked List) : 노드를 단위로 다음 노드를 가리키는 포인터로 구성

- 원형 연결 리스트(Circular Linked List) : 연결 리스트에서 마지막 노드가 처음 노드를 포인터

- 이중 연결 리스트(Double Linked List) : 각 노드는 이전, 다음 노드를 포인터

- 원형 이중 연결 리스트(Circular Double Linked List) : 이중 연결 리스트에서 처음 노드는 마지막 노드를 포인터, 마지막 노드는 처음 노드를 포인터

 

형태에 따른 분류

선형 자료구조

- 스택(Stack) : LIFO 구조 / PUSH, POP, TOP

- 큐(Queue) : FIFO 구조 / PUT, GET, FRONT, REAR

- 덱(Dequeue) : 큐에서 입구가 양쪽으로 존재

- 리스트(List) : 포인터가 서로 연결되어있음

 

비선형 자료구조 

- 트리(Tree) : 뿌리 노드인 부모를 바탕으로 자식들을 가지는 부모-자식 관계를 가짐

- 그래프(Graph) : 정점과 정점을 잇는 간선으로 데이터를 가짐

- 이진 트리(Binary Tree) : 자식 노드가 최대 두개인 트리

- 힙(Heap) : 이진 트리에 어떤 특성을 부여해 데이터를 저장 관리

 

정렬 동작에 따른 분류

- 안전한 정렬(Stable Sorting) : 정렬시 같은 값이 존재할 때 같은 순서로만 정렬

- 안전하지 않은 정렬(Unstable Sorting) : 정렬시 같은 값이 존재할 때 섞일 수 있게 정렬