프로그래밍을 시작하면 처음 배우게 되는 것이 자료구조다.

프로그래머에게 자료구조가 무슨 의미를 갖기에 처음으로 알려주고, 컴퓨터 공학(Computer Science)의 기초라고 하는 걸까?

자료구조는 프로그래머의 무기이다.

프로그래머는 프로그래밍 언어로 컴퓨터에게 명령한다

프로그래밍이란 현실의 문제(예약, 결제, 모임, 채팅 등)을 해결하기 위해 컴퓨터 프로그램을 만드는 작업이다.

구체적으로 말하면 현실의 문제를 컴퓨터가 해결할 수 있도록 컴퓨터에게 명령하는 일이다.
그런 명령들의 모음이 프로그램이다. (일종의 작업 지시서라고나 할까?)

컴퓨터에게 일을 시키려면 컴퓨터가 알아들을 수 있게 얘기해야한다.
인간의 언어가 아닌 JavaScript, C 같은 프로그래밍 언어로 말해야한다.

프로그래머는 자료구조를 통해 현실을 표현한다.

문제들을 프로그래밍 언어로 설명하려면 현실을 프로그래밍 언어로 표현해야한다.
그러나 현실은 아주 복잡해서 0과 1이라는 단순한 표현만 가지고는 설명하기에 역부족이다.
현실을 표현할 더 풍부하고 효과적인 표현방식이 필요하다.

복잡한 현실을 효과적으로 표현(모델링)하기 위해 만들어진 것이 자료구조이다.
적절한 자료구조를 통해 복잡한 구조를 더 명확하고 쉽게 표현할 수 있다.

적절한 자료구조를 선택하면 문제를 잘 해결할 수 있다.

프로그래머를 현실의 문제를 무찌르기(해결하기)위한 전사라고 비유해보자.

자료구조는 프로그래머가 잘 싸울수 있게 해주는 무기이다.

멀리 있는 적에게는 활을,
눈 앞의 가까운 적에게는 짧은 칼을,
말을 탄 적에게는 창을 사용하는게 좋은 것처럼,
상대에 따라 적절한 무기를 골라 싸워야한다.

사용할 수 있는 무기가 다양할 수록 전사는 효과적으로 싸울 수 있다.
사용할 수 있는 자료구조가 많을 수록 프로그래머는 좋은 프로그램을 짤 수 있다.

자료구조란 '추상 자료형'(ADT, Abstract Data Type)을 구현한 것이다.

추상자료형이란 무엇인가?

자료구조가 중요하다는 것은 알았다.
이제 자료구조라는 무기를 만들어보자.

우리가 활을 만들어야한다고 생각해보자.
먼저 재료인 나무와 실을 구해야 할 것이다.
하지만 이것은 우리가 '활'이라는 것이 무엇인지 알고 있기 때문에 할 수 있는 행동이다.
게임이나 영화에서 활의 생김새와 기능을 보았기 때문에 '활이란 무엇인가'라는 활에 대한 '개념'이 있기 때문에 가능한 것이다.

자료구조도 마찬가지다.
배열이라는 자료구조를 구현하려면, 먼저 배열에 대한 개념을 가지고 있어야한다.

우리의 선조들이 칼, 창, 활에 대한 아이디어를 만들어 냈듯이,
우리의 프로그래머 선배들도 배열, 스택, 큐, 그래프 등의 자료구조라는 자료들과 그 자료들의 기능들에 대한 아이디어들, 즉 추상 자료형(Abstract Data Type)이라는 것을 만들어놓았다.

추상 자료형은 특정 자료구조를 정의해 놓은 개념이다.

"큐(Queue)는 선입선출(First In First Out)의 구조이고,
데이터를 추가하는 push기능과 데이터를 꺼내는 pop기능이 있다."

라고 정의해 놓는 식이다.

프로그래밍 언어는 '추상자료형'을 구현하여 '자료구조'를 만든다.

우리가 쓰는 프로그래밍 언어에서 자료 구조를 사용하기 위해서는, 추상자료형에 따라 그 언어로 자료구조를 구현해야한다.

아주 기본적인 자료구조형인 배열같은 경우는 거의 모든 프로그래밍 언어에서 기본적으로 구현되어있지만, 그렇지 않은 것은 프로그래머가 구현해서 사용해야한다.
추상 자료형에서 정의된 자료구조의 인터페이스에 따라 자료구조를 구현한다.

추상자료형의 이름과 그것을 구현된 자료구조의 이름은 대부분 같지만 다른 경우도 있다.
예를 들어, 추상자료형의 딕셔너리는 'key-value 쌍'구조로 저장된 자료구조를 의미하지만
Python에서는 딕셔너리(Dictionary)가 해시테이블로 구현되어있고,
JavaScript의 맵(Map)역시 해시테이블로 구현되어 있다.(JavaScript 엔진에 따라 다를 수 있음)
따라서 각 언어에서 제공하는 API의 이름으로 내부 구현까지 판단해서는 안 된다.

자료구조의 종류

배열, 연결리스트같은 기본적인 것부터 시작해서 그것들을 조합하고 확장한 자료구조까지 여러 종류의 자료구조가 있다.

아래는 내가 아는 자료구조들이다.

정리된 자료구조들은 링크로 연결해 두었다.

각 자료구조는 해당 자료구조의 추상자료형을 설명하고, 그것을 특정 프로그래밍언어로 구현하는 방식으로 정리했다.
확장된 자료구조들에 대해서도 설명했다.

구현은 JavaScript로 했으며 가능한 한 ES6이상의 문법을 사용했다.

• 배열 Array
• 연결 리스트 Linked List
• 스택 Stack
• 큐 Queue
• 집합 Set
• 딕셔너리 Dictionary
• 해시 테이블 Hash Table
• 트리 Tree
• 힙 Heap
• 그래프 Graph