Java 9 Data Structures and Algorithms

Debasish Ray Chawdhuri

• Publisher: Packt Publishing
• Year: 2017
• ISBN:
  9781785888076
• Edition: 1
• Topic: Informatica
• Subtopic: Programmazione in Java

Gain a deep understanding of the complexity of data structures and algorithms and discover the right way to write more efficient codeAbout This Book• This book provides complete coverage of reactive and functional data structures• Based on the latest version of Java 9, this book illustrates the impact of new features on data structures• Gain exposure to important concepts such as Big-O Notation and Dynamic ProgrammingWho This Book Is ForThis book is for Java developers who want to learn about data structures and algorithms. Basic knowledge of Java is assumed.What You Will Learn• Understand the fundamentals of algorithms, data structures, and measurement of complexity• Find out what general purpose data structures are, including arrays, linked lists, double ended linked lists, and circular lists• Get a grasp on the basics of abstract data types—stack, queue, and double ended queue• See how to use recursive functions and immutability while understanding and in terms of recursion• Handle reactive programming and its related data structures• Use binary search, sorting, and efficient sorting—quicksort and merge sort• Work with the important concept of trees and list all nodes of the tree, traversal of tree, search trees, and balanced search trees• Apply advanced general purpose data structures, priority queue-based sorting, and random access immutable linked lists• Gain a better understanding of the concept of graphs, directed and undirected graphs, undirected trees, and much moreIn DetailJava 9 Data Structures and Algorithms covers classical, functional, and reactive data structures, giving you the ability to understand computational complexity, solve problems, and write efficient code. This book is based on the Zero Bug Bounce milestone of Java 9.We start off with the basics of algorithms and data structures, helping you understand the fundamentals and measure complexity. From here, we introduce you to concepts such as arrays, linked lists, as well as abstract data types such as stacks and queues. Next, we'll take you through the basics of functional programming while making sure you get used to thinking recursively.We provide plenty of examples along the way to help you understand each concept. You will get the also get a clear picture of reactive programming, binary searches, sorting, search trees, undirected graphs, and a whole lot more!Style and approachThis book will teach you about all the major algorithms in a step-by-step manner. Special notes on the Big-O Notation and its impact on algorithms will give you fresh insights.

Java 9 Data Structures and Algorithms

---

Table of Contents

Java 9 Data Structures and Algorithms

Credits

About the Author

About the Reviewer

www.PacktPub.com

eBooks, discount offers, and more

Why subscribe?

Customer Feedback

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Downloading the color images of this book

Errata

Piracy

Questions

1. Why Bother? – Basic

The performance of an algorithm

Best case, worst case and the average case complexity

Analysis of asymptotic complexity

Asymptotic upper bound of a function

Asymptotic upper bound of an algorithm

Asymptotic lower bound of a function

Asymptotic tight bound of a function

Optimization of our algorithm

Fixing the problem with large powers

Improving time complexity

Summary

2. Cogs and Pulleys – Building Blocks

Arrays

Insertion of elements in an array

Insertion of a new element and the process of appending it

Linked list

Appending at the end

Insertion at the beginning

Insertion at an arbitrary position

Looking up an arbitrary element

Removing an arbitrary element

Iteration

Doubly linked list

Insertion at the beginning or at the end

Insertion at an arbitrary location

Removing the first element

Removing an arbitrary element

Removal of the last element

Circular linked list

Insertion

Removal

Rotation

Summary

3. Protocols – Abstract Data Types

Stack

Fixed-sized stack using an array

Variable-sized stack using a linked list

Queue

Fixed-sized queue using an array

Variable-sized queue using a linked list

Double ended queue

Fixed-length double ended queue using an array

Variable-sized double ended queue using a linked list

Summary

4. Detour – Functional Programming

Recursive algorithms

Lambda expressions in Java

Functional interface

Implementing a functional interface with lambda

Functional data structures and monads

Functional linked lists

The forEach method for a linked list

Map for a linked list

Fold operation on a list

Filter operation for a linked list

Append on a linked list

The flatMap method on a linked list

