자료구조

자료구조란?

데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것 입니다.

 

 

 

선형과 비선형

자료구조는 선형과 비선형 등의 여러 속성을 기반으로 분류할 수 있습니다. 선형 자료구조(Linear Data Structure)는 데이터 요소를 순서대로 정렬하며, 비선형 자료구조(Nonlinear Data Structure)는 데이터를 비연속적으로 연결합니다. 예를 들어 파이썬의 리스트는 각 요소의 앞과 뒤에 다른 요소가 있는 선형 자료구조인 반면, 그래프는 각 요소가 다른 여러 요소와 연결될 수 있는 비선형 자료 구조입니다.

 

자료구조를 순회(Traverse)한다는 말은 자료구조의 첫 번째 요소에서 출발해 마지막 요소로 이동한다는 뜻입니다. 선형 자료구조에서는 첫 번째 요소에서 마지막 요소까지 백트래킹(Backtracking)없이 쉽게 순회할 수 있지만, 비선형 자료구조에서는 종종 되돌아가야 합니다. 

 

비선형 자료구조에서는 원하는 요소에 접근하기 위해 백트래킹이나 재귀가 필요한 경우가 많기 때문에 개별 요소에 접근하는 작업에는 선형 자료구조가 더 효율적입니다. 또한 선형 자료구조는 데이터를 쉽게 순회할 수 있어 비선형 자료구조에 비해 요소 전체를 변경하는 작업이 쉽고, 백트래킹 없이 모든 요소에 접근할 수 있어 자료구조를 설계하고 사용하는 것도 더 쉽습니다. 그러나 비선형 자료구조는 특정한 몇 가지 문제에 대해 더 효율적인 방법일 수 있습니다. 예를 들어 소셜 네트워크의 연결과 같은 데이터는 선형 자료구조로 저장하기에는 비효율적이고, 비선형 자료구조가 더 알맞습니다.

 

정적, 동적 자료구조

정적인지 동적인지에 따라 자료구조를 분류하기도 합니다. 정적 자료구조(Static Data Structure)는 크기가 고정되어 있는 자료구조를 말하며, 동적 자료구조(Dynamic Data Structure)는 크기가 바뀔 수 있는 자료구조를 말합니다. 보통 정적 자료구조는 프로그램을 생성할 때 크기를 정의합니다. 한 번 정적 자료구조를 정의하면 그 크기는 고정되어 바꿀 수 없지만, 안에 저장된 데이터의 값은 바꿀 수 있습니다.

 

정적 자료구조에 요소를 추가하려면 새로운 자료구조를 만들어 기존 요소와 새로운 요소를 모두 담을 정도로 충분히 큰 메모리를 다시 할당한 다음, 기존 구조를 새 구조에 복사하면서 새로운 요소도 함께 추가하는 것이 유일한 방법일 때가 많습니다. 따라서 저장할 요소의 개수를 미리 알 수 없다면 정적 자료구조는 좋은 선택이 아닙니다. 그러나 저장할 요소의 개수를 미리 알고 있고, 그 개수가 변하지 않는 상황이라면 정적 자료구조가 동적 자료구조보다 뛰어난 성능을 보일 때가 많습니다. 예를 들어 사용자가 프로그램에서 ‘실행 취소’ 작업을 수행할 수 있고, 실행 취소 목록을 최대 10개까지 만들 수 있다면 정적 자료구조가 적합할 수 있습니다.

 

동적 자료구조는 정적 자료구조와 달리 크기를 자유롭게 바꿀 수 있습니다. 동적 자료구조에서는 요소를 추가할 때 컴퓨터가 추가로 메모리를 할당하고, 요소를 제거할 때 메모리를 비워 다른 데이터가 사용할 수 있도록 만듭니다. 크기가 고정되어 있지 않은 동적 자료구조는 효율적으로 요소를 추가하거나 제거할 수 있어 메모리를 더 효율적으로 사용합니다. 하지만 정적 자료구조에 비해 요소에 접근하는 작업이 느릴 수 있고, 일정 수의 요소를 저장한다고 할 때 정적 자료구조보다 더 많은 메모리를 사용할 수 있습니다. 저장해야 할 데이터의 양을 특정 할 수 없고, 특히 메모리 공간이 한정적일 때는 동적 자료구조가 더 나은 선택인 경우가 많습니다.

 

이미 언급했듯이 자료구조에는 저마다의 장단점이 있습니다. 이러한 장단점은 주로 데이터의 삽입과 삭제, 탐색의 효율성과 관련되며, 메모리 공간을 얼마나 효율적으로 사용하는가에 달려 있습니다.