Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Best of 2016 Recommended by Editor Recommended by Reviewer Recommended by Reader
Search
Guide to data structures : a concise introduction using Java
Streib J., Soma T., Springer International Publishing, New York, NY, 2018. 376 pp. Type: Book (978-3-319700-83-0)
Date Reviewed: Jul 16 2018

Data structures seem to be the bane of every computer science (CS) undergraduate’s education. Thus, a good data structures text aimed at undergraduates is a necessity. Even though relatively few programmers actually implement data structures (as opposed to objects, which are semi-structured bags of data), understanding data structures and their behavior is essential. And yes, questions about data structures are common in interviews.

This text is intended to provide undergraduates using Java with a concise, focused, and relatively simple coverage of some of the basic data structures in use. These include arrays, linked lists, trees, heaps (in arrays), and hash tables.

There are 11 chapters:

(1) “Preliminary Concepts” includes the required skills for reading the book, a quick discussion of time complexity, and some details of Java that will be useful later in the text.
(2) “Stacks Using Arrays” covers building a stack structure in an array and some simple applications using stacks.
(3) “Queues using Arrays” covers building a queue in an array.
(4) “Lists Using Arrays” covers using an array to hold ordered linked lists.
(5) “Lists Using Objects and References” covers building unordered linked lists with objects and references and includes a bit of recursion.
(6) “Ordered Linked Lists” extends chapter 5 to cover building ordered lists using objects and references.
(7) “Stacks and Queues Using References” uses the basic linked list structure to build stacks and queues.
(8) “Binary Trees” includes binary search trees and preorder, inorder, and postorder traversals.
(9) “Sorting” covers insertion, sort, quick sort, and radix sort.
(10) “Heaps” is on building and using heaps in an array.
(11) “Hashing” covers building and using a hash table.

The book covers the algorithms and data structures well with clear language, abundant diagrams, and good exercises. It could be a good introduction for curricula using Java as a primary teaching language. It does feel like it is aimed at students who are struggling a bit with programming and with the underlying algorithms.

I have some problems with it, though. Most of the programs use prompts for user input as a way to run the code; as anyone who has done this knows, this gets tedious very fast. Few students are likely to actually input more than a couple entries for, say, a linked list, and even for those who do, entering the same sequence of inputs more than once is unlikely. Among other things, this means that there are few repeatable tests. There’s nothing wrong with using an array of values as input; it encourages a focus on testable code. Using a combination of specified inputs and randomly generated inputs is even more useful and can often, especially in student code, uncover problems quickly--if you have a sort routine that can sort a large number of randomly generated lists of integers, you may not be certain that it works, but you can have a good deal more confidence. It helps no one if you can write a sort function that doesn’t sort, or that loses input data along the way.

Furthermore, most data structures have correctness criteria that can be applied. It is both instructive and helpful to encourage students to build routines that test for correctness and use them as part of the testing process. For instance, if you build a binary search tree from a shuffled list of the integers from zero to 100, you can then quite easily test to be sure that it is indeed a binary search tree (and this often helps understand the structure), but you can also check to be sure that all the numbers are present in the final tree. Similarly, building a heap in an array is a bit more complicated if you write an “is_heap” function that tests whether it is a valid heap, though not seriously so. Doing that makes debugging substantially faster and easier. The scary word “invariant” does not need to be used for the idea to be useful.

Spending time on invariants, debugging, and testing may be a distraction, but it is likely to pay off for students in the end, for example, in future courses or in their careers.

Insertion sort is mentioned in a few places, but the authors don’t seem to point out that part of the process of inserting an element in a heap and maintaining the heap invariant is essentially an insertion sort--noting such commonalities is an important part of learning abstraction.

Finally, recursion is mentioned, but it can be useful to spend a bit of time on it. Most students find recursion a bit opaque (and the more time spent on it, the easier it becomes), whereas some students seem to think in terms of recursion naturally. Having recursive versions of an algorithm alongside iterative versions can help both sets of students.

These potential shortcomings would not be so serious in a text that covered many more data structures, or in a text that covered data structures more abstractly, but in this basic a text they feel far more serious.

There is a website, but it does not contain the text of the programs as claimed in the foreword. This isn’t entirely a bad thing, though, as actually typing in programs gives learners better familiarity with the language used, as well as ample opportunity to debug the inevitable errors that will occur. Interestingly enough, you can download a “high definition” version of the book cover.

With more coverage of things, as noted above, or with instructors who are careful to cover debugging and correctness, this could be a decent text.

Reviewer:  Jeffrey Putnam Review #: CR146152 (1809-0479)
Bookmark and Share
  Editor Recommended
Featured Reviewer
 
 
Data Structures (E.1 )
 
 
Java (D.3.2 ... )
 
 
Object-Oriented Programming (D.1.5 )
 
Would you recommend this review?
yes
no
Other reviews under "Data Structures": Date
Handbook of algorithms and data structures
Gonnet G. (ed), Baeza-Yates R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991. Type: Book (9780201416077)
Feb 1 1992
Data structures and algorithm analysis
Weiss M., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1992. Type: Book (9780805390544)
Aug 1 1992
Data structures and program design in C
Kruse R., Leung B., Tondo C., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780137256495)
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy