[토론] 자료구조 - 순차/비순차 자료 구조

다음 토론답변은 KG아이티뱅크 2학기 3기수 자료구조 수업의 토론 주제에 대한 개인적인 답변입니다.

이에 받은 점수와 무관하게 학기를 마무리하며 개인적으로 기록을 남기고자 포스팅합니다.

 

 

주제

순차 자료구조란 무엇이며 어떤 특징을 갖는지 설명하고 비순차 자료구조(또는 연결 자료구조)와 비교하시오

 

 

답변

순차 자료구조란 선형 자료구조라고도 하며, 자료를 순서를 매겨 나열한 구조를 뜻한다. 원소들이 순서를 가지고 나열되며 메모리에도 같은 순서로 저장되기 때문에, 물리적 구조와 논리적 구조가 같다고 할 수 있다. 하지만 그런 특징 때문에, 원소의 삽입이나 삭제를 위해서는 다른 원소들의 자리 이동이 필요하여 추가적 작업 및 시간소요, 또는 오버헤드가 발생한다. 1차원뿐만 아니라, 2차원, 3차원으로도 구현이 가능하며, 2차원과 3차원 배열에서는 각각 행 우선방법, 면 우선 방법이 C 컴파일러에서 사용된다. 이러한 배열을 사용한 선형리스트에서는 <인덱스, 원소>의 쌍으로 구성된다. 다항식과 행렬 또한 1차원 이상의 배열로 구현하여 순차 자료구조로 표현할 수 있다.
반면 비순차 자료구조 (또는 연결 자료구조)는 이름에서 보이듯이, 원소를 '순서'대로 저장하지 않고 '주소'를 이용해 저장, 접근하게 한다. 물리적 순서와 논리적 순서가 다르기 때문에, 물리적 순서를 맞추기 위한 오버헤드를 피할 수 있다. 연결 자료구조는 <원소, 주소>의 '노드' 구조를 가지기 때문에, 주소를 저장할 추가적인 공간이 필요하다는 점 외에는 순차 자료구조보다 효율적이라 할 수 있다.