[자료구조] 종류

자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라서 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다.

종류로는 단순 구조와 자료 간 관계가 1대 1인 선형 구조, 1대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일구조가 있다.

 

구현에 따른 분류

배열 

   : 가장 일반적인 구조로 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위

     이다.

 

튜플

   : 둘 이상의 자료형을 묶음으로 다루는 구조

 

연결 리스트

   : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조 값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

 

원형 연결 리스트

   : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결리스트이다.

 

이중 연결 리스트

   : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.

 

환형 이중 연결 리스트

    : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트

 

해시 테이블

    : 개체가 해시값에 따라 인덱싱된다.

 

형태에 따른 분류

선형 구조

  - 스택

     자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다.

     만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.

 

  - 큐

     스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 즉, 들어간 순서와 나오는 순서가 같다.

         - 환형 큐 : 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐

  - 덱 

    양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

 

 

비선형 구조

  - 그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성

  - 트리 : 뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조.

               부모 자식 관계는 변으로 표현된다.

            - 이진 트리 : 자식이 최대 두 개인 트리

                       - 힙 : 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

 

 

[REFERENCE]

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0