[Review] Think Data Structures

July 24, 2018

7월 한빛미디어 [Think data structures] 도서에 대한 리뷰를 해보겠습니다. 한빛미디어를 통해 매번 도서 리뷰를 진행하는데... 정시를 맞춘적이 거의 없는 것 같습니다... (그래도 계속 뽑아주셔서 감사해요 ㅠㅠ 열심히 하겠습니다...)

이번 리뷰에서는 제가 주로 개발하는 Node나 Javascript에 관련된 책이 없었기 때문에, 회사 백엔드 스택으로 들어가 있는 자바에 대한 책으로 리뷰를 진행하기로 결정하고 신청했습니다.

Think data structures 도서에 대한 리뷰! 시작하겠습니다.

200p가 되지 않는 얇은 책이기 때문에 부담없이 읽을 수 있는 책입니다. 물론 한 언어의 알고리즘이란 주제로 200p라면 모든 내용을 담지 못하기 때문에, 중요한 내용들을 잘 응축해 놓았겠죠?! 그 중에서도 중요하거나 괜찮은 내용이 들은 챕터를 위주로 리뷰를 해보겠습니다.

Chap. 1 인터페이스

알고리즘에 대한 자세한 설명 전, List와 List를 implements한 ArrayList, LinkedList를 가지고 Casting에 대한 매우 간략한 (주로 Downcasting 에 대한)설명이 나옵니다. 인터페이스를 왜 쓰는지 아는건 중요한 일이죠.

Chap. 3 ArrayList 클래스

제목은 ArrayList지만, ArrayList의 구성 요소들 (get, equals, remove, removeAll 등등...)을 보여주고, LinkedList를 설명해준다. (음...? chap4가 LinkedList인데 여기서 나오네...?)

Chap. 4 LinkedList 클래스

chapter의 제목을 조금 바꿔야할 것 같네요... chap4에서는 ArrayList와 LinkedList(add 메서드의)의 성능 비교를 합니다. 몇개를 add할 때, 얼마나 걸리는지를 구한 뒤, 수식을 통해 어떤 결과가 나오는 지 확인할 수 있습니다.

Chap. 5 이중 연결 리스트

LinkedList의 앞, 뒤에 Element가 추가될 때의 성능을 비교하고, 이중 연결 리스트에서 같은 연산에서 어떤 자료구조가 효율적인지 확인해봅니다.

Chap. 6 트리 순회, Chap. 7 철학으로 가는 길

검색 엔진 (검색 엔진은 크롤링 / 인덱싱 / 검색으로 이루어짐)을 주제로 [위키트리의 본문의 제일 첫 소문자 링크를 클릭하고 이어지는 기사에서도 이를 반복하다 보면 마지막 글은 철학에 도달하게 된다] 라는 추측을 테스트 해 봅니다. 깊이 우선 탐색을 Iterator로 반복하여 탐색하는 구조에 대해 설명하는데, 짧게 설명하다보니 생략된 부분이 많아 내용을 모르고 보는 초보자들에게는 조금 어려울 수 있을 것 같네요. 반복적인 트리 순회로 크롤러를 만드는 챕터입니다.

Chap. 8 인덱서

인덱서란 검색어가 다수라면 이들의 집합을 분석하고, 검색어를 바탕으로 관련성 높은 페이지를 추리는 작업을 합니다. 콜렉션, 맵이 이에 알맞는 자료구조지만 이 중 속도면에서는 맵이 더 빠르기에, 맵을 이용해 인덱서를 구성해봅니다.

Chap. 9 Map 인터페이스

가장 많이 사용하는 자료구조 중 하나인 Map입니다. 반복적이고 단순한 구조인 LinearMap에 대해 설명되어 있습니다.

Chap. 10 해싱, Chap. 11 HashMap 클래스

Map 인터페이스를 해시값으로 구현한 해싱입니다. 반복으로 키에 매핑되는 값을 구해내는 LinearMap과는 달리, 해시된 키를 이용하여 값을 구하는 방법입니다.

Chap. 12 TreeMap 클래스, Chap. 13 이진 탐색 트리

해시맵에서도 O(n)구조를 벗어날 수 없었기에, 조금 더 빠른 구조인 TreeMap이 나왔습니다. (O(logn)) 이 TreeMap에 사용된 이진 탐색 트리 구조가 어떤 것인지, 또 다른 트리구조엔 어떤것이 있는지 알아봅니다.

추가적인 chapter가 있지만, 필수적이라기보단, 성능 향상과 추가 기능들을 알려줍니다.

이번 리뷰 도서는 조금... 애매합니다. 주관적으로 생각하기에는 난이도가 고르지 못한 느낌이었고, chapter의 제목이 내용과 매치되지 않는 부분이 존재했습니다. 문장들이 이해하긴 쉬웠지만 조금 다듬어야 될 것 같습니다.

이번 리뷰는 여기서 마치겠습니다.

감사합니다.