자료구조 06/24 - 2

자료의 분류

자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간의 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다.

자료구조의 종류로는
1. 자료형에 따라 분류하는 단순 구조
2. 자료 간 관계가 1 대 1인 선형 구조
3. 1 대 다 혹은 다 대 다 구조인 비선형 구조
4. 마지막으로 파일 구조가 있다.

구현에 따라

1. Array : 가장 일반적인 구조. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위. 다른 복잡한 자료 구조들을 표현하기 위해서 또는 'Matrix', 'Vector' 등을 컴퓨터에서 표현하는 용도 등으로도 사용된다.
2. Tuple : 둘 이상의 자료형을 묶음으로 다루는 구조.
3. Linked List : 노드를 단위로 한다. 노드는 다음 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
4. Circular Linked List : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 linked list이다.
5. Doubly Linked List : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
6. Circular, Doubly Linked List : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 Doubly Linked List이다.
7. Hash Table : 개체가 해시값에 따라 인덱싱된다.

형태에 따라

1. 선형 구조
   a. Stack(FILO) : 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
   b. Queue(FIFO) : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
   c. Circular Queue : 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐.
2. 비선형 구조
   a. Graph : 꼭짓점과 꼭짓점을 잇는 변으로 구성.
   i) Directed graph, Undirected graph
   변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다. Undirected graph의 경우, 순환이 없는 연결 그래프를 뜻한다. Directed graph의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
   b. Tree : root와 root, 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.
   i) Binary tree : 자식이 최대 2개인 tree
   ex) Heap : 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것.