The concept of a monad

Option monad

Try monad

Analysis of the complexity of a recursive algorithm

Performance of functional programming

Summary

5. Efficient Searching – Binary Search and Sorting

Search algorithms

Binary search

Complexity of the binary search algorithm

Sorting

Selection sort

Complexity of the selection sort algorithm

Insertion sort

Complexity of insertion sort

Bubble sort

Inversions

Complexity of the bubble sort algorithm

A problem with recursive calls

Tail recursive functions

Non-tail single recursive functions

Summary

6. Efficient Sorting – quicksort and mergesort

quicksort

Complexity of quicksort

Random pivot selection in quicksort

mergesort

The complexity of mergesort

Avoiding the copying of tempArray

Complexity of any comparison-based sorting

The stability of a sorting algorithm

Summary

7. Concepts of Tree

A tree data structure

The traversal of a tree

The depth-first traversal

The breadth-first traversal

The tree abstract data type

Binary tree

Types of depth-first traversals

Non-recursive depth-first search

Summary

8. More About Search – Search Trees and Hash Tables

Binary search tree

Insertion in a binary search tree

Invariant of a binary search tree

Deletion of an element from a binary search tree

Complexity of the binary search tree operations

Self-balancing binary search tree

AVL tree

Complexity of search, insert, and delete in an AVL tree

Red-black tree

Insertion

Deletion

The worst case of a red-black tree

Hash tables

Insertion

The complexity of insertion

Search

Complexity of the search

Choice of load factor

Summary

9. Advanced General Purpose Data Structures

Priority queue ADT

Heap

Insertion

Removal of minimum elements

Analysis of complexity

Serialized representation

Array-backed heap

Linked heap

Insertion

Removal of the minimal elements

Complexity of operations in ArrayHeap and LinkedHeap

Binomial forest

Why call it a binomial tree?

Number of nodes

The heap property

Binomial forest

Complexity of operations in a binomial forest

Sorting using a priority queue

In-place heap sort

Summary

10. Concepts of Graph

What is a graph?

The graph ADT

Representation of a graph in memory

Adjacency matrix

Complexity of operations in a sparse adjacency matrix graph

More space-efficient adjacency-matrix-based graph

Complexity of operations in a dense adjacency-matrix-based graph

Adjacency list

Complexity of operations in an adjacency-list-based graph

Adjacency-list-based graph with dense storage for vertices

Complexity of the operations of an adjacency-list-based graph with dense storage for vertices

Traversal of a graph

Complexity of traversals

Cycle detection

Complexity of the cycle detection algorithm

Spanning tree and minimum spanning tree

For any tree with vertices V and edges E, |V| = |E| + 1

Any connected undirected graph has a spanning tree

Any undirected connected graph with the property |V| = |E| + 1 is a tree

Cut property

Minimum spanning tree is unique for a graph that has all the edges whose costs are different from one another

Finding the minimum spanning tree

Union find

Complexity of operations in UnionFind

Implementation of the minimum spanning tree algorithm

Complexity of the minimum spanning tree algorithm

Summary

11. Reactive Programming

What is reactive programming?

Producer-consumer model

Semaphore

Compare and set

Volatile field

Thread-safe blocking queue

Producer-consumer implementation

Spinlock and busy wait

Functional way of reactive programming

Summary

Index

Java 9 Data Structures and Algorithms

Copyright © 2017 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

First published: April 2017

Production reference: 1250417

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham B3 2PB, UK.

ISBN 978-1-78588-934-9

www.packtpub.com

Credits

Author

Debasish Ray Chawdhuri

Reviewer

Miroslav Wengner

Commissioning Editor

Kunal Parikh

Acquisition Editor

Chaitanya Nair

Content Development Editor

Nikhil Borkar

Technical Editor

Madhunikita Sunil Chindarkar

Copy Editor

Muktikant Garimella

Project Coordinator

Vaidehi Sawant

Proofreader

Safis Editing

Indexer

Mariammal Chettiyar

Graphics

Abhinash Sahu

Production Coordinator

Nilesh Mohite

Cover ...