[Data Structure] 선형 자료구조 vs 비선형 자료구조

자료구조

데이터를 효율적으로 저장하고 관리하기 위한 체계적인 구조

어떤 자료구조를 선택하는가에 따라서, 성능과 효율성에 영향을 미칠 수 있으며, 상황에 따라 적절한 자료구조를 사용하는 것이 중요하다.

예를 들어, 1~10억 까지 임의의 숫자 100만개의 데이터 원소가 배열과 힙(우선순위 큐를 구현하기 위한 자료구조)에 저장되어있다고 할때, 가장 작은 수를 찾는다고 하자.

배열을 사용해서 데이터를 저장하면, 모든 수들을 순회해서 가장 작은 수를 찾아야한다.(100만번 연산)

힙을 사용해서 데이터를 저장하면, 가장 상위 노드에 있는 값이 가장 작은 수이다.(log(100만)연산)

 

이와 같이 어떤 자료구조를 사용하는가에 따라서 프로그램의 성능은 매우 달라질 수 있다.

 

자료구조는 형태에 따라 선형/비선형 자료구조로 구분된다.

 

선형 자료구조

자료구조에 저장한 데이터 원소들이 순차적으로 나열되어 있으며, 각 원소의 관계가 1:1인 자료구조를 이야기한다.

배열, 연결리스트, 스택, 큐, 덱과 같은 자료구조들이 여기에 해당한다.

 

비선형 자료구조

자료구조에 저장한 데이터 원소들이 계층구조(트리) 혹은 그물망(그래프) 처럼 연결 되어 있으며, 하나의 원소 뒤에 여러 개 원소가 존재할 수 있다.(1:N, N:N, N:1관계)

트리, 그래프와 같은 자료구조들이 여기에 해당한다.