이 책의 주요 특징

독자들의 쉬운 이해를 위해 본서는 대부분의 자료구조를 다음의 다섯 단계에 따라 설명한다.

1. 주어진 자료구조에 대한 이해
2. 핵심 아이디어 소개
3. 예제
4. 파이썬 프로그램
5. 수행시간 분석

기본적으로 각 자료구조의 필요성을 소개하고, 자료구조를 이해하는데 도움이 되는 핵심 아이디어를 살펴본다. 또한 자료구조에 대한 예제를 통해 이해를 도우며, 파이썬(Python 3) 프로그램으로 구현한 자료구조를 제시하고, 수행시간을 분석한다. 아울러 자료구조의 응용 및 활용 분야를 살펴보고, 대부분의 파이썬 프로그램을 Eclipse 통합 개발 환경에서 실제로 실행시킨 결과 화면 또한 보여준다. 단, 몇몇 자료구조들에 대한 프로그램은 너무 길어 생략하였고 개념 위주로 서술하였다.

이 책의 주요 내용

제1장 자료구조를 배우기 위한 준비
자료구조와 추상 데이터 타입, 수행시간의 분석, 수행시간의 점근 표기법, 파이썬 언어의 기본 지식, 그리고 순환에 대해 살펴본다. 단, 본서에서 다루는 파이썬 언어의 기본 지식은 본서에 제공된 파이썬 프로그램을 이해하기 위해 필요한 파이썬의 일부 구문, 함수 등만을 포함하고 있다.

제2장 리스트
단순연결리스트, 이중연결리스트, 원형연결리스트를 설명한다.

제3장 스택과 큐
스택, 큐, 데크 자료구조를 다룬다.

제4장 트리
일반적인 트리, 이진트리, 이진트리에서의 순회 및 기타 기본적인 연산, 이진힙을 각각 소개한다.

제5장 탐색트리
이진탐색트리, AVL 트리, 2-3트리, 레드블랙트리, B-트리를 소개하며, 특히 이진탐색트리, AVL 트리는 파이썬 프로그램을 통하여 상세히 설명한다.

제6장 해시 테이블
해시함수, 출동 해결 방법으로 선형조사, 이차조사, 랜덤조사, 이중해싱, 체이닝을 배우고, 새로운 충돌 해결방식인 2-방향 체이닝(Two-Way Chaining), 뻐꾸기 해싱(Cuckoo Hashing)을 소개하며, 재해싱과 동적해싱을 각각 살펴본다.

제7장 정렬
기본적인 정렬알고리즘인 선택정렬, 삽입정렬을 다루고, 이보다 효율적인 쉘정렬, 합병정렬, 퀵정렬, 힙정렬을 살펴보며, 특정 환경에서 사용되는 기수정렬과 외부 정렬을 소개한다. 또한 비교적 최근에 소개되었고 자바의 시스템 정렬로 활용되는 이중피벗퀵정렬(Dual Pivot Quicksort)과 파이썬, 자바 SE7, 안드로이드의 시스템 정렬로 채택된 Tim Sort는 부록에서 소개한다.

제8장 그래프
깊이우선탐색, 너비우선탐색을 공부하고, 기본적인 그래프 알고리즘인 연결성분 찾기와 위상정렬에 대해 살펴본다. 또한 Kruskal, Prim, Sollin의 최소신장트리 알고리즘을 소개하고, Dijkstra와 Floyd-Warshall 최단경로 알고리즘을 소개한다.

부록
파이썬 메모리를 살펴보며, 이중피벗퀵정렬(Dual Pivot Quick Sort)과 Tim Sort를 살펴보며, 정렬 문제의 하한을 알아보고, 최소신장트리 알고리즘들이 항상 정확한 해를 리턴하는 지를 Cut Property의 증명을 통하여 알아본다.