자료구조를 대분류로 나누면 선형(Linear)와 비선형구조(NonLinear)가 있다.

선형구조(Linear)

자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태를 선형구조라고 한다. 각 데이터 항목은 바로 앞이나 뒤의 하나의 데이터 항목과 관련이 있다. 선형구조는 데이터를 목록 형태로 저장하고 관리하기 때문에 데이터 추가, 삭제, 탐색 등의 작업을 직관적이고 단순하게 수행할 수 있다.

선형 구조의 예는 아래와 같다.

• 배열 (Array)

배열은 고정된 크기를 가지고, 메모리 상에 연속적으로 할당된 데이터 항목의 집합이다. 배열의 각 요소는 인덱스를 통해 직접 적근할 수 있어, 접근 속도가 매우 빠르다. 하지만 크기가 고정되어 있어 배열을 생성할 때 최대 크기를 미리 정해야 한다.

• 연결 리스트(Linked List)

연결리스트는 데이터 항목(노드)이 포인터를 통해 순차적으로 연결된 구조다. 각 노드는 데이터와 다음 노드를 가르키는 포인터로 구성된다. 연결 리스트는 동적으로 크기가 변할 수 있어, 실행 시간에 데이터 항목의 추가나 삭제가 자유롭다.

• 스택(Stack)

스택은 LIFO(Last In, Fisrt Out)방식이고, 스택에 데이터를 추가하는 작업을 ‘푸시(push)’, 스택에서 데이터를 제거하는 작업을 팝(pop)이라고 한다. 스택은 함수의 호출과 반환, 싶이 우선 탐색(DFS)등에 사용된다.

• 큐(Queue)

큐는 FIFO(Fisrt In First Out)방식이고, 큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 제거하는 작업을 디큐(dequeue)라고 한다. 큐는 버퍼, 너비 우선 탐색(BFS)등에 사용된다.

비선형구조(NonLinear)

데이터 항목이 계층적이거나 그래프 형태로 구성되어, 한 항목이 여러 개의 다른 항목과 연결될 수 있는 자료구조를 말한다. 복잡한 데이터 관게를 모델링하고 표현하기에 적합하고, 데이터 간에 일대일(One-to-One), 일대다(One-to-Many), 다대다(Many-to-Many)와 같은 관계가 있을 때 비선형 구조를 사용한다.

• 트리(Tree)

트리는 계층적인 구조를 가진 자료구조, 노드(Node)와 이 노드들을 연결하는 간선(Edge)으로 구성된다. 트리의 가장 상위에 있는 노드를 루트(Root)노드라고 하고, 루트 노드에서부터 시작하여 분기하면서 여러 개의 자식 노드를 가질 수 있다.

• 그래프(Graph)

그래프는 노드들이 간선으로 연결된 구조를 가진 자료구조다. 그래프는 방향이 있거나 없을 수 있고, 네트워크 모델링, 소셜 네트웤, 웹 페이징 링크 구조 등 다양한 문제에 사용한다.

• 힙(Heap)

힙은 완전 이진 트리의 일종으로, 힙 속성을 만족하는 트리 기반의 자료구조다. 힙은 주로 우선순위 큐를 구현하는데 사용된다.