What is the most comprehensive book on data structures?

views:

416

answers:

+5 Q:

What is the most comprehensive book on data structures?

I am looking for a comprehensive book on data structures which covers wide range of data structures, both fundamental and advanced, with implementation code.

I have consulted a few books but all of them skip some fundamental data structures here and there. For example, I am looking for some book which covers all variants of tree data structure including Red-Black trees, 2-3-4 trees, B trees, various types of Heaps etc, ALL with implementation code, not merely with short descriptions. Also, I am looking for a book whose main focus is on data structures rather than algorithms, as many book which cover both go more in detail on algorithms and skips details on data structures.

It doesn't matter what programming language it uses for implementation, it can be any, though preferably C, C++, C# or JAVA.

Anyone? Thanks.

+6 A:

I find the classical Introduction to Algorithms to be a very pleasant read. It covers all the data structures you mentioned, and it provides pseudo-code for most implementations.

There's also Algorithms in C and Algorithms in Java, both by Robert Sedgewick, but I don't have a copy with me to check what data structures they cover. These books are a bit more practical than Introduction to Algorithms (which has lots of theory and mathematical proofs).

JG 2009-09-08 13:23:49

I'll second JG's suggestion. I used this book in college and it was very helpful. There was another that has great implementations of some graph and tree structures... I'll post back when I remember what it was.

Cory Larson 2009-09-08 13:30:46

+1 - Intro to Algorithms is a very good book on the subject. It documents most of the data structures the OP describes. Note that in most cases you need to understand various algorithms for insertion, deletion, node rotation etc. in order to use the data structure in the first place.

ConcernedOfTunbridgeWells 2009-09-08 13:31:38

I can't comment on the book, because I haven't read it but. It is on my list from other recommendations. Also the MIT course Introduction to Algorithms uses this book and the course is on MIT's [OpenCourseware site][1] [1]: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm

bkoch 2009-09-08 13:53:40

That's the one I used in college. Good recommendation.

Brian Gideon 2009-09-08 13:58:54

Thanks JG. I already own Introduction to Algorithms, it is certainly a great source but not a comprehensive one in my opinion. It is mainly an algorithms book. It skips a few data structures or only briefly discusses them (e.g., 2-3-4 trees, Doubly linked list). And most importantly it doesn't provide implementation code.

Jahanzeb Farooq 2009-09-12 14:40:05

Fair enough. You can also take a look at Robert Sedgewick's page and his books; some of the implementation code that is used in the books (if not all) is provided in the page.

JG 2009-09-12 16:23:38

+6 A:

The Art of Computer Programming by Knuth is a classic that contains mostly fundamental data structures. There is a lot of theory and math in there so it is not for the faint of heart.

Brian Gideon 2009-09-08 13:29:00

It is very thorough, but it's not the most accessible of works. You definitely have to be comfortable with idiomatic maths jargon to use it in realtime (i.e. not spend most of your time deciphering it). Most computer science courses are not taught in this way, so there is something of a culture gap. Cormen, Lieserson and Rivest's book is considerably more accessible and covers most of the relevant material.

ConcernedOfTunbridgeWells 2009-09-08 13:38:12

@ConcernedOfTunbridgeWells: Then these "computer science courses" are bad.

Developer Art 2009-09-08 13:40:46

@New in town: Wow, that's quite a statement. Many MIT lectures are based on the Introduction to Algorithms book (sure, one of the authors is the lecturer, so some bias here : )), and I believe it uses the "right amount" of math for a CS book. Algorithms books should not be a contest of "who uses more LaTeX symbols".

JG 2009-09-08 13:52:30

Personally, I find Knuth's use of the MIX assembly language for examples incredibly frustrating and outdated. I would hate using this book in an actual class. Nevertheless, I felt a mention of it was compulsory in the context of the question asked.

Brian Gideon 2009-09-08 14:03:19

I have only briefly looked into TAOCP. Isn't it mainly an algorithms book? At least I don't remember seeing data structures there. And definitely not implementation code. Above this all, lots of mind-torturing math.

Jahanzeb Farooq 2009-09-12 14:48:13

There is definitely data structures in there. But, they are pretty basic (linked list, hashtable, etc). You will not find skip lists or splay trees for example.

Brian Gideon 2009-09-12 15:17:47

+2 A:

George Stocker 2009-09-08 13:37:44

Thanks. I actually own a slightly shorter version of this book, titled "Data Structures and Algorithms in 24 Hours" by Robert Lafore (although it is in C++). It is definitely a great (quick) introduction to data structures, with implementation code for most of the data structures. Highly recommendable. However given that it is a 24 hour book it skips a few data structures here and there or doesn't include code. This book you are recommending apparently is the comprehensive version. And based on my experience of the previous, perhaps the one I am looking for.

Jahanzeb Farooq 2009-09-12 15:17:07

It's insanely detailed; Hell, I don't use Java any more but this book still harkens my desk monthly.

George Stocker 2009-09-12 15:20:44

+1 A:

The book JG suggested is great for an Algorithms class, but I can't remember if the "implementations" were in pseudocode or not.

Data Structures and the Java Collections Framework, 2nd ed. is helpful for several tree and graph structures, but it doesn't cover all of the ones mentioned in your post. I used it in school and have gone back to it for reference more than once at my job.

Most of the source code for the book is available for download at the publisher's website, but it's all plainly printed right in the book as well.

Cory Larson 2009-09-08 13:40:08

+2 A:

Jahanzeb Farooq 2009-09-17 22:44:17

I can suggest "Data Structures, Algorithms, and Performance" by Derick Wood.

CesarGon 2009-11-17 03:41:58

File Structures: An Object-Oriented Approach

Michael J. Folk, Bill Zoellick, Greg Riccardi

File Structures: An Object-Oriented Approach

http://www.amazon.com/File-Structures-Object-Oriented-Approach-C/dp/0201874016

This was generally used where I studied. It's a very nice book to read, covering several trees, hash tables, with an emphasis on how to move them efficiently to and from disk. It's a good practical approach without too much algorithmic analysis.

It has quite a lot of C++ code in it. It's good for conveying understanding but it's not written the way I'd write some of the algorithms.

Edmund 2009-11-17 03:55:15

ansaurus

tags:

views:

answers:

What is the most comprehensive book on data structures?

related questions