순차 자료구조와 연결 자료구조

순차 자료구조

자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉩니다. 이러한 자료구조를 구현하는 방식에는 순차 자료구조와 연결 자료구조가 있습니다.

순차 자료구조는 구현할 자료를 논리적인 순서대로 메모리에 연속해서 저장하는 방식입니다. 그래서 순차 자료구조는 논리적인 순서와 물리적인 순서가 일치해야 합니다.

순차 자료구조는 논리적 순서와 물리적 순서가 같기 때문에 찾는건 매우 빠르지만 삽입 삭제 연산을 하면 물리적 순서와 논리적 순서를 일치 시키기 위해 원소를 옮기는 작업이 필요해 그 만큼 시간이 필요합니다.

연결 자료구조는 원소의 물리적 순서와 논리적 순서가 일치하지 않아도 됩니다. 따라서 원소를 옮기는 작업이 필요없게 되어 순차 자료구조보다 삽입 삭제 연산이 더 빠릅니다.

연속한 물리 주소에 원소를 저장하는 것이 아니라 각 원소가 이곳 저곳에 저장되어 있고 다음 원소의 주소인 링크를 가져 연결되는 구현 방식입니다.

	순차 자료구조	연결 자료구조
메모리 저장 방식	메모리 저장은 시작 주소부터 빈자리 없이 순서대로 저장, 논리적인 순서와 물리적 순서가 일치 구현 방식	메모리에 저장된 물리적 위치나 물리적 순서에 상관없이 링크에 의해 논리적인 순서를 표현하는 구현 방식
연산 특징	삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장	삽입, 삭제 연산으로 논리적 순서가 변경되어도 물리적 순서는 변경되지 않음
프로그램 기법	배열을 이용한 구현	포인터를 이용한 구현