Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2017 | Book

Preliminary Concepts Read chapter Read first chapter

Guide to Data Structures

A Concise Introduction Using Java

Authors: James T. Streib, Takako Soma

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This accessible and engaging textbook/guide provides a concise introduction to data structures and associated algorithms. Emphasis is placed on the fundamentals of data structures, enabling the reader to quickly learn the key concepts, and providing a strong foundation for later studies of more complex topics. The coverage includes discussions on stacks, queues, lists, (using both arrays and links), sorting, and elementary binary trees, heaps, and hashing. This content is also a natural continuation from the material provided in the separate Springer title Guide to Java by the same authors.Topics and features: reviews the preliminary concepts, and introduces stacks and queues using arrays, along with a discussion of array-based lists; examines linked lists, the implementation of stacks and queues using references, binary trees, a range of varied sorting techniques, heaps, and hashing; presents both primitive and generic data types in each chapter, and makes use of contour diagrams to illustrate object-oriented concepts; includes chapter summaries, and asks the reader questions to help them interact with the material; contains numerous examples and illustrations, and one or more complete program in every chapter; provides exercises at the end of each chapter, as well as solutions to selected exercises, and a glossary of important terms.

This clearly-written work is an ideal classroom text for a second semester course in programming using the Java programming language, in preparation for a subsequent advanced course in data structures and algorithms. The book is also eminently suitable as a self-study guide in either academe or industry.

Table of Contents

Frontmatter
Chapter 1. Preliminary Concepts
Abstract
The chapter reviews and discusses various preliminary concepts to ensure that the reader is ready for the following chapters. The concepts include (1) elementary algorithm analysis using Big O notation, (2) data abstraction and procedural abstraction, and (3) interfaces. A simple program that implements an interface is presented in the complete program.
James T. Streib, Takako Soma
Chapter 2. Stacks Using Arrays
Abstract
Stacks, whose property is known as last-in, first-out or LIFO, is introduced and implemented using arrays. Some of the common operations for stacks such adding and removing an item, push and pop, are discussed. Using stacks, elements in the list can easily be reversed and strings can be checked for a palindrome. Further, prefix and postfix expressions are discussed where postfix expressions can be evaluated using stacks.
James T. Streib, Takako Soma
Chapter 3. Queues Using Arrays
Abstract
Unlike stacks where items can only be pushed or popped from the top, a queue has two access points and can only have items added at the rear called enqueue or removed from the front called dequeue. A queue is known as a first-in, first-out or FIFO data structure and is implemented using arrays. A queue is used to simulate a simple scheduler in an operating system in the complete program.
James T. Streib, Takako Soma
Chapter 4. Lists Using Arrays
Abstract
Unlike stacks that have one access point at the top where an item can be pushed or popped and queues which can only have items enqueued at the rear or dequeued from the front, a list can have items inserted or deleted from the front, rear, or anywhere in between. In this chapter arrays are used to implement ordered lists. The insert and delete methods in addition to the search method are discussed. In the complete program recursion is used to print strings stored in the list.
James T. Streib, Takako Soma
Chapter 5. Lists Using Objects and References
Abstract
The creation of lists using references and objects is introduced in this chapter. First references and simple objects are reviewed followed by the creation of a node class. Then a simple linked list is created which is then output both iteratively in the test program and recursively in the complete program.
James T. Streib, Takako Soma
Chapter 6. Ordered Linked Lists
Abstract
Ordered linked lists are discussed in this chapter. The insert method is created by carefully looking at inserting in the middle, end, and beginning of a linked list, as well as in an empty list. The delete method is examined and is left as an exercise. Doubly linked lists as well as an inner class are introduced and the complete program implements a list of user defined objects.
James T. Streib, Takako Soma
Chapter 7. Stacks and Queues Using References
Abstract
This chapter revisits stack and queues. Instead of using arrays as done in Chaps. 2 and 3, it uses references to implement the structures which illustrates the ideas of data and procedural abstraction. The chapter also reinforces the ideas presented in Chaps. 5 and 6. The complete program uses a graphical user interface to implement an undo button using a stack.
James T. Streib, Takako Soma
Chapter 8. Binary Trees
Abstract
Binary trees are illustrated and discussed in this chapter. Starting with a general introduction to trees, the chapter first examines binary expression trees along with preorder and in order traversals. Then binary search trees are discussed along with a test program. The complete program uses a generic class to implement a binary search tree.
James T. Streib, Takako Soma
Chapter 9. Sorting
Abstract
This chapter examines three different sorts. The first is one of the simpler ones, the insertion sort. The second is one of the fastest sorts, the quick sort. The third is called the radix (or bucket) sort and can be used for sorting physical items, but can also be adapted to sort items in memory as well. Al three sorts are illustrated using diagrams and include an elementary analysis of the algorithms. The complete program uses the quick sort to sort string items.
James T. Streib, Takako Soma
Chapter 10. Heaps
Abstract
This chapter begins by first examining heaps. Then it looks at how heaps can be used to create priority queues followed by how they can also be used to create the heap sort. Although both are implemented using arrays, drawings of both trees and arrays are included to help illustrate the concepts. After introducing the priority queue a test program is included. Then the heap sort is introduced first as a simplified sort and then modified to show the complete heap sort is implemented. Lastly, a complete program simulating how a priority queue might be used in printing is presented.
James T. Streib, Takako Soma
Chapter 11. Hashing
Abstract
This chapter is a brief introduction to hashing which is a technique that can be used to perform operations such as insertions, deletions, and searches efficiently. It introduces simple hash functions and discusses how to deal with collisions. The chapter also shows implementation of hash tables using the hashMap class and the hashSet class defined in Java Application Program Interface (API). A small database is created with the hashMap class using simple GUI in the complete program.
James T. Streib, Takako Soma
Backmatter
Metadata
Title
Guide to Data Structures
Authors
James T. Streib
Takako Soma
Copyright Year
2017
Electronic ISBN
978-3-319-70085-4
Print ISBN
978-3-319-70083-0
DOI
https://doi.org/10.1007/978-3-319-70085-4

Premium Partner

    Image Credits