자료 구조란?

잘은 모르겠지만 컴퓨터공학과에서 제일 처음 배우는 전공 과목이

자료구조 (data structure)가 아닐까 싶다.

​

그렇다면 자료구조가 뭘까 ?

위키백과의 정의에 따르면 컴퓨터과학에서 효율적인 접근 및 수정을 가능케하는 자료의 조직, 관리, 저장을 의미한다고 한다.

즉, 쉽게 얘기해서 자료, 즉 데이터가 저장된 형태란 거다. 예를 들면 데이터를 array로 저장할지, queue로 저장할지 등을 결정하는게 바로 그 저장되는 형태 또는 구조를 정하는 것과 같다.

참고로 여기서 말하는 데이터란 RAM(Random Access Memory)상에서의 데이터를 말한다. 즉, 단기적으로 사용할 데이터. 쓰고 바로 버릴 데이터를 말한다.

​

우리는 주로 컴퓨터로 어떤 문제를 해결하려고 할 때, 알고리즘을 이용한다.

즉, 어떤 알고리즘을 설계하고 그걸 통해 컴퓨터가 input을 받아 자동적으로 output을 내게 만드는 것이다.

이때, 알고리즘의 시간 복잡도는 자료 구조에 많이 의존할 것이다.

즉, 알고리즘 내에서 자료들이 어떤 자료구조 형태로 저장되어 있게 만드느냐에 따라서 알고리즘의 효율성의 차이가 날 수 있다.

​

그리고 흔히 말하는 ADT(Abstract Data Type 또는 Abstract Data Structures)는 우리말로 추상적 자료구조라고 하며, ADT 안에는 자료구조의 목적 및 기본적인 기능 등이 축약되어 있는 관념적인 개념이다. ADT는 무엇을 하는 자료구조이냐에 대한 개념이며 ADT 내부에는 (1)어떤 데이터 타입이 저장되어야 하는지, (2)어떤 operation들이 제공되어야 하는지 등이 정의되어있다.

​

예를들어, Singly Linked List나 Doubly Linked List는 Linked List라는 공통된 ADT의 구현을 다르게 한 것 뿐이다. 즉, 두 종류의 Linked List는 역할과 목적 (즉, 앞의 (1)과 (2))가 사실상 같으므로 같은 ADT로 볼 수 있다.