선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure)

자료구조 분류

 

1. 선형 구조

데이터를 연속적으로 연결되어 있는 모양으로 구성한다.

 

1) 배열(Array)

• 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다.
• 빠른 접근(O(1))과 random access가 가능하다.
  • 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 해당 원소에 접근할 수 있다.
  • 인덱스란 배열의 요소를 간단히 구별하기 위해 사용하는 번호이다. (0 ~ n-1)
• 정적인 자료 구조로 기억 장소의 추가가 어렵고 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아있어 메모리 낭비가 발생한다.

 

2) 배열 리스트(Array List)

• 배열과 같이 연속되는 기억 장소에 차례대로 데이터가 저장되지만 빈 공간이 없다.
• 기억 장소를 연속적으로 배정받기 때문에 기억 장소 이용 효율은 가장 좋다.
• 접근(O(1))은 빠르지만 삽입과 삭제(O(n)) 시 자료의 이동이 필요하다. 

 

3) 연결 리스트(Liked List)

• 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨다.
• 각각의 원소들은 자신의 위치의 이전, 다음 원소의 위치만을 기억한다.
• 동적인 크기를 가져 삽입과 삭제(O(1))가 용이하지만 검색(O(n)) 속도가 느리다. 삽입과 삭제 전에 검색이 필요하기 때문에 결국 모두 O(n)의 시간 복잡도를 갖는다. 

 

4) 스택(Stack)

• 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어진다.
• LIFO(Last In First Out): 가장 나중에 삽입된 자료가 가장 먼저 삭제된다.

 

5) 큐(Queue)

• 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어진다.
• FIFO(First In First Out): 가장 먼저 삽입된 자료가 가장 먼저 삭제된다.
• 우선순위 큐(Priority Queue): 우선순위를 가진 데이터 구조로 보통 힙(Heap)으로 구현한다.

 

2. 비선형 구조

선형 구조와는 달리 비선형적인 계층 구조를 나타낸다.

 

그래프와 트리의 차이

 

1) 그래프(graph)

정점(노드)과 선분(간선)의 집합이다.

 

2) 트리(Tree)

정점(노드)과 선분(간선)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로 계층적 관계를 표현한다.

 

트리의 구성요소