자료구조의 종류

1. 단순구조(기본구조): 언어에서 기본으로 제공하는 타입

2. 선형구조: 데이터가 연속적으로 붙어있거나 순서가 정해져 있는 구조

1) 리스트(배열, array): 데이터가 연속적으로 붙어 있는 구조

2) 연결 리스트(linked list): 불연속적인 데이터가 링크를 통해 연결되어 있는 구조

- 단순 연결 리스트: 한 데이터가 다음 데이터(next)를 가리키고 있는 구조. 순서가 있다.

- 이중 연결 리스트(doubly linked list): 연결 리스트에서 이전 데이터(previous)를 가리키는 링크를 추가한 구조

- 원형 연결 리스트(circular linked list): 이중 연결 리스트에서 맨 앞 데이터와 맨 뒤 데이터를 연결하는 링크를 추가한 구조

3) 스택(stack): 한쪽에서만 데이터 삽입과 삭제가 가능한 구조. LIFO(Last In First Out, 마지막 삽입 데이터가 먼저 삭제됨)

4) 큐(queue): 삽입과 삭제가 각각 다른 쪽에서 일어나는 구조. FIFO(First In First Out, 첫 삽입 데이터가 먼저 삭제됨)

5) 덱(deque, double-ended queue): 삽입과 삭제가 양쪽에서 일어나는 구조

 

3. 비선형구조: 데이터가 선형이 아닌 규칙으로 연결되어 있는 구조

1) 트리(tree): 값을 가진 노드(node)가 엣지(edge)로 연결되어 있는 구조. 상위 노드를 부모, 하위 노드를 자식이라 부른다. 최상위 노드는 루트(root)라고 부른다.

- 일반 트리: 부모 노드에 자식 노드가 0~n개 연결되어 있는 구조

- 이진 트리(binary tree): 자식 노드가 최대 2개인 구조

2) 그래프: 값을 가진 노드(node)가 엣지(edge)로 연결되어 있는 구조. 상하위가 정해져 있지 않다.

- 방향 그래프(directed graph): 엣지에 방향이 없는 구조

- 무방향 그래프(undirected graph): 엣지에 방향이 있는 구조

 

4. 파일구조: 파일 내용이 연결되어 있는 구조

1) 순차 파일

2) 색인 파일

3) 직접 파일