자료구조

자료구조의 정의

자료구조는 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.

 

단순히 데이터를 저장하는 것에서 그치지 않고, 데이터에 대한 접근, 검색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있도록 설계되었습니다.

 

데이터의 특성과 사용 목적에 맞게 '정리정돈'하여 프로그램의 전반적인 성능을 향상시키는 것이 핵심입니다.

 

자료구조의 분류

자료구조는 크게 선형 구조와 비선형 구조로 나뉩니다.

 

1. 선형 자료구조 (Linear Data Structures)

데이터를 순차적으로 나열시킨 형태입니다.

• 배열 (Array) : 같은 타입의 데이터들이 메모리 상에 연속적으로 저장되는 가장 기본적인 구조입니다. 인덱스(index)를 통해 데이터에 빠르게 접근(O(1))할 수 있다는 큰 장점이 있습니다. 하지만 크기가 고정되어 있고, 중간에 데이터를 삽입하거나 삭제할 때 비효율적이라는 단점이 있습니다.
• 연결 리스트 (Linked List) : 각 데이터(노드)가 다음 데이터를 가리키는 포인터를 가지고 있어, 데이터들이 메모리 상에 흩어져 있어도 논리적으로는 연결된 구조입니다. 데이터의 삽입과 삭제가 배열보다 훨씬 빠르지만(O(1), 포인터만 바꿔주면 되므로), 특정 데이터에 접근하려면 처음부터 순차적으로 찾아야 하므로 검색 속도가 느리다는(O(n)) 단점이 있습니다.
• 스택 (Stack) : LIFO (Last-In, First-Out), 즉 '후입선출' 구조입니다. 가장 마지막에 들어온 데이터가 가장 먼저 나가는 방식입니다.
• 큐 (Queue) : FIFO (First-In, First-Out), 즉 '선입선출' 구조입니다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 방식입니다.

 

2. 비선형 자료구조 (Non-linear Data Structures)

하나의 데이터 뒤에 여러 개의 데이터가 올 수 있는, 계층적이거나 망(network) 형태를 가진 구조입니다.

• 트리 (Tree) : 부모-자식 관계를 가지는 계층적 구조입니다. 폴더 구조나 조직도처럼 하나의 루트(root)에서 여러 갈래로 뻗어 나가는 형태를 가집니다. 데이터를 효율적으로 검색하거나 정렬할 때 많이 사용됩니다. (예: 이진 탐색 트리)

• 그래프 (Graph) : 정점(Vertex)과 그 정점을 연결하는 간선(Edge)으로 이루어진 구조입니다. 지하철 노선도처럼 여러 지점들이 서로 복잡하게 연결된 관계를 표현하는 데 사용됩니다. (예: 내비게이션 길 찾기, 소셜 네트워크 친구 관계)

 

자료구조가 필요한 이유

자료구조는 알고리즘의 효율성과 직결됩니다. 어떤 자료구조를 선택하느냐에 따라 프로그램의 시간 복잡도(수행 시간)와 공간 복잡도(메모리 사용량)가 크게 달라집니다.

예를 들어, 100만 개의 데이터 중에서 특정 값을 찾아야 할 때,

• 배열을 순차적으로 검색하면 최악의 경우 100만 번을 비교해야 합니다.
• 데이터가 정렬되어 있다는 가정 하에 이진 탐색 트리를 사용하면 약 20번의 비교만으로 값을 찾을 수 있습니다.

특히 대규모 데이터를 다루는 게임 클라이언트에서는 이러한 성능 차이가 유저 경험에 치명적인 영향을 미칠 수 있으므로, 상황에 맞는 최적의 자료구조를 선택하는 능력이 매우 중요합니다.

 

장단점 요약 

자료구조	장점	단점
배열	인덱스를 통한 빠른 접근 속도 (O(1))	크기 변경이 어렵고, 데이터 삽입/삭제가 비효율적임 (O(n))
연결 리스트	데이터 삽입/삭제가 빠름 (O(1)), 크기가 동적으로 변함	특정 데이터 검색 속도가 느림 (O(n)), 포인터 저장을 위한 추가 메모리 필요
스택	구조가 단순하고 구현이 쉬움, 데이터 저장/읽기 속도가 빠름	가장 상위 데이터에만 접근 가능하여 유연성이 떨어짐
큐	데이터가 들어온 순서대로 처리됨, 구현이 쉬움	중간 데이터에 접근이 불가능함
트리	데이터 검색, 삽입, 삭제가 효율적임 (특히 이진 탐색 트리: O(log n))	구현이 복잡하고, 데이터가 편향될 경우 성능이 저하될 수 있음 (선형 구조화)
그래프	복잡한 관계를 표현하는 데 매우 유용함	구현이 복잡하고, 알고리즘의 시간 복잡도가 높을 수 있음
해시 테이블	평균적으로 매우 빠른 데이터 검색, 삽입, 삭제 속도 (O(1))	해시 충돌 발생 가능성이 있고, 순서가 있는 데이터에는 부적합함