Java 9 Data Structures and Algorithms电子书

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