Java 9 Data Structures and Algorithms

Java 9 Data Structures and Algorithms

by Debasish Ray Chawdhuri
Released April 2017
Publisher(s): Packt Publishing
ISBN: 9781785889349

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Gain a deep understanding of the complexity of data structures and algorithms and discover the right way to write more efficient code

About 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 Programming

Who This Book Is For

This 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 more

In Detail

Java 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 approach

This 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.

Table of contents

  1. Java 9 Data Structures and Algorithms
    1. Table of Contents
    2. Java 9 Data Structures and Algorithms
    3. Credits
    4. About the Author
    5. About the Reviewer
    6. www.PacktPub.com
      1. eBooks, discount offers, and more
        1. Why subscribe?
    7. Customer Feedback
    8. Preface
      1. What this book covers
      2. What you need for this book
      3. Who this book is for
      4. Conventions
      5. Reader feedback
      6. Customer support
        1. Downloading the example code
        2. Downloading the color images of this book
        3. Errata
        4. Piracy
        5. Questions
    9. 1. Why Bother? – Basic
      1. The performance of an algorithm
        1. Best case, worst case and the average case complexity
        2. Analysis of asymptotic complexity
          1. Asymptotic upper bound of a function
          2. Asymptotic upper bound of an algorithm
          3. Asymptotic lower bound of a function
          4. Asymptotic tight bound of a function
      2. Optimization of our algorithm
      3. Fixing the problem with large powers
        1. Improving time complexity
      4. Summary
    10. 2. Cogs and Pulleys – Building Blocks
      1. Arrays
        1. Insertion of elements in an array
        2. Insertion of a new element and the process of appending it
      2. Linked list
        1. Appending at the end
        2. Insertion at the beginning
        3. Insertion at an arbitrary position
        4. Looking up an arbitrary element
        5. Removing an arbitrary element
        6. Iteration
      3. Doubly linked list
        1. Insertion at the beginning or at the end
        2. Insertion at an arbitrary location
        3. Removing the first element
        4. Removing an arbitrary element
        5. Removal of the last element
      4. Circular linked list
        1. Insertion
        2. Removal
        3. Rotation
      5. Summary
    11. 3. Protocols – Abstract Data Types
      1. Stack
        1. Fixed-sized stack using an array
        2. Variable-sized stack using a linked list
      2. Queue
        1. Fixed-sized queue using an array
        2. Variable-sized queue using a linked list
      3. Double ended queue
        1. Fixed-length double ended queue using an array
        2. Variable-sized double ended queue using a linked list
      4. Summary
    12. 4. Detour – Functional Programming
      1. Recursive algorithms
      2. Lambda expressions in Java
        1. Functional interface
        2. Implementing a functional interface with lambda
      3. Functional data structures and monads
        1. Functional linked lists
          1. The forEach method for a linked list
          2. Map for a linked list
          3. Fold operation on a list
          4. Filter operation for a linked list
          5. Append on a linked list
          6. The flatMap method on a linked list
      4. The concept of a monad
        1. Option monad
        2. Try monad
      5. Analysis of the complexity of a recursive algorithm
      6. Performance of functional programming
      7. Summary
    13. 5. Efficient Searching – Binary Search and Sorting
      1. Search algorithms
        1. Binary search
          1. Complexity of the binary search algorithm
      2. Sorting
        1. Selection sort
          1. Complexity of the selection sort algorithm
        2. Insertion sort
          1. Complexity of insertion sort
        3. Bubble sort
          1. Inversions
          2. Complexity of the bubble sort algorithm
      3. A problem with recursive calls
        1. Tail recursive functions
        2. Non-tail single recursive functions
      4. Summary
    14. 6. Efficient Sorting – quicksort and mergesort
      1. quicksort
        1. Complexity of quicksort
        2. Random pivot selection in quicksort
      2. mergesort
        1. The complexity of mergesort
        2. Avoiding the copying of tempArray
      3. Complexity of any comparison-based sorting
      4. The stability of a sorting algorithm
      5. Summary
    15. 7. Concepts of Tree
      1. A tree data structure
        1. The traversal of a tree
          1. The depth-first traversal
          2. The breadth-first traversal
      2. The tree abstract data type
      3. Binary tree
        1. Types of depth-first traversals
        2. Non-recursive depth-first search
      4. Summary
    16. 8. More About Search – Search Trees and Hash Tables
      1. Binary search tree
        1. Insertion in a binary search tree
        2. Invariant of a binary search tree
        3. Deletion of an element from a binary search tree
        4. Complexity of the binary search tree operations
      2. Self-balancing binary search tree
        1. AVL tree
          1. Complexity of search, insert, and delete in an AVL tree
      3. Red-black tree
        1. Insertion
        2. Deletion
        3. The worst case of a red-black tree
      4. Hash tables
        1. Insertion
          1. The complexity of insertion
        2. Search
          1. Complexity of the search
        3. Choice of load factor
      5. Summary
    17. 9. Advanced General Purpose Data Structures
      1. Priority queue ADT
      2. Heap
        1. Insertion
        2. Removal of minimum elements
        3. Analysis of complexity
        4. Serialized representation
        5. Array-backed heap
      3. Linked heap
        1. Insertion
        2. Removal of the minimal elements
        3. Complexity of operations in ArrayHeap and LinkedHeap
      4. Binomial forest
        1. Why call it a binomial tree?
        2. Number of nodes
        3. The heap property
        4. Binomial forest
        5. Complexity of operations in a binomial forest
      5. Sorting using a priority queue
      6. In-place heap sort
      7. Summary
    18. 10. Concepts of Graph
      1. What is a graph?
      2. The graph ADT
      3. Representation of a graph in memory
        1. Adjacency matrix
          1. Complexity of operations in a sparse adjacency matrix graph
        2. More space-efficient adjacency-matrix-based graph
          1. Complexity of operations in a dense adjacency-matrix-based graph
        3. Adjacency list
          1. Complexity of operations in an adjacency-list-based graph
        4. Adjacency-list-based graph with dense storage for vertices
          1. Complexity of the operations of an adjacency-list-based graph with dense storage for vertices
      4. Traversal of a graph
        1. Complexity of traversals
      5. Cycle detection
        1. Complexity of the cycle detection algorithm
      6. Spanning tree and minimum spanning tree
        1. For any tree with vertices V and edges E, |V| = |E| + 1
        2. Any connected undirected graph has a spanning tree
        3. Any undirected connected graph with the property |V| = |E| + 1 is a tree
        4. Cut property
        5. Minimum spanning tree is unique for a graph that has all the edges whose costs are different from one another
      7. Finding the minimum spanning tree
        1. Union find
        2. Complexity of operations in UnionFind
        3. Implementation of the minimum spanning tree algorithm
        4. Complexity of the minimum spanning tree algorithm
      8. Summary
    19. 11. Reactive Programming
      1. What is reactive programming?
      2. Producer-consumer model
        1. Semaphore
        2. Compare and set
        3. Volatile field
        4. Thread-safe blocking queue
        5. Producer-consumer implementation
        6. Spinlock and busy wait
      3. Functional way of reactive programming
      4. Summary
    20. Index

Product information

  • Title: Java 9 Data Structures and Algorithms
  • Author(s): Debasish Ray Chawdhuri
  • Release date: April 2017
  • Publisher(s): Packt Publishing
  • ISBN: 9781785889349