자바로 배우는 핵심 자료구조와 알고리즘 - 2. 역사적인 자료구조

yudong (35)in #kr • 6 years ago

오늘은 책에는 나오지 않는 "외전"으로 프로그래밍 언어에서 자료구조를 어떻게 제공하였는지 역사적(?)으로 알아봅니다.

1. 파이썬의 자료구조

자바에 대한 글인데 왜 갑자기 파이썬에 대해서 얘기할까요? 저는 작년에 AI나 배워볼까하고 파이썬 초급을 익혔습니다. 가장 먼저 놀란 것은..

"언어에서 자료구조를 내장하고 있다"는 것이었습니다.

예를 들어 자바에서 리스트를 만드는 문장과 파이썬을 비교해봅니다.

리스트에 1,2,3 넣기

java:
import java.util.List;
import java.util.ArrayList;

List< String> a = new ArrayList<>();
a.add(1); a.add(2); a.add(3);

python:
a = [1,2,3] #이걸로 끝

또한 파이썬은 다음의 자료구조도 기본적으로 제공합니다.

딕셔너리 (자바의 Map에 해당)
튜플 (자바에는 없어요)
json (일반적으로는 json을 프로그래밍 언어의 자료구조로 분류하지는 않지만 저는 소스코드에서 그대로 활용할 수 있는 구조화된 자료이므로 여기에 포함합니다)

이것은 지극히 모던(modern)한 현상으로 이로 인해 소스 코드의 표현력이 매우 높아졌습니다. 특히 리스트 표현법(List Comprehension)과 슬라이스(Slice) 등은 정말 멋진거 같아요 +.+

역사적으로 좀더 앞선 다른 언어의 자료구조에 대해서 알아볼까요?

2. C언어의 자료구조

C언어는 1970년에 만들어졌으며 내장한 자료구조가 거의 없습니다. 배열과 구조체(struct)정도?

배열은 가장 단순한 형태의 자료구조로 다음의 특징을 가지고 있습니다.

요소의 타입이 같다 (심지어는 primitive type 수준으로..)
갯수가 정적이다

따라서 적은 메모리에서도 효율적으로 사용할 수 있는 반면 언제든지 오류의 가능성(심지어는 blue screen)이 있고 유연하지 못한 단점이 있습니다. 즉 손이 많이 갑니다.

한편 리스트와 같은 동적 자료 구조는 ADT(추상적 자료형) 이라고 불렀습니다. 사실 ADT라는 단어도 C언어 기초를 배우고 학부 2학년때 "C언어로 배우는 자료구조"라는 책에서 처음 접하였습니다. ~~ADT는 캡스가 아니죠~~

위키 참고: https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95

당시 프로그램을 만들때 가장 먼저 해야할 일이 필요한 자료구조를 만드는 것일 정도였습니다. 라이브러리도 풍부하지 않았지요. (지금은 상상도 하기 힘들죠. DBMS도 재대로 된것이 없었던 시절얘기입니다 ㄷㄷ)

3. C++의 자료구조

C언어를 계승하는 C++ 언어는 1980년에 만들어졌으며 이후에 추상적인 자료구조를 지원하기 시작합니다.

혁신적인 STL(Standard Template Library)을 통해서 generic을 지원합니다. 또한 list, vector, map과 같은 일반적인 자료구조를 지원합니다.

제가 C++ 언어는 잘 몰라서 간략하게만 언급합니다.

4. Java의 자료구조

자바 언어는 90년대 중반에 나왔으며 자료 구조 수준에서는 C++ 언어를 계승하였습니다. 대신 STL보다는 좀더 깔끔하게 세분화된 JCF(Java Collection Framework) 클래스들을 제공합니다. 당시 발표된 자바5는 generic도 함께 지원하였기 때문에 대단히 충격적이었습니다.

자바도 JCF 이전에는 Hashtable, Vector 같은 클래스들을 개별적으로 제공하였지만 JCF를 통해서 깔끔하게 계열화된 자료구조(collections) 클래스들을 제공하게 되었습니다.

사실 애플리케이션 수준에서는