자료구조란? 자료구조, 추상 자료형(ADT)

자료구조

자료구조란 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다.

자료구조에는 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다.

어떠한 자료구조를 사용하느냐에 따라 공간의 효율성과 프로그램의 실행시간이 달라진다.

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

 

- 자료구조의 종류

 

자료구조는 크게 선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure)로 나뉘어 진다.

• 선형 구조(Linear Structure): 자료를 표현 및 저장하는 방식이 선형(linear) 으로써 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.
• 비선형 구조(Non-Linear Structure): 데이터를 나란히 저장하지 않는 구조 로써 선형 자료구조에 비해 상대적으로 학습 난이도가 높다.

 

- 선형 구조(Linear Structure)

. 선형 리스트(Linear List): 리스트에서 나열한 데이터간에 순서를 가지고 있는 리스트다. 보통 배열로 구현한다.

. 연결 리스트(Linked List): 노드를 단위로 한다. 노드는 데이터와 다음 노드를 가리키는 참조값으로 구성되어 있다. 

. 스택(Stack): 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다.

. 큐(Queue): 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.

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

- 비선형 구조(Non-Linear Structure)

. 트리(Tree): 뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부로로 같는 꼭짓점드로 이러우진 구조다. 부모 자식 관계는 변으로 표현된다.

. 그래프(Graph): 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.

---

2. ADT(Abstract Data Type) 

추상자료형(ADT)이란 '구체적인 기능의 완성을 업급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'을 말한다.

예를들어 전기 밥솥을 추상자료형으로 비유하면, 그속에 들어가는 밥은 자료가되고, 밥솥에 있는에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다.

추상자료형은 밥솥 내부에서 어떠한 복잡한 일이 발생하는지에 대해서는 관심없고 기능과 사용방법을 정의한 것이다.

ADT는 두 부분으로 구성된다.

• 데이터의 선언
• 연산의 선언

ADT를 정의할 때는 구체적인 구현은 신경쓰지 않아도 된다. 실제 사용할 때 구현이 중요하다.

주로 사용하는 ADT는 연결리스트, 스택, 큐, 우선순위 큐, 이진 트리, 딕셔너리, 서로 집합, 해시 테이블, 그래프등등 다수가 있다.

사용 용도에 따라 그에 알맞는 ADT들이 쓰이며, 몇몇 ADT는 특정 용도에 최적화 되어있다.

소년코딩 블로그에서는 많은 ADT들을 소개하고, 자바스크립트로 구현해보겠다.

---

 

by 소년코딩

추천은 글쓴이에게 큰 도움이 됩니다.

악플보다 무서운 무플, 댓글은 블로그 운영에 큰 힘이됩니다.