[자료구조] 선형 비선형

---

자료구조(data structure)

자료를 메모리에 어떤식으로 담을지 표현하는 구조를 말하며 크게 선형 자료구조와 비선형 자료구조로 나뉘어 진다.

선형 자료구조(linear data)

자료를 구성하는 원소들을 순차적으로 나열시킨 형태를 의미한다.

종류

• 배열
  인덱스를 가지고 있으며 순차적으로 데이터가 삽입, 삭제 될 수 있는 형태의 자료구조이다.

  데이터를 순차적으로 삽입, 삭제할 때 가장 효과적이며 인덱스를 사용하기 때문에 검색이 빠르지만 중간에 삽입, 삭제가 어렵다.

• 연결 리스트
  자료들을 임의의 기억공간에 기억시키되 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.

  포인터를 통해 연결시키기 때문에 배열에 비해 검색 속도와 접근 속도가 느리고 메모리 이용 효율이 떨어지지만 중간에 삽입, 삭제가 빠르고 용이하다.

• 스택
  리스트의 한 쪽 끝으로만 자료를 삽입, 삭제 작업이 이루어 진다.

  가장 마지막으로 들어온 데이터부터 빠져나가는 후입선출(last in first out) 형식이다.

• 큐
  리스트의 한 쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어진다.

  가장 먼저 삽입된 자료가 가정 먼저 출력되는 선입선출(first in first out) 방식으로 처리한다.

• 데크
  스택과 큐의 장점만으로 구성된 자료구조로 삽입, 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.

  입력은 한쪽에서 출력은 양쪽에서 발생하는 입력 제한 데크(scroll)

  입력은 양쪽에서 출력은 한쪽에서에서 발생하는 출력 제한 데크(shelf)

비선형 자료구조(non-linear data structure)

하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조이다.

• 트리
  노드들의 집합으로 각 노드들은 서로 다른 자식을 가지며 이 때 노드들은 재사용 되지 않는 구조이다. 대표적으로 컴퓨터의 파일의 구조가 트리 형식이다.

  사용법과 형태에 따라 종류가 다양하다.

  • 이진 트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 균형 트리

• 그래프
  노드와 그 노드를 연결하는 간선을 하나로 모아놓은 구조이다. 연결되어 있는 객체 간의 관계를 표현할 수 있다. 지하철의 노선도가 그래프 형태라 볼 수 있다.

  루트 노드와 노드간의 부모자식 관계의 개념이 없으며 2개 이상의 경로가 가능하며 순회는 너비 우선 탐색(breadth first search, BFS)와 깊이 우선 탐색(depth first search)로 이루어 진다.

  • 가중치 그래프, 무방향 그래프, 방향 그래프, 비연결 그래프, 연결 그래프, 비순환 그래프, 순환 그래프, 완전 그래프