데이터 구조(data structure)는 프로그래밍에서 데이터를 저장하고 조직화하는 방식을 의미하며, 크게 선형(linear) 데이터 구조와 비선형(non-linear) 데이터 구조로 나눌 수 있습니다. 이번 글에서는 두 구조의 핵심 차이점과 각각의 특징, 그리고 파이썬 예제 코드까지 자세히 살펴보겠습니다.
선형 데이터 구조란?
- 요소들이 순차적으로(sequentially) 배치됩니다.
- 구조를 처음부터 끝까지 순회(traverse)하면 모든 요소에 접근할 수 있습니다.
- 모든 요소가 단일 레벨에 존재하므로 계층(hierarchy)이 없습니다.
- 구현과 사용이 비교적 쉽습니다.
- 메모리를 상대적으로 많이 사용하기 때문에 메모리 효율성은 떨어지는 편입니다.
- 데이터 크기가 커질수록 연산 시간 복잡도(time complexity)가 함께 증가하는 경향이 있습니다.
- 대표적인 예: 리스트(list), 배열(array), 스택(stack), 큐(queue)
다음은 파이썬에서 리스트를 정의하고 출력하는 간단한 예제입니다.
my_list = [45, 42, 12, 34, 56, 7]
print(my_list)출력 결과
[45, 42, 12, 34, 56, 7]비선형 데이터 구조란?
- 요소들이 계층적(hierarchical)으로 저장됩니다.
- 요소들은 '노드(node)'를 통해 서로 연결됩니다.
- 요소들이 여러 레벨에 걸쳐 존재하며, 단일 레벨에 국한되지 않습니다.
- 구현 난이도가 상대적으로 높습니다.
- 한 번의 순회만으로 전체를 탐색하기 어려우며, 여러 번의 반복(iteration)이 필요합니다.
- 메모리를 효율적으로 사용하는 것이 큰 장점입니다.
- 데이터 크기가 증가해도 시간 복잡도가 대체로 일정하게 유지됩니다.
- 대표적인 예: 맵(map), 트리(tree), 그래프(graph)
아래 예제는 파이썬 딕셔너리를 활용해 그래프를 정의하는 방법을 보여줍니다. 비선형 구조에서는 노드 자체뿐 아니라 노드 간의 연결 관계(edge)까지 함께 정의해야 한다는 점에 주목하세요.
예제
graph = {'A': ['B', 'C'],
'B': ['C'],
'C': ['D', 'E'],
'D': ['C'],
'E': ['F', 'G'],
'F': ['C']}선형 vs 비선형 데이터 구조 비교 요약
| 구분 | 선형 데이터 구조 | 비선형 데이터 구조 |
|---|---|---|
| 배치 방식 | 순차적 | 계층적 / 네트워크형 |
| 레벨 | 단일 레벨 | 다중 레벨 |
| 구현 난이도 | 쉬움 | 어려움 |
| 순회 방식 | 한 번의 순회로 가능 | 여러 번의 순회 필요 |
| 메모리 효율 | 낮음 | 높음 |
| 시간 복잡도 | 크기가 커지면 증가 | 대체로 일정하게 유지 |
| 예시 | 리스트, 배열, 스택, 큐 | 맵, 트리, 그래프 |
마무리
선형 데이터 구조는 단순하고 구현이 쉬워 소규모 데이터나 순차적인 데이터 처리에 적합합니다. 반면 비선형 데이터 구조는 계층적이거나 복잡하게 얽힌 관계를 표현하는 데 유리하며, 대용량 데이터를 다룰 때도 효율성을 유지할 수 있습니다. 따라서 해결하려는 문제의 성격과 데이터의 형태를 고려해 적절한 데이터 구조를 선택하는 것이 무엇보다 중요합니다.