기본 자료구조에 대해

자료구조

---

자료구조는 자료들을 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법등을 분석한 것입니다.

 

적은 데이터에서는 자료구조 간 차이가 미미하지만,

많은 데이터를 처리할 때 어떤 자료구조를 선택하느냐에 따라 효율성과 실행시간이 많은 차이를 보이기 때문에

기본적인 자료 구조의 특성에 대해 알아두는 것은 꽤나 중요합니다.

 

 

 

자료구조의 분류

---

자료구조는 흔히 선형 구조와 비선형 구조로 분류되고는 합니다.

 

▶선형구조

선형 구조는 데이터가 일렬로 연결되어 있는 구조입니다.

 

- 배열(Array)

크기와 타입이 같은 자료들이 순서대로 나열된 자료의 집합입니다.

반복적인 데이터 처리 작업에 적합한 구조이지만, 정적인 구조로 인해 데이터의 추가, 삭제 시 효율이 좋지 않습니다.

 

- 연결 리스트(Linked List)

자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조입니다.

연결을 위한 포인터 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않으나,

배열과는 달리 동적인 구조로 인해 데이터의 추가, 삭제 시 좋은 성능을 보입니다.

 

- 스택(Stack)

스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조입니다.

마지막에 들어온 데이터가 가장 먼저 사용되는 후입선출(Last In First Out) 방식입니다.

저장 공간의 부족할 때 데이터를 삽입하면 오버플로(Overflow)가 발생하고,

데이터가 없을 때 데이터를 삭제하면 언더플로(Underflow)가 발생합니다.

 

- 큐(Queue)

큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고, 다른 한쪽에서는 삭제 작업이 이루어집니다.

먼저 들어온 데이터가 가장 먼저 사용되는 선입선출(First In First Out) 방식입니다.

시작을 표시하는 Front 포인터와 끝을 표시하는 Rear 포인터가 있습니다.

 

 

▶비선형구조

비선형 구조는 자료의 구성이 일렬이 아닌 특정한 형태를 나타내는 구조를 가지고 있습니다.

 

-그래프(Graph)

그래프는 정점(Vertex)와 간선(Edge)의 두 집합으로 이루어지는 자료구조입니다.

간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됩니다.

 

-트리(Tree)

부모 노드 밑에 여러 개의 자식 노드가 연결되고,

자식 노드가 다시 부모가 되어 각각의 자식노드로 연결되는 재귀적 형태의 자료구조입니다.

사이클이 없는 그래프를 트리라고 합니다.