선형 구조 VS 비선형 구조

복습하는 겸, 데이터 구조의 두 가지 종류인 선형과 비선형에 대해 정리를 진행 보겠습니다.

 

선형 구조

- 데이터가 연속적이고 순차적으로 배치되는 구조입니다.

- 각 요소는 하나의 선형 순서로 정렬되어 있으며, 각 요소는 이전 요소와 다음 요소와의 관계를 가집니다.

- 종류에는 배열, 연결 리스트, 스택, 큐가 존재합니다.

- 연속성 : 메모리에서 연속된 위치에 데이터가 저장됩니다 (특히 배열의 경우)

- 접근 방식 : 각 요소는 단 하나의 직접 앞선 요소와 단 하나의 직접 뒤따른 요소를 가집니다.

 

 

- 탐색 시간 : 특정 요소에 대한 접근 시간은 구조에 따라 다릅니다. 예를 들어, 배열은 O(1)로 접근할 수 있지만, 연결 리스트는 O(n)이 걸릴 수 있습니다.

- 연결 리스트의 경우에는 동적 할당을 통해 메모리 조절이 가능합니다.

 

비선형 구조

- 데이터가 계층적이나 비연속적으로 배치되는 구조입니다.

- 각 요소는 여러 요소와 관계를 가질 수 있으며, 데이터가 여러 경로로 연결됩니다.

- 종류에는 트리, 그래프, 힙 등이 존재합니다.

- 계층적 구조 : 데이터가 계층적 구조를 가지며, 루트와 하위 노드의 개념이 존재합니다 (특히 트리의 경우)

- 노드 기반 구조로 동적 메모리 할당을 사용하여 메모리 크기를 조절할 수 있으며, 요소 간의 관계를 저장하는 추가 메모리가 필요합니다.