Java 9 Data Structures And Algorithms: A Step By Guide To Algorithms
User Manual: Pdf
Open the PDF directly: View PDF 
.
Page Count: 340
| Download | |
| Open PDF In Browser | View PDF |
Java 9 Data Structures and
Algorithms
A step-by-step guide to data structures and algorithms
Debasish Ray Chawdhuri
BIRMINGHAM - MUMBAI
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 Work
Nilesh Mohite
About the Author
Debasish Ray Chawdhuri is an established Java developer and has been in the
industry for the last 8 years. He has developed several systems, right from CRUD
applications to programming languages and big data processing systems. He
had provided the first implementation of extensible business reporting language
specification, and a product around it, for the verification of company financial data
for the Government of India while he was employed at Tata Consultancy Services
Ltd. In Talentica Software Pvt. Ltd., he implemented a domain-specific programming
language to easily implement complex data aggregation computation that would
compile to Java bytecode. Currently, he is leading a team developing a new highperformance structured data storage framework to be processed by Spark. The
framework is named Hungry Hippos and will be open sourced very soon. He also
blogs at http://www.geekyarticles.com/ about Java and other computer sciencerelated topics.
He has worked for Tata Consultancy Services Ltd., Oracle India Pvt. Ltd., and
Talentica Software Pvt. Ltd.
I would like to thank my dear wife, Anasua, for her continued
support and encouragement, and for putting up with all my
eccentricities while I spent all my time writing this book. I would also
like to thank the publishing team for suggesting the idea of this book
to me and providing all the necessary support for me to finish it.
About the Reviewer
Miroslav Wengner has been a passionate JVM enthusiast ever since he
joined SUN Microsystems in 2002. He truly believes in distributed system
design, concurrency, and parallel computing. One of Miro's biggest hobby is
the development of autonomic systems. He is one of the coauthors of and main
contributors to the open source Java IoT/Robotics framework Robo4J.
Miro is currently working on the online energy trading platform for enmacc.de
as a senior software developer.
I would like to thank my family and my wife, Tanja, for big support
during reviewing this book.
www.PacktPub.com
eBooks, discount offers, and more
Did you know that Packt offers eBook versions of every book published, with PDF
and ePub files available? You can upgrade to the eBook version at www.PacktPub.
com and as a print book customer, you are entitled to a discount on the eBook copy.
Get in touch with us at customercare@packtpub.com for more details.
At www.PacktPub.com, you can also read a collection of free technical articles, sign
up for a range of free newsletters and receive exclusive discounts and offers on Packt
books and eBooks.
https://www.packtpub.com/mapt
Get the most in-demand software skills with Mapt. Mapt gives you full access to all
Packt books and video courses, as well as industry-leading tools to help you plan
your personal development and advance your career.
Why subscribe?
•
Fully searchable across every book published by Packt
•
Copy and paste, print, and bookmark content
•
On demand and accessible via a web browser
Customer Feedback
Thanks for purchasing this Packt book. At Packt, quality is at the heart of our
editorial process. To help us improve, please leave us an honest review on this book's
Amazon page at https://www.amazon.com/dp/1785889346.
If you'd like to join our team of regular reviewers, you can e-mail us at
customerreviews@packtpub.com. We award our regular reviewers with free
eBooks and videos in exchange for their valuable feedback. Help us be relentless in
improving our products!
Table of Contents
Preface
Chapter 1: Why Bother? – Basic
vii
1
Asymptotic upper bound of a function
Asymptotic upper bound of an algorithm
Asymptotic lower bound of a function
Asymptotic tight bound of a function
4
8
8
9
The performance of an algorithm
Best case, worst case and the average case complexity
Analysis of asymptotic complexity
Optimization of our algorithm
Fixing the problem with large powers
Improving time complexity
Summary
Chapter 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
[i]
2
3
4
10
10
11
13
15
16
16
18
20
21
23
24
25
27
28
30
31
32
33
34
Table of Contents
Removal of the last element
Circular linked list
Insertion
Removal
Rotation
Summary
36
37
38
38
39
40
Chapter 3: Protocols – Abstract Data Types
41
Chapter 4: Detour – Functional Programming
57
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
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
Chapter 5: Efficient Searching – Binary Search and Sorting
Search algorithms
Binary search
Complexity of the binary search algorithm
[ ii ]
42
43
45
47
48
50
52
53
55
56
58
60
60
61
62
62
65
66
67
70
74
74
76
76
82
86
89
90
91
92
93
96
Table of Contents
Sorting
Selection sort
Complexity of the selection sort algorithm
98
98
101
Insertion sort
102
Bubble sort
105
Complexity of insertion sort
104
Inversions
Complexity of the bubble sort algorithm
106
107
A problem with recursive calls
Tail recursive functions
Non-tail single recursive functions
Summary
108
109
112
114
Chapter 6: Efficient Sorting – quicksort and mergesort
115
Chapter 7: Concepts of Tree
135
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
A tree data structure
The traversal of a tree
115
120
122
123
126
127
129
133
134
136
139
The depth-first traversal
The breadth-first traversal
140
142
The tree abstract data type
Binary tree
Types of depth-first traversals
Non-recursive depth-first search
Summary
Chapter 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
[ iii ]
143
145
147
149
153
155
156
158
160
162
167
168
171
176
Table of Contents
Red-black tree
Insertion
Deletion
The worst case of a red-black tree
Hash tables
Insertion
177
179
183
188
190
191
The complexity of insertion
193
Search
193
Complexity of the search
194
Choice of load factor
Summary
194
194
Chapter 9: Advanced General Purpose Data Structures
195
Chapter 10: Concepts of Graph
225
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
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
[ iv ]
195
196
197
198
199
200
201
204
206
207
209
209
211
212
212
214
221
221
222
223
226
228
229
230
234
235
243
Table of Contents
Adjacency list
244
Adjacency-list-based graph with dense storage for vertices
251
Complexity of operations in an adjacency-list-based graph
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
250
258
259
264
264
267
267
268
269
269
269
271
272
273
277
277
279
280
Chapter 11: Reactive Programming
281
Index
315
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
[v]
282
283
283
284
285
286
289
296
301
313
Preface
Java has been one of the most popular programming languages for enterprise
systems for decades now. One of the reasons for the popularity of Java is its platform
independence, which lets one write and compile code on any system and run it on
any other system, irrespective of the hardware and the operating system. Another
reason for Java's popularity is that the language is standardized by a community
of industry players. The latter enables Java to stay updated with the most recent
programming ideas without being overloaded with too many useless features.
Given the popularity of Java, there are plenty of developers actively involved in Java
development. When it comes to learning algorithms, it is best to use the language
that one is most comfortable with. This means that it makes a lot of sense to write an
algorithm book, with the implementations written in Java. This book covers the most
commonly used data structures and algorithms. It is meant for people who already
know Java but are not familiar with algorithms. The book should serve as the first
stepping stone towards learning the subject.
What this book covers
Chapter 1, Why Bother? – Basic, introduces the point of studying algorithms and data
structures with examples. In doing so, it introduces you to the concept of asymptotic
complexity, big O notation, and other notations.
Chapter 2, Cogs and Pulleys – Building Blocks, introduces you to array and the different
kinds of linked lists, and their advantages and disadvantages. These data structures
will be used in later chapters for implementing abstract data structures.
Chapter 3, Protocols – Abstract Data Types, introduces you to the concept of abstract
data types and introduces stacks, queues, and double-ended queues. It also covers
different implementations using the data structures described in the previous chapter.
[ vii ]
Preface
Chapter 4, Detour – Functional Programming, introduces you to the functional
programming ideas appropriate for a Java programmer. The chapter also introduces
the lambda feature of Java, available from Java 8, and helps readers get used to the
functional way of implementing algorithms. This chapter also introduces you to the
concept of monads.
Chapter 5, Efficient Searching – Binary Search and Sorting, introduces efficient searching
using binary searches on a sorted list. It then goes on to describe basic algorithms
used to obtain a sorted array so that binary searching can be done.
Chapter 6, Efficient Sorting – Quicksort and Mergesort, introduces the two most popular
and efficient sorting algorithms. The chapter also provides an analysis of why this is
as optimal as a comparison-based sorting algorithm can ever be.
Chapter 7, Concepts of Tree, introduces the concept of a tree. It especially introduces
binary trees, and also covers different traversals of the tree: breadth-first and
depth-first, and pre-order, post-order, and in-order traversal of binary tree.
Chapter 8, More About Search – Search Trees and Hash Tables, covers search using
balanced binary search trees, namely AVL, and red-black trees and hash-tables.
Chapter 9, Advanced General Purpose Data Structures, introduces priority queues and
their implementation with a heap and a binomial forest. At the end, the chapter
introduces sorting with a priority queue.
Chapter 10, Concepts of Graph, introduces the concepts of directed and undirected
graphs. Then, it discusses the representation of a graph in memory. Depth-first and
breadth-first traversals are covered, the concept of a minimum-spanning tree is
introduced, and cycle detection is discussed.
Chapter 11, Reactive Programming, introduces the reader to the concept of reactive
programming in Java. This includes the implementation of an observable patternbased reactive programming framework and a functional API on top of it. Examples
are shown to demonstrate the performance gain and ease of use of the reactive
framework, compared with a traditional imperative style.
What you need for this book
To run the examples in this book, you need a computer with any modern popular
operating system, such as some version of Windows, Linux, or Macintosh. You
need to install Java 9 in your computer so that javac can be invoked from the
command prompt.
[ viii ]
Preface
Who this book is for
This book is for Java developers who want to learn about data structures and
algorithms. A basic knowledge of Java is assumed.
Conventions
In this book, you will find a number of text styles that distinguish between different
kinds of information. Here are some examples of these styles and an explanation of
their meaning.
Code words in text, database table names, folder names, filenames, file extensions,
pathnames, dummy URLs, user input, and Twitter handles are shown as follows:
"We can include other contexts through the use of the include directive."
A block of code is set as follows:
public static void printAllElements(int[] anIntArray){
for(int i=0;i |g(x)| for all sufficiently large x, then f(x) =
O(h(x)).
°°
For example, x3 = O(x4), because if x is sufficiently large, x4 > x3.
Note that whenever there is an inequality on functions, we are only interested in
what happens when x is large; we don't bother about what happens for small x.
To summarize the above definition, you can drop constant
multipliers (rule 2) and ignore lower order terms (rule 3). You
can also overestimate (rule 4). You can also do all combinations
for those because rules can be applied any number of times.
We had to consider the absolute values of the function to cater to the case when
values are negative, which never happens in running time, but we still have it for
completeness.
There is something about the sign = that is not usual. Just
because f(x) = O(g(x)), it does not mean, O(g(x)) = f(x). In fact,
the last one does not even mean anything.
It is enough for all purposes to just know the preceding definition of the big
O notation. You can read the following formal definition if you are interested.
Otherwise you can skip the rest of this subsection.
The preceding idea can be summarized in a formal way. We say the expression f(x)
= O(g(x)) means that positive constants M and x0 exist, such that |f(x)| < M|g(x)|
whenever x > x0. Remember that you just have to find one example of M and x0 that
satisfy the condition, to make the assertion f(x) = O(g(x)).
[5]
Why Bother? – Basic
For example, Figure 1 shows an example of a function T(x) = 100x2+2000x+200. This
function is O(x2), with some x0 = 11 and M = 300. The graph of 300x2 overcomes the
graph of T(x) at x=11 and then stays above T(x) up to infinity. Notice that the function
300x2 is lower than T(x) for smaller values of x, but that does not affect our conclusion.
Figure 1. Asymptotic upper bound
To see that it's the same thing as the previous four points, first think of x0 as the
way to ensure that x is sufficiently large. I leave it up to you to prove the above four
conditions from the formal definition.
I will, however, show some examples of using the formal definition:
•
5x2 = O(x2) because we can say, for example, x0 = 10 and M = 10 and thus f(x)
< Mg(x) whenever x > x0, that is, 5x2 < 10x2 whenever x > 10.
•
It is also true that 5x2 = O(x3) because we can say, for example, x0 = 10 and M
= 10 and thus f(x) < Mg(x) whenever x > x0, that is, 5x2 < 10x3 whenever x >
10. This highlights a point that if f(x) = O(g(x)), it is also true that f(x) = O(h(x))
if h(x) is some functions that grows at least as fast as f(x).
[6]
Chapter 1
•
How about the function f(x) = 5x2 - 10x + 3? We can easily see that when x is
sufficiently large, 5x2 will far surpass the term 10x. To prove my point, I can
simply say x>5, 5x2 > 10x. Every time we increment x by one, the increment
in 5x2 is 10x + 1 and the increment in 10x is just a constant, 10. 10x+1 > 10 for
all positive x, so it is easy to see why 5x2 is always going to stay above 10x as
x goes higher and higher.
In general, any polynomial of the form anxn + an-1xn-1 + an-2xn-2 + … + a0 = O(xn). To
show this, we will first see that a0 = O(1). This is true because we can have x0 = 1 and
M = 2|a0|, and we will have |a0| < 2|a0| whenever x > 1.
Now, let us assume it is true for some n. Thus, anxn + an-1xn-1 + an-2xn-2 + … + a0 = O(xn).
What it means, of course, is that some Mn and x0 exist, such that |anxn + an-1xn-1 + anxn-2 + … + a0 | < Mnxn whenever x>x0. We can safely assume that x0 >2, because if it is
2
not so, we can simply add 2 to it to get a new x0 , which is at least 2.
Now, |anxn + an-1xn-1 + an-2xn-2 + … + a0| < Mnxn implies |an+1xn+1 + anxn + an-1xn-1 + an-2xn-2
+ … + a0| ≤ |an+1xn+1| + |anxn + an-1xn-1 + an-2xn-2 + … + a0| < |an+1xn+1| + Mnxn.
This means |an+1xn+1| + Mnxn > |anxn + an-1xn-1 + an-2xn-2 + … + a0|.
If we take Mn+1= |an+1| + Mn, we can see that Mn+1 xn+1 = |an+1| xn+1 + Mn xn+1 =|an+1
xn+1| + Mn xn+1> |an+1 xn+1| + Mn xn > |an+1 xn+1 + anxn + an-1xn-1 + an-2xn-2 + … + a0|.
That is to say, |an+1 xn+1 + an-1xn-1 + an-2xn-2 + … + a0 |< Mn+1 xn+1 for all x > x0, that is, an+1
xn+1 + anxn + an-1xn-1 + an-2xn-2 + … + a0 = O(xn+1).
Now, we have it true for n=0, that is, a0 = O(1). This means, by our last conclusion,
a1x + a0 = O(x). This means, by the same logic, a2 x2 + a1x + a0 = O(x2), and so
on. We can easily see that this means it is true for all polynomials of positive
integral degrees.
[7]
Why Bother? – Basic
Asymptotic upper bound of an algorithm
Okay, so we figured out a way to sort of abstractly specify an upper bound on
a function that has one argument. When we talk about the running time of a
program, this argument has to contain information about the input. For example,
in our algorithm, we can say, the execution time equals O(power). This scheme of
specifying the input directly will work perfectly fine for all programs or algorithms
solving the same problem because the input will be the same for all of them.
However, we might want to use the same technique to measure the complexity of
the problem itself: it is the complexity of the most efficient program or algorithm that
can solve the problem. If we try to compare the complexity of different problems,
though, we will hit a wall because different problems will have different inputs.
We must specify the running time in terms of something that is common among
all problems, and that something is the size of the input in bits or bytes. How
many bits do we need to express the argument, power, when it's sufficiently large?
Approximately log2 (power). So, in specifying the running time, our function needs
to have an input that is of the size log2 (power) or lg (power). We have seen that the
running time of our algorithm is proportional to the power, that is, constant times
power, which is constant times 2 lg(power) = O(2x),where x= lg(power), which is the
the size of the input.
Asymptotic lower bound of a function
Sometimes, we don't want to praise an algorithm, we want to shun it; for example,
when the algorithm is written by someone we don't like or when some algorithm
is really poorly performing. When we want to shun it for its horrible performance,
we may want to talk about how badly it performs even for the best input. An a
symptotic lower bound can be defined just like how greater-than-or-equal-to can be
defined in terms of less-than-or-equal-to.
A function f(x) = Ω(g(x)) if and only if g(x) = O(f(x)). The following list shows a
few examples:
•
Since x3 = O(x3), x3 = Ω(x3)
•
Since x3 = O(5x3), 5x3 = Ω(x3)
•
Since x3 = O(5x3 - 25x2 + 1), 5x3 - 25x2 + 1 = Ω(x3)
•
Since x3 = O(x4), x4 = O(x3)
Again, for those of you who are interested, we say the expression f(x) = Ω(g(x))
means there exist positive constants M and x0, such that |f(x)| > M|g(x)| whenever
x > x0, which is the same as saying |g(x)| < (1/M)|f(x)| whenever x > x0 , that is, g(x)
= O(f(x)).
[8]
Chapter 1
The preceding definition was introduced by Donald Knuth, which was a stronger
and more practical definition to be used in computer science. Earlier, there was a
different definition of the lower bound Ω that is more complicated to understand and
covers a few more edge cases. We will not talk about edge cases here.
While talking about how horrible an algorithm is, we can use an asymptotic lower
bound of the best case to really make our point. However, even a criticism of the
worst case of an algorithm is quite a valid argument. We can use an asymptotic
lower bound of the worst case too for this purpose, when we don't want to find out
an asymptotic tight bound. In general, the asymptotic lower bound can be used to
show a minimum rate of growth of a function when the input is large enough
in size.
Asymptotic tight bound of a function
There is another kind of bound that sort of means equality in terms of asymptotic
complexity. A theta bound is specified as f(x) = Ͽ(g(x)) if and only if f(x) = O(g(x)) and
f(x) = Ω(g(x)). Let's see some examples to understand this even better:
•
Since 5x3=O(x3) and also 5x3=Ω(x3), we have 5x3=Ͽ(x3)
•
Since 5x3 + 4x2=O(x3) and 5x3 + 4x2=Ω(x3), we have 5x3 + 4x2=O(x3)
•
However, even though 5x3 + 4x2 =O(x4), since it is not Ω(x4), it is also
not Ͽ(x4)
•
Similarly, 5x3 + 4x2 is not Ͽ(x2) because it is not O(x2)
In short, you can ignore constant multipliers and lower order terms while
determining the tight bound, but you cannot choose a function which grows either
faster or slower than the given function. The best way to check whether the bound is
right is to check the O and the condition separately, and say it has a theta bound only
if they are the same.
Note that since the complexity of an algorithm depends on the particular input, in
general, the tight bound is used when the complexity remains unchanged by the
nature of the input.
[9]
Why Bother? – Basic
In some cases, we try to find the average case complexity, especially when the upper
bound really happens only in the case of an extremely pathological input. But since
the average must be taken in accordance with the probability distribution of the
input, it is not just dependent on the algorithm itself. The bounds themselves are just
bounds for particular functions and not for algorithms. However, the total running
time of an algorithm can be expressed as a grand function that changes it's formula
as per the input, and that function may have different upper and lower bounds.
There is no sense in talking about an asymptotic average bound because, as we
discussed, the average case is not just dependent on the algorithm itself, but also on
the probability distribution of the input. The average case is thus stated as a function
that would be a probabilistic average running time for all inputs, and, in general, the
asymptotic upper bound of that average function is reported.
Optimization of our algorithm
Before we dive into actually optimizing algorithms, we need to first correct our
algorithm for large powers. We will use some tricks to do so, as described below.
Fixing the problem with large powers
Equipped with all the toolboxes of asymptotic analysis, we will start optimizing our
algorithm. However, since we have already seen that our program does not work
properly for even moderately large values of power, let's first fix that. There are two
ways of fixing this; one is to actually give the amount of space it requires to store all
the intermediate products, and the other is to do a trick to limit all the intermediate
steps to be within the range of values that the long datatype can support. We will
use binomial theorem to do this part.
As a reminder, binomial theorem says (x+y)n = xn + nC1xn-1y + nC2xn-2y2 + nC3xn-3y3 +
n
C4xn-4y4 + … nCn-1x1yn-1 + yn for positive integral values of n. The important point here
is that all the coefficients are integers. Suppose, r is the remainder when we divide a
by b. This makes a = kb + r true for some positive integer k. This means r = a-kb, and rn
= (a-kb)n.
If we expand this using binomial theorem, we have rn = an - nC1 an-1.kb + nC2an-2.(kb)2 n
C3an-3.(kb)3 + nC4an-4.(kb)4 + … nCn-1a1.(kb)n-1 ± (kb)n.
Note that apart from the first term, all other terms have b as a factor. Which means
that we can write rn = an + bM for some integer M. If we divide both sides by b now
and take the remainder, we have rn % b = an % b, where % is the Java operator for
finding the remainder.
[ 10 ]
Chapter 1
The idea now would be to take the remainder by the divisor every time we raise the
power. This way, we will never have to store more than the range of the remainder:
public static long computeRemainderCorrected(long base, long
power, long divisor){
long baseRaisedToPower = 1;
for(long i=1;i<=power;i++){
baseRaisedToPower *= base;
baseRaisedToPower %= divisor;
}
return baseRaisedToPower;
}
This program obviously does not change the time complexity of the program; it
just fixes the problem with large powers. The program also maintains a constant
space complexity.
Improving time complexity
The current running time complexity is O(2x), where x is the size of the input as we
have already computed. Can we do better than this? Let's see.
What we need to compute is (basepower) % divisor. This is, of course, the same as
(base2)power/2 % divisor. If we have an even power, we have reduced the number of
operations by half. If we can keep doing this, we can raise the power of base by 2n in
just n steps, which means our loop only has to run lg(power) times, and hence, the
complexity is O(lg(2x)) = O(x), where x is the number of bits to store power. This is a
substantial reduction in the number of steps to compute the value for large powers.
However, there is a catch. What happens if the power is not divisible by 2? Well, then
we can write (basepower)% divisor = (base ((basepower-1))%divisor = (base ((base2)power-1)%divisor,
and power-1 is, of course, even and the computation can proceed. We will write up this
code in a program. The idea is to start from the most significant bit and move towards
less and less significant bits. If a bit with 1 has n bits after it, it represents multiplying
the result by the base and then squaring n times after this bit. We accumulate this
squaring by squaring for the subsequent steps. If we find a zero, we keep squaring for
the sake of accumulating squaring for the earlier bits:
public static long computeRemainderUsingEBS(long base, long power,
long divisor){
long baseRaisedToPower = 1;
long powerBitsReversed = 0;
int numBits=0;
[ 11 ]
Why Bother? – Basic
First reverse the bits of our power so that it is easier to access them from the least
important side, which is more easily accessible. We also count the number of bits
for later use:
while(power>0){
powerBitsReversed <<= 1;
powerBitsReversed += power & 1;
power >>>= 1;
numBits++;
}
Now we extract one bit at a time. Since we have already reversed the order of bit,
the first one we get is the most significant one. Just to get an intuition on the order,
the first bit we collect will eventually be squared the maximum number of times and
hence will act like the most significant bit:
while (numBits-->0){
if(powerBitsReversed%2==1){
baseRaisedToPower *= baseRaisedToPower * base;
}else{
baseRaisedToPower *= baseRaisedToPower;
}
baseRaisedToPower %= divisor;
powerBitsReversed>>>=1;
}
return baseRaisedToPower;
}
We test the performance of the algorithm; we compare the time taken for the same
computation with the earlier and final algorithms with the following code:
public static void main(String [] args){
System.out.println(computeRemainderUsingEBS(13, 10_000_000, 7));
long startTime = System.currentTimeMillis();
for(int i=0;i<1000;i++){
computeRemainderCorrected(13, 10_000_000, 7);
}
long endTime = System.currentTimeMillis();
System.out.println(endTime - startTime);
startTime = System.currentTimeMillis();
for(int i=0;i<1000;i++){
computeRemainderUsingEBS(13, 10_000_000, 7);
}
endTime = System.currentTimeMillis();
System.out.println(endTime - startTime);
}
[ 12 ]
Chapter 1
The first algorithm takes 130,190 milliseconds to complete all 1,000 times execution
on my computer and the second one takes just 2 milliseconds to do the same. This
clearly shows the tremendous gain in performance for a large power like 10 million.
The algorithm for squaring the term repeatedly to achieve exponentiation like we did
is called... well, exponentiation by squaring. This example should be able to motivate
you to study algorithms for the sheer obvious advantage it can give in improving the
performance of computer programs.
Summary
In this chapter, you saw how we can think about measuring the running time of
and the memory required by an algorithm in seconds and bytes, respectively. Since
this depends on the particular implementation, the programming platform, and
the hardware, we need a notion of talking about running time in an abstract way.
Asymptotic complexity is a measure of the growth of a function when the input is
very large. We can use it to abstract our discussion on running time. This is not to say
that a programmer should not spend any time to make a run a program twice as fast,
but that comes only after the program is already running at the minimum asymptotic
complexity.
We also saw that the asymptotic complexity is not just a property of the problem
at hand that we are trying to solve, but also a property of the particular way we
are solving it, that is, the particular algorithm we are using. We also saw that two
programs solving the same problem while running different algorithms with
different asymptotic complexities can perform vastly differently for large inputs.
This should be enough motivation to study algorithms explicitly.
In the following chapters, we will study the most used algorithmic tricks and
concepts required in daily use. We will start from the very easy ones that are also
the building blocks for the more advanced techniques. This book is, of course, by no
means comprehensive; the objective is to provide enough background to make you
comfortable with the basic concepts and then you can read on.
[ 13 ]
Cogs and Pulleys – Building
Blocks
We discussed algorithms in the previous chapter, but the title of the book also
includes the term "data structure." So what is a data structure? A data structure is
an organization of data in memory that is generally optimized so it can be used by
a particular algorithm. We have seen that an algorithm is a list of steps that leads to
a desired outcome. In the case of a program, there is always some input and output.
Both input and output contain data and hence must be organized in some way or
another. Therefore, the input and output of an algorithm are data structures. In fact,
all the intermediate states that an algorithm has to go through must also be stored in
some form of a data structure. Data structures don't have any use without algorithms
to manipulate them, and algorithms cannot work without data structures. It's
because this is how they get input and emit output or store their intermediate states.
There are a lot of ways in which data can be organized. Simpler data structures are
also different types of variables. For example, int is a data structure that stores one
4-byte integer value. We can even have classes that store a set of specific types of
values. However, we also need to think about how to store a collection of a large
number of the same type of values. In this book, we will spend the rest of the time
discussing a collection of values of the same type because how we store a collection
determines which algorithm can work on them. Some of the most common ways
of storing a collection of values have their own names; we will discuss them in this
chapter. They are as follows:
•
Arrays
•
Linked lists
•
Doubly linked lists
•
Circular linked lists
[ 15 ]
Cogs and Pulleys – Building Blocks
These are the basic building blocks that we will use to build more complex data
structures. Even if we don't use them directly, we will use their concepts.
Arrays
If you are a Java programmer, you must have worked with arrays. Arrays are the
basic storage mechanisms available for a sequence of data. The best thing about
arrays is that the elements of an array are collocated sequentially and can be accessed
completely and randomly with single instructions.
The traversal of an array element by an element is very simple. Since any element
can be accessed randomly, you just keep incrementing an index and keep accessing
the element at this index. The following code shows both traversal and random
access in an array:
public static void printAllElements(int[] anIntArray){
for(int i=0;i=targetIndex;i--){
array[i+1]=array[i];
}
array[targetIndex]=value;
}
}
[ 17 ]
Cogs and Pulleys – Building Blocks
What would be the running time complexity of the preceding algorithm? For all our
cases, we will only consider the worst case. When does an algorithm perform worst?
To understand this, let's see what the most frequent operation in an algorithm is. It is
of course the shift that happens in the loop. The number of shifts become maximum
when startIndex is at the beginning of the array and targetIndex at the end or
vice versa. This is when all but one element has to be shifted one by one. The running
time in this case must be some constant times the number of elements of the array
plus some other constant to account for the non-repeating operations. So it is T(n) =
K(n-1)+C for some constants K and C, where n is the number of elements in the array
and T(n) is the running time of the algorithm. This can be expressed as follows:
T(n) = K(n-1)+C = Kn + (C-K)
The following steps explain the expression:
1. As per rule 1 of the definition of big O, T(n) = O(Kn + (C-K)).
2. As per rule 3, T(n) = O(Kn).
3. We know |-(C-K)| < |Kn + (C-K)| is true for sufficiently large n. Therefore,
as per rule 3, since T(n) = O(Kn + (C-K)), it means T(n) = O(Kn + (C-K) + (-(CK))), that is, T(n) = O(Kn).
4. And, finally, as per rule 2, T(n) = O(n).
Now since the array is the major input in the algorithm, the size of the input is
represented by n. So we will say, the running time of the algorithm is O(n), where n
is the size of the input.
Insertion of a new element and the process of
appending it
Now we move on to the process of insertion of a new element. Since arrays are fixed
in size, insertion requires us to create a new array and copy all the earlier elements
into it. The following figure explains the idea of an insertion made in a new array:
Figure 2: Insertion of a new element into an array
[ 18 ]
Chapter 2
The following code does exactly that:
public static int [] insertExtraElementAtIndex(int[] array,
int index, int value){
int [] newArray = new int[array.length+1];
First, you copy all the elements before the targeted position as they are in the
original array:
for(int i=0;i implements Iterable, Visualizable {
First, we create a Node class inside the LinkedList class, which will act as a wrapper
for the elements and also hold the reference to the next node:
protected static class Node {
protected E value;
protected Node next;
public String toString(){
return value.toString();
}
}
int length = 0;
Node[] lastModifiedNode;
[ 20 ]
Chapter 2
Then, we must have references for the first and last elements:
Node first;
Node last;
Finally, we create a method called getNewNode() that creates a new empty node. We
will need this if we want to use a different class for a node in any of the subclasses:
protected Node getNewNode() {
Node node = new Node<>();
lastModifiedNode = new Node[]{node};
return node;
}
}
At this point, the unfinished class LinkedList will not be able to store any element;
let's see how to do this, though. Notice that we have implemented the Iterable
interface. This will allow us to loop through all the elements in an advanced for loop.
Appending at the end
Appending at the end is achieved by simply creating a link from the last element
of the original linked list to the new element that is being appended and then
reassigning the reference to the last element. The second step is required because the
new element is the new last element. This is shown in the following figure:
Figure 4: Appending at the end of a linked list
[ 21 ]
Cogs and Pulleys – Building Blocks
There is a small difference when you append an element to a linked list that is empty
to start with. At this point, the first and last references are null, and this case must be
handled separately. The following figure explains this case:
Figure 5: Appending to an empty linked list
We will achieve this by using the following simple code as is. We return the node
that has just been added. This is helpful to any class that is extending this class. We
will do the same in all cases, and we will see the use of this while discussing doubly
linked lists:
public Node appendLast(E value) {
Node node = getNewNode();
node.value = value;
We try to update the reference of the current last node only if the list is not empty:
if (last != null)
last.next = node;
Then, we must update the last reference as the new element is not going to be the
last element:
last = node;
Finally, if the list is empty, the new element must also be the first new element and
we must update the first reference accordingly, as shown in the preceding figure:
if (first == null) {
first = node;
}
length++;
return node;
}
[ 22 ]
Chapter 2
Notice that we also keep track of the current length of the list. This is not essential,
but if we do this, we do not have to traverse the entire list just to count how many
elements are in the list.
Now, of course, there is this important question: what is the time complexity of
appending to a linked list? Well, if we do it the way we have done it before—that is,
by having a special reference to the last element—we don't need any loop, as we can
see in the code. If the program does not have any loops, all operations would be onetime operations, hence everything is completed in constant time. You can verify that
a constant function has this complexity: O(1). Compare this with what was appended
at the end of an array. It required the creation of a new array and also had O(n)
complexity, where n was the size of the array.
Insertion at the beginning
Inserting an element at the beginning of a list is very similar to appending it at the
end. The only difference is that you need to update the first reference instead of the
last reference:
public Node appendFirst(E value) {
Node node = getNewNode();
node.value = value;
node.next = first;
first = node;
if (length == 0)
last = node;
length++;
return node;
}
[ 23 ]
Cogs and Pulleys – Building Blocks
Insertion at an arbitrary position
Insertion at an arbitrary position can be achieved in the same way we perform an
insertion in the first element, except that we update the reference of the previous
element instead of the first reference. There is, however, a catch; we need to find the
position where we need to insert the element. There is no way to find it other than
to start at the beginning and walk all the way to the correct position while counting
each node we step on.
Figure 6: Insertion of an arbitrary element into a linked list
We can implement the idea as follows:
public Node insert(int index, E value) {
Node node = getNewNode();
First, we take care of the special cases:
if (index < 0 || index > length) {
throw new IllegalArgumentException("Invalid
index for insertion");
} else if (index == length) {
return appendLast(value);
} else if (index == 0) {
return appendFirst(value);
} else {
As mentioned earlier, we walk all the way to the desired position while counting the
nodes, or in this case, counting the index in the opposite direction:
Node result = first;
while (index > 1) {
index--;
result = result.next;
}
[ 24 ]
Chapter 2
Finally, we update the references:
node.value = value;
node.next = result.next;
result.next = node;
length++;
return node;
}
}
What is the complexity of this algorithm? There is a loop that must run as many
times as the index. This algorithm seems to have a running time that is dependent
on the value of the input and not just its size. In this case, we are only interested in
the worst case. What is the worst case then? It is when we need to step on all the
elements of the list, that is, when we have to insert the element at the end of the list,
except for the last element. In this case, we must step on n-1 elements to get there
and do some constant work. The number of steps would then be T(n) = C(n-1)+K for
some constants C and K. So, T(n) = O(n).
Looking up an arbitrary element
Finding the value of an arbitrary element has two different cases. For the first and
last element, it is simple. Since we have direct references to the first and last element,
we just have to traverse that reference and read the value inside it. I leave this for
you to see how it could be done.
However, how do you read an arbitrary element? Since we only have forward
references, we must start from the beginning and walk all the way, traversing
references while counting steps until we reach the element we want.
Let's see how we can do this:
public E findAtIndex(int index) {
We start from the first element:
Node result = first;
while (index >= 0) {
if (result == null) {
throw new NoSuchElementException();
} else if (index == 0) {
[ 25 ]
Cogs and Pulleys – Building Blocks
When the index is 0, we would have finally reached the desired position, so
we return:
return result.value;
} else {
If we are not there yet, we must step onto the next element and keep counting:
index--;
result = result.next;
}
}
return null;
}
Here too, we have a loop inside that has to run an index a number of times. The
worst case is when you just need to remove one element but it is not the last one;
the last one can be found directly. It is easy to see that just like you insert into an
arbitrary position, this algorithm also has running time complexity of O(n).
Figure 7: Removing an element in the beginning
Removing an element in the beginning means simply updating the reference to the
first element with that of the next element. Note that we do not update the reference
in the element that has just been removed because the element, along with the
reference, would be garbage-collected anyway:
public Node removeFirst() {
if (length == 0) {
throw new NoSuchElementException();
}
[ 26 ]
Chapter 2
Assign the reference to the next element:
Node origFirst = first;
first = first.next;
length--;
If there are no more elements left, we must also update the last reference:
if (length == 0) {
last = null;
}
return origFirst;
}
Removing an arbitrary element
Removing an arbitrary element is very similar to removing an element from the
beginning, except that you update the reference held by the previous element instead
of the special reference named first. The following figure shows this:
Figure 8: Removing an arbitrary element
Notice that only the link in the linked list is to be reassigned to the next element. The
following code does what is shown in the preceding figure:
protected Node removeAtIndex(int index) {
if (index >= length || index < 0) {
throw new NoSuchElementException();
}
[ 27 ]
Cogs and Pulleys – Building Blocks
Of course, removing the first element is a special case:
if (index == 0) {
Node nodeRemoved = first;
removeFirst();
return nodeRemoved;
}
First, find out the element just before the one that needs to be removed because this
element would need its reference updated:
Node justBeforeIt = first;
while (--index > 0) {
justBeforeIt = justBeforeIt.next;
}
Update the last reference if the last element is the one that is being removed:
Node nodeRemoved = justBeforeIt.next;
if (justBeforeIt.next == last) {
last = justBeforeIt.next.next;
}
Update the reference held by the previous element:
justBeforeIt.next = justBeforeIt.next.next;
length--;
return nodeRemoved;
}
It is very easy to see that the running time worst case complexity of this algorithm is
O(n)—which is similar to finding an arbitrary element—because this is what needs
to be done before removing it. The operation of the actual removal process itself
requires only a constant number of steps.
Iteration
Since we are working in Java, we prefer to implement the Iterable interface. It lets
us loop through the list in a simplified for loop syntax. For this purpose, we first
have to create an iterator that will let us fetch the elements one by one:
protected class ListIterator implements Iterator {
protected Node nextNode = first;
@Override
[ 28 ]
Chapter 2
public boolean hasNext() {
return nextNode != null;
}
@Override
public E next() {
if (!hasNext()) {
throw new IllegalStateException();
}
Node nodeToReturn = nextNode;
nextNode = nextNode.next;
return nodeToReturn.value;
}
}
The code is self-explanatory. Every time it is invoked, we move to the next element
and return the current element's value. Now we implement the iterator method of
the Iterable interface to make our list an iterable:
@Override
public Iterator iterator() {
return new ListIterator();
}
This enables us to use the following code:
for(Integer x:linkedList){
System.out.println(x);
}
The preceding code assumes that the variable linkedList was
LinkedList. Any list that extends this class will also get this
property automatically.
[ 29 ]
Cogs and Pulleys – Building Blocks
Doubly linked list
Did you notice that there is no quick way to remove the element from the end of a
linked list? This is because even if there is a quick way to find the last element, there
is no quick way to find the element before it whose reference needs to be updated.
We must walk all the way from the beginning to find the previous element. Well
then, why not just have another reference to store the location of the last but one
element? This is because after you remove the element, how would you update the
reference otherwise? There would be no reference to the element right before that.
What it looks like is that to achieve this, we have to store the reference of all the
previous elements up to the beginning. The best way to do this would be to store the
reference of the previous element in each of the elements or nodes along with the
reference to the next element. Such a linked list is called a doubly linked list since
the elements are linked both ways:
Figure 9: Doubly linked list
We will implement a doubly linked list by extending our original linked list because
a lot of the operations would be similar. We can create the barebones class in the
following manner:
public class DoublyLinkedList extends LinkedList {
We create a new Node class extending the original one and adding a reference for the
previous node:
protected static class DoublyLinkedNode extends Node {
protected DoublyLinkedNode prev;
}
Of course, we need to override the getNode() method to use this node:
@Override
protected Node getNewNode() {
return new DoublyLinkedNode();
}
}
[ 30 ]
Chapter 2
Insertion at the beginning or at the end
Insertion at the beginning is very similar to that of a singly linked list, except that
we must now update the next node's reference for its previous node. The node being
inserted does not have a previous node in this case, so nothing needs to be done:
public Node appendFirst(E value) {
Node node = super.appendFirst(value);
if (first.next != null)
((DoublyLinkedNode) first.next).prev =
(DoublyLinkedNode) first;
return node;
}
Pictorially, it can be visualized as shown in the following figure:
Figure 10: Insertion at the beginning of a doubly linked list
Appending at the end is very similar and is given as follows:
public Node appendLast(E value) {
DoublyLinkedNode origLast = (DoublyLinkedNode)
this.last;
Node node = super.appendLast(value);
If the original list were empty, the original last reference would be null:
if (origLast == null) {
origLast = (DoublyLinkedNode) first;
}
((DoublyLinkedNode) this.last).prev = origLast;
return node;
}
[ 31 ]
Cogs and Pulleys – Building Blocks
The complexity of the insertion is the same as that of a singly linked list. In fact, all
the operations on a doubly linked list have the same running time complexity as that
of a singly linked list, except the process of removing the last element. We will thus
refrain from stating it again until we discuss the removal of the last element. You
should verify that the complexity stays the same as with a singly linked list in all
other cases.
Insertion at an arbitrary location
As with everything else, this operation is very similar to the process of making
an insertion at an arbitrary location of a singly linked list, except that you need to
update the references for the previous node.
Figure 11: Insertion at an arbitrary location of a doubly linked list
The following code does this for us:
public Node insert(int index, E value) {
DoublyLinkedNode inserted = (DoublyLinkedNode)
super.insert(index, value);
[ 32 ]
Chapter 2
In the case of the first and last element, our overridden methods are invoked
anyway. Therefore, there is no need to consider them again:
if(index!=0 && index!=length) {
if (inserted.next != null) {
This part needs a little bit of explaining. In Figure 11, the node being inserted is 13.
Its previous node should be 4, which was originally the previous node of the next
node 3:
inserted.prev = ((DoublyLinkedNode)
inserted.next).prev;
The prev reference of the next node 3 must now hold the newly inserted node 13:
((DoublyLinkedNode) inserted.next).prev = inserted;
}
}
return inserted;
}
Removing the first element
Removing the first element is almost the same as that for a singly linked list. The
only additional step is to set the prev reference of the next node to null. The
following code does this:
public Node removeFirst() {
super.removeFirst();
if (first != null) {
((DoublyLinkedNode) first).prev = null;
}
return first;
}
[ 33 ]
Cogs and Pulleys – Building Blocks
The following figure shows what happens. Also, note that finding an element does
not really need an update:
Figure 12: Removal of the first element from a doubly linked list
There can be an optimization to traverse backward from the last element to the first
in case the index we are looking for is closer toward the end; however, it does not
change the asymptotic complexity of the find operation. So we leave it at this stage. If
interested, you would be able to easily figure out how to do this optimization.
Removing an arbitrary element
Just like other operations, removal is very similar to removal of elements in the case
of a singly linked list, except that we need to update the prev reference:
[ 34 ]
Chapter 2
Figure 13: Removal of an arbitrary element from a doubly linked list
The following code will help us achieve this:
public Node removeAtIndex(int index) {
if(index<0||index>=length){
throw new NoSuchElementException();
}
This is a special case that needs extra attention. A doubly linked list really shines
while removing the last element. We will discuss the removeLast() method in the
next section:
if(index==length-1){
return removeLast();
}
[ 35 ]
Cogs and Pulleys – Building Blocks
The rest of the code is fairly easy to figure out:
DoublyLinkedNode nodeRemoved
= (DoublyLinkedNode) super.removeAtIndex(index);
if ((DoublyLinkedNode) nodeRemoved.next != null)
((DoublyLinkedNode) nodeRemoved.next).prev
= nodeRemoved.prev;
return nodeRemoved;
}
Removal of the last element
This is where a doubly linked list really shines. This is the reason we got started with
a doubly linked list. And it's not even a lot of code. Check this out:
public Node removeLast() {
Node origLast = last;
if(last==null){
throw new IllegalStateException
("Removing element from an empty list");
}
Just use the fact that we have access to the previous node's reference and we can
update the last reference very easily:
last = ((DoublyLinkedNode)last).prev;
If the list is not empty after removal, set the next reference of the new last element to
null. If the new list is empty instead, update the first element as well:
if(last!=null){
last.next = null;
} else{
first = null;
}
Don't forget to update the length:
length--;
return origLast;
}
[ 36 ]
Chapter 2
We don't need a new figure to understand the update of the references as they are
really similar to the removal process of the first element. The only difference from the
singly linked list is that in the case of a singly linked list, we need to walk all the way
to the end of the list to find the previous element of the list. However, in the case of a
doubly linked list, we can update it in one step because we always have access to the
previous node's reference. This drastically reduces the running time from O(n) in the
case of a singly linked list to O(1) in the case of a doubly linked list.
Circular linked list
A circular linked list is an ordinary linked list, except that the last element holds the
reference to the first element as its next element. This, of course, justifies its name. It
would be useful when, for example, you are holding a list of players in a list and they
play in turn in a round robin fashion. The implementation is simplified if you use a
circular linked list and just keep rotating as the players complete their turn:
Figure 14: A circular linked list
[ 37 ]
Cogs and Pulleys – Building Blocks
The basic structure of a circular linked list is the same as that of a simple linked list;
no more fields or methods are required:
public class CircularLinkedList extends LinkedList{
}
Insertion
This is the same as the insertion for a simple linked list, except that you assign the
last references next to the first:
@Override
public Node appendFirst(E value) {
Node newNode = super.appendFirst(value);
last.next = first;
return newNode;
}
From this, it is not hard to guess how it would be to append at the end:
@Override
public Node appendLast(E value) {
Node newNode = super.appendLast(value);
last.next = first;
return newNode;
}
Insertion at any other index, of course, remains the same as that for a simple linked
list; no more changes are required. This means the complexity of the insertion stays
the same as with that for a simple linked list.
Removal
Removal also only changes when you remove the first or the last element. In any
case, just updating the last element's next reference solves the purpose. The only
place where we need to change this is when we remove the first element. This is
because the same operation we used for a simple linked list does not update the
previous element's next reference, which we need to do:
@Override
public Node removeFirst() {
Node newNode = super.removeFirst();
last.next = first;
return newNode;
}
Nothing else needs to be done in removal.
[ 38 ]
Chapter 2
Rotation
What we are doing here is just bringing the next element of the first element to the
first position. This is exactly what the name "rotation" would imply:
public void rotate(){
last = first;
first = first.next;
}
Figure 15: Rotation of a circular linked list
[ 39 ]
Cogs and Pulleys – Building Blocks
Doing the same with a simple linked list would require no more than assigning one
more reference. You should be able to figure out how to do this with a simple linked
list. But this operation looks more natural for a circular linked list, as conceptually,
there is no first element.
The real power of a circular linked list is the iterator, which never ends. If the list is
non-empty, the iterator will have hasNext(), which always returns true. This means
you can simply keep calling the next() method on the iterator and keep processing
the elements in a round robin fashion. The following code should make it clear what
I mean:
for(int i=0;i<30;i++){
System.out.print(" "+ linkedList.first);
linkedList.rotate();
}
Note that if you try to use the enhanced for loop with a circular
linked list, you will run into an infinite loop.
Summary
We covered a few basic data structures and the algorithms for manipulating them.
In addition to this, we also found out their running time complexities. To summarize
this, an array provides you with the fastest random access there is with this time
complexity: O(1). But arrays cannot change size; the only modification they allow is
to change the value of an element. A linked list allows fast append at the end and
insertion at the beginning at O(1) time. However, O(1) removal is only available for
removing the first element. This is resolved by a doubly linked list that also allows
O(1) removal from the end. A circular linked list holds a reference to the first element
in the next reference of the last element. This makes the list a circular structure that
allows one to loop indefinitely.
In the upcoming chapters, we will discuss the abstraction of data structures called
abstract data types. We will use the data structures we have seen in this chapter to
implement the abstract data types, which in turn will be used in later chapters.
[ 40 ]
Protocols – Abstract
Data Types
In the last chapter, we saw a few basic data structures and some algorithms to
manipulate them. However, sometimes we may want to hide the implementation
details of a data structure and only want to know how they interact with other
algorithms. We may want to specify a few operations that they must allow and forget
about how they are achieved. This is not very different from abstraction of a part of a
program in any large software application. For example, in Java, we create interfaces
that only define the methods of an object that its class must implement, and then
we use this interface type, being confident that they will be implemented properly.
We do not want to think about how an implementation class would provide their
implementation. Such interfaces of data structure are called abstract data types. To
put this another way, an abstract data type (ADT) is a description of what a data
structure should do for its user. It is a list of operations that any implementation
must support and the complete description of what these operations are supposed to
do. A few of these have very frequent usage and have names given to them. We will
discuss a few of these here.
In this chapter, you will learn about the following concepts:
•
The definition of some common ADTs and their operations
•
How to implement these ADTs using both simple arrays and the data
structures you learned in the last chapter
[ 41 ]
Protocols – Abstract Data Types
Stack
A stack is a very commonly used ADT. It is so named because it resembles a stack
of plates used in a restaurant. In such a stack, a plate that has been washed and put
last would stay on top. This would be the first plate to be picked up when a plate is
needed. The plate that went in first would be at the bottom of the stack and would be
picked last. So, the last plate to be placed in the stack is the first plate to get out, we
can also call this last in first out (LIFO).
Similarly, a stack ADT has a protocol where the last value that is put in it must be
returned on the first attempt to get a value out, and the value that went in first must
come out last. The following figure will make it more clear:
The operation of putting a new value in a stack is called push, and the operation of
retrieving a value from a stack is called pop. The element that was pushed last must
be popped first. The operation that allows one to see what the next pop will return is
called peek. The peek operation returns the top element without modifying the stack.
We expect all stack implementations to have all operations implemented in the time
complexity of O(1). This is also part of our stack protocol.
The stack ADT has the following operations:
•
Push: This adds an element at the top of the stack
•
Pop: This removes the element at the top of the stack
•
Peek: This checks the next value to be popped
[ 42 ]
Chapter 3
Since we know that ADTs are to data structures what interfaces are to classes, we
will code an ADT as an interface. The following is our interface for a stack:
public interface Stack {
void push(E value);
E pop();
E peek();
}
Of course, we will not leave it at this. We will see how a stack can actually be
implemented. To this end, we will see both a fixed-sized stack using an array to store
it's data, and a growing stack using a linked list for storing data. We will start with
the first.
Fixed-sized stack using an array
A fixed-sized stack uses a pre-allocated array to store values, that is when this stack
has used up the entire array, it can no longer accept new values until the old ones
are popped. This is not very different from an actual stack of plates, which most
certainly has a maximum height that it can handle.
As always, we start with the basic structure of the class, as follows:
public class StackImplArray implements Stack {
We need an array to store the elements, and we need to remember where the top of
the stack is in that array. The top always marks the index of the element that will be
popped next. When there are no more elements to be popped, it is set to -1. Why -1?
Because this is the natural choice as it does not require any special handling when
the first element is inserted:
protected E[] array;
int top=-1;
public StackImplArray(int size){
array = (E[])new Object[size];
}
}
The push operation in a stack can be to simply put the value in the array right next
to the current top and then set the top to the new position, as illustrated in the
following code:
@Override
public void push(E value) {
[ 43 ]
Protocols – Abstract Data Types
We first check whether the stack is already full or the current top is equal to the
maximum index possible, like this:
if(top == array.length-1){
throw new NoSpaceException("No more space in stack");
}
Now, we set the top to the new position and put the value we need to store in there
as follows:
top++;
array[top] = value;
}
The exception we used is a custom exception for this purpose. The code of the
exception is simple as shown in the following code:
public class NoSpaceException extends RuntimeException{
public NoSpaceException(String message) {
super(message);
}
}
The pop operation is just the opposite. We need to first take the value of the current
top and then update the top to the new position, which is one less than the current
position, as shown in the following code:
@Override
public E pop() {
We first check whether the stack is already empty, in which case we return a special
value, null. This is shown in the following code:
if(top==-1){
return null;
}
Then we update the top and return the value at the current top as follows:
top--;
return array[top+1];
}
[ 44 ]
Chapter 3
The peek operation does not change the state of the stack, and hence is even simpler:
@Override
public E peek() {
Just like the pop operation, we return null if the stack is empty:
if(top==-1){
return null;
}
Otherwise, we return the top element, as follows:
return array[top];
}
It is in fact possible to have a stack without an upper limit backed up by an array.
What we really need to do is that whenever we run out of space, we can resize the
array. Array actually cannot be resized, so the operation would be to create a new
array with a higher size (maybe twice as much as the original size), and copy all the
old elements into this array. Since this involves copying all the n elements to the new
array one by one, the complexity of this operation is O(n).
Variable-sized stack using a linked list
The problem with an array-based implementation is that since arrays are fixed in size,
the stacks cannot grow beyond a fixed-size. To resolve this, we have to do what we did
to fix the same problem for an array, that is, use a linked list instead. We start such an
implementation with the following bare bone class. The linked list will store the values.
Instead of assigning a new linked list to it, we do so using an overridable method
getNewLinkedList(). This will be useful in the class that extends from this one:
public class StackImplLinkedList implements Stack {
protected LinkedList list = getNewLinkedList();
protected LinkedList getNewLinkedList(){
return new LinkedList<>();
}
}
[ 45 ]
Protocols – Abstract Data Types
To see which end of the linked list must be used as the top of the stack, we need
to remember that our stack protocol expects the operations to be O(1), so we must
choose an end that allows both insertion and removal in O(1) time. That end is of
course the front of the list as we saw in the last chapter. This makes the following
code for the push operation self-explanatory:
@Override
public void push(E value) {
list.appendFirst(value);
}
Note that this time, we did not check whether the stack is full because this
implementation of the stack is never full, it grows as it needs and the underlying
linked list takes care of that.
The pop operation, however, does need to check whether the stack is empty and
return null at that point. The following code for the pop operation is also quite
self-explanatory:
@Override
public E pop() {
if(list.getLength()==0){
return null;
}
E value = list.getFirst();
list.removeFirst();
return value;
}
The peek operation is, of course, the same, except it does not remove the top element:
@Override
public E peek() {
if(list.getLength()==0){
return null;
}
return list.getFirst();
}
This concludes our linked list-based implementation of a stack. In the next section,
we will check out another ADT called a queue.
[ 46 ]
Chapter 3
Queue
What is the opposite of a stack? This may be a weird question. However, a stack follows
LIFO, last in first out. The opposite of that is first-in-first-out (FIFO). So, in some sense,
a FIFO ADT can be considered as the opposite of a stack. This is not very different from
a queue of people waiting for a bus or at a doctor's clinic. The first person to show up
gets the first chance to get onto the bus or to get to see the doctor. The second person
gets the second chance. No wonder, such an abstract data type is called a queue.
Appending to the end of a queue is called enqueuing and removing from it is called
dequeuing. The contract is, of course, that the first value that is enqueued would be the
first to be dequeued. The following figure illustrates this operation:
The queue ADT has the following operations:
•
Enqueue: This adds an element at the back of the queue
•
Dequeue: This removes an element from the front of the queue
•
Peek: This checks the element that would be dequeued next
The queue will be represented by the following interface:
public interface Queue {
void enqueue(E value);
E dequeue();
E peek();
}
[ 47 ]
Protocols – Abstract Data Types
Fixed-sized queue using an array
Just like the stack, we have an array-based implementation of a queue. However,
since a queue receives new values and removes old values from opposite sides, the
body of the queue moves as it does. The following figure will illustrate this point:
[ 48 ]
Chapter 3
This means that after a sequence of a few such operations, the end of the queue will
reach the end of the array, and there will be space left at the beginning of the array.
At this point, we don't want to stop receiving new values as there is space left, so we
roll over to the beginning of the array. That is to say, we continue adding the new
values at the beginning of the array.
To do all these manipulations, we must have separate variables storing the indexes
of the beginning and the end of the queue. Also, since due to roll over, sometimes
the end is smaller than the beginning, we store the length separately to avoid
confusion. We start with the bare bone implementation of the class just as before. The
start represents the index of the element that would be dequeued next and the end
represents the position of the next value that would be enqueued. This is illustrated
in the following code:
public class QueueImplArray implements Queue{
protected E[] array;
protected int start=0;
protected int end=0;
protected int length=0;
public QueueImplArray(int size){
array = (E[]) new Object[size];
}
}
The enqueue operation does not change the start position. The new value is put at
the end position of the array and the end is incremented by one. The end, of course,
needs to be rolled over in case it goes beyond the maximum index of the array, as
shown in the following code:
@Override
public void enqueue(E value) {
if(length>=array.length){
throw new NoSpaceException("No more space to add an element");
}
array[end] = value;
The modulo operator will make sure that the index goes to the beginning of the array
when it hits the end of the array, as follows:
end = (end+1) % array.length;
length++;
}
[ 49 ]
Protocols – Abstract Data Types
The dequeue operation does not change the end position. We read from the start
index and then increment the start index with rollover, as follows:
@Override
public E dequeue() {
if(length<=0){
return null;
}
E value = array[start];
start = (start+1) % array.length;
length--;
return value;
}
The peek operation lets us see the element that would be dequeued next, without
removing it. It is, of course, simpler. We just return the next element to be dequeued.
This is shown in the following code:
@Override
public E peek() {
if(length<=0){
return null;
}
return array[start];
}
A queue backed up by an array can be resized in a similar manner as described for
the case of a stack, and this too will be O(n), since we must copy all the old elements
to the newly allocated array one by one.
Variable-sized queue using a linked list
Just like a stack, we want to implement a queue using a linked list. We need to
remember that all operations must be O(1) in running time. If we enqueue by
appending new elements at the beginning of the linked list, we will need to remove
elements from the end of the list during dequeuing. This will not work as removal of
an element from the end of a linked list is O(n). But appending at the end of a linked
list is O(1) and so is removing from the beginning of the list. Hence, the end of the
queue, where new elements are enqueued, would be the end of the list. And the start
of the queue, where the elements are dequeued from, would be the beginning of the
linked list.
[ 50 ]
Chapter 3
Given this, the implementation of a queue using a linked list is straightforward.
Again, we create an instance of the list only using a getNewLinkedList() method,
which can be overridden by a subclass to use a different linked list, as follows:
public class QueueImplLinkedList implements Queue{
protected LinkedList list = getNewLinkedList();
protected LinkedList getNewLinkedList(){
return new LinkedList<>();
}
The enqueue operation simply appends at the end of the list as follows:
@Override
public void enqueue(E value) {
list.appendLast(value);
}
The dequeue operation first checks if the list is empty so it can return null, and then
it simply removes the first element from the list. It must also return the element that
it just removed:
@Override
public E dequeue() {
if(list.getLength()==0){
return null;
}
E value = list.getFirst();
list.removeFirst();
return value;
}
Just like the dequeue operation, the peek operation first needs to check whether the
list is empty, in which case it has to return a null value, otherwise it simply returns
the element at the beginning of the list that would be dequeued on the next dequeue
operation, as shown in the following code:
@Override
public E peek() {
if(list.getLength()==0){
return null;
}
return list.getFirst();
}
}
[ 51 ]
Protocols – Abstract Data Types
Double ended queue
A double ended queue is a combination of a stack and a queue. The idea is that you
are allowed to insert and remove elements at both ends of the queue. If you remove
elements from the side you have inserted, it will behave like a stack. On the other
hand, if you insert and remove on opposite ends, it will behave like a queue. You can
mix these operations and use them in any order you like. The following figure shows
a few operations to clarify this idea:
A double ended queue has the following operations all with a complexity of O(n):
•
Push: This inserts an element at the beginning
•
Pop: This removes an element from the beginning
•
Inject: This inserts an element at the end
•
Eject: This removes an element from the end
•
Peek: This checks the first element
•
PeekLast: This checks the last element
[ 52 ]
Chapter 3
A double ended queue will be represented by the following interface:
public interface DoubleEndedQueue extends Stack {
void inject(E value);
E eject();
E peekLast();
}
Note that since a double ended queue has push and pop operations just like a stack and
it preserves the same meaning, we create this interface extending the Stack interface.
Fixed-length double ended queue using
an array
Since we have created the double ended queue as an extension of a stack, one would
expect its implementation to extend a stack implementation as well. However,
remember that a double ended queue is both a stack and a queue. The array-based
implementation for a queue was more complex than that for a stack due to rollover
of the indexes. We don't want to reprogram those, so we choose to extend a queue
implementation instead of a stack implementation, as shown in the following code:
public class DoubleEndedQueueImplArray extends
QueueImplArray implements DoubleEndedQueue {
We initialize the queue to the fixed length, as follows:
public DoubleEndedQueueImplArray(int size) {
super(size);
}
This is appended at the end of the double ended queue, which is the same as the
enqueue operation of a queue:
@Override
public void inject(E value) {
enqueue(value);
}
The eject operation is the removal of an element from the end of the double ended
queue. We don't have an equivalent operation in a simple queue. So, we must code
for it as follows:
@Override
public E eject() {
if (length <= 0) {
return null;
}
[ 53 ]
Protocols – Abstract Data Types
The end has to decrement by one with a provision for rollover. But if the end is
already at zero, it will become negative, which will not work well with the modulo
operator, because it will return a negative value. To always keep it positive, we add
the length of the array to it. Note that it does not change the remainder when divided
by the length of the array. This is shown in the following code:
end = (end + array.length - 1) % array.length;
E value = array[end];
length--;
return value;
}
The peekLast operation simply needs to return the element that would have been
returned by the eject operation without modifying anything, as shown in the
following code:
@Override
public E peekLast() {
if (length <= 0) {
return null;
}
return array[(end + array.length - 1) % array.length];
}
The push operation is the insertion of an element at the beginning of the double
ended queue. There is no equivalent operation in a simple queue. Hence, we need to
code for it as follows:
@Override
public void push(E value) {
if (length >= array.length) {
throw new NoSpaceException("No more space to add an
element");
}
This operation is very similar to updating the end index eject operation, as shown
in the following code:
start = (start + array.length - 1) % array.length;
array[start] = value;
length++;
}
[ 54 ]
Chapter 3
The pop operation is the removal of the element at the beginning of the queue, which
is the same as the dequeue operation of an ordinary queue. This is illustrated in the
following code:
@Override
public E pop() {
return dequeue();
}
}
Note that we don't write any code for the peek operation, which should return the
element at the beginning of the double ended queue, as it is the same as the peek
operation for a simple queue.
The array-based implementation is, of course, fixed in size and cannot hold more
elements than it's fixed size. Next, we develop a linked list-based implementation.
Variable-sized double ended queue using a
linked list
We had earlier used a simple linked list to implement both a queue and a stack.
However, remember again that all operations must be O(1). Now, we must both
add and remove elements at both ends of the underlying linked list. We know that
removal from the end of a singly linked list is O(n) and we cannot use it. So, we must
use a doubly linked list instead.
This time we do not have to worry about rollovers and so we will extend the linked list
implementation of a stack, which is the natural choice. We will replace its singly linked
list with a doubly linked list by overriding the getLinkedList() method, as follows:
public class DoubleEndedQueueImplLinkedList extends
StackImplLinkedList implements DoubleEndedQueue {
@Override
protected LinkedList getNewLinkedList() {
return new DoublyLinkedList();
}
The inject operation inserts a new element at the end of the list as shown in the
following code:
@Override
public void inject(E value) {
list.appendLast(value);
}
[ 55 ]
Protocols – Abstract Data Types
The eject operation must remove and return the last element of the list. This is
illustrated in the following code:
@Override
public E eject() {
if(list.getLength()==0){
return null;
}
E value = list.getLast();
list.removeLast();
return value;
}
Finally, the peekLast() method will just return the last element of the doubly linked
list as follows:
@Override
public E peekLast() {
if(list.getLength()==0){
return null;
}
return list.getLast();
}
}
We only had to implement the inject(), eject(), and peekLast() methods as the
other methods are already implemented by the stack we extend.
Summary
In this chapter, we saw that an abstract data type or ADT is an abstraction of a data
structure. It is a contract that an underlying data structure is supposed to adhere to.
The contract involves different operations on the data structure and their specific
behavior. We then saw a few simple ADTs as examples. These ADTs are, however,
extremely useful as we will see in the course of this book when we encounter other
algorithms. Abstraction allows different implementations of the structures. We will
also see more ADTs in the course of this book and their implementations.
In the next chapter, we will take a detour into a new area of algorithms called
functional programming. Remember that an algorithm is a sequence of steps that
may be followed to achieve a desired processing; it turns out that there is another
way of looking at it, which we will explore in the next chapter.
[ 56 ]
Detour – Functional
Programming
In the beginning of this book, we saw that an algorithm is a sequence of steps
to achieve a result. This way of solving a problem by following a sequence of
instructions is called imperative programming. Each statement in the program can be
thought of as an imperative sentence asking the computer to do something. However,
this is not the only way of looking at it. Functional programming sees an algorithm as
a composition of components rather than as a sequence of steps. A problem to solve is
seen as a composition of smaller-sized problems. Instead of using a loop, we combine
smaller versions of the same problem. Functional programming uses recursion as a
basic component. A recursion is nothing but solving the same problem for a smaller
size and then composing the result with something else to get the solution for the
given size of the problem. This has a far-reaching implication in how easy it is to read
and understand a program. This makes it very important to study.
There are really two worlds in the programming paradigm. The imperative style
of programming is favored by C-like languages, such as C, C++, and Java. On the
purely functional side, there are languages such as Lisp, Haskell, and Scheme. Apart
from these, some languages try to have the best of both worlds, such as Python or
Scala. This is easier said than done; trying to mix both ideas in a language means you
have features to support both, but to use them effectively is truly an art.
So, if Java is imperative in nature, why are we talking about functional programming
in this book? Well, as I pointed out, sometimes, it is better to mix both concepts and
get the best of both worlds. Recently, the Java community has taken note of this fact
and has introduced a feature lambda from Java version 8 to provide some level of
functional programming support. So, our intention is not to program completely in
functional style, as that is not the preferred programming style of Java, but we will
do it just enough to make our programs more beautiful and to aid our understanding
of algorithms.
[ 57 ]
Detour – Functional Programming
This chapter will introduce this rather foreign concept to you and provide some
basic tools that are commonly used in functional programming. You will learn the
following concepts:
•
Recursive algorithms and the immutability of variables
•
Monads
•
Aggregations on monads
•
Java's support for functional programming, that is, lambda.
Recursive algorithms
As I have already pointed out, recursive algorithms are a different way of thinking
about solving a problem. For example, say our problem is to write a program that,
given a positive integer n, returns the sum of numbers from zero to n. The known
imperative way of writing it is simple:
public int sum_upto(int n){
int sum=0;
for(int i=0;i<=n;i++){
sum+=i;
}
return sum;
}
The following would be the functional version of the problem:
public int sum_upto_functional(int n){
return n==0?0:n+sum_upto_functional(n-1);
}
That's it–just a one-liner! This is probably nothing new to Java programmers, as they
do understand recursive functions. However, an imperative programmer would use
recursion only when nothing else worked. But this is a different way of thinking.
How do we justify that it is equivalent to solving the problem for a smaller input and
then composing it with something else? Well, we are certainly first computing the
same function for an input that is smaller by one and then just adding n to it. There is
one more thing to note here: in the imperative version, we are updating the variable
called sum for each value of the loop variable i. However, in the functional version,
we are not updating any variable. What do we achieve by that? When a variable is
updated multiple times in a program, it is hard to understand or debug it because
you need to keep track of the latest value. When this does not happen, it is far easier
to understand what is happening. In fact, it makes it simpler in such a way that we
can even prove the correctness of the program completely formally, which is rather
hard to do for imperative programs where variables change values.
[ 58 ]
Chapter 4
Let's check out another example. This one is about choosing r objects from n objects,
where the order does not matter. Let's have a set A of a finite amount of objects. Let
the number of objects in this set be n. How many subsets B of this set A have exactly
r elements? Of course, the maximum number of elements any subset of A can have
is n; hence r ≤ n. We will call this function choose. So, we write this as choose(n,r).
Now, the only subset that has an equal number of elements as A is A itself. So,
choose(n,n) equals 1.
How do we break this problem into subproblems of a similar nature but with smaller
input? To find out how many subsets B have r elements, we first think of the set A as
a combination of a subset C with n-1 elements and one particular element a. So, we
can say A = C ⋃ {a}. Now, we consider two disjoint cases: the element a is a member
of the subset B and when it is not a member of the subset B. When a is not a member
of the subset B, B is also a subset of C. The number of such subsets B with exactly
r elements is choose(n-1,r), since C has n-1 elements. On the other hand, when
a is a member of the set B, then B can be thought of as a union of two sets – a set D
that has all the elements of B except a, and the other is just {a}. So, B = D ⋃ {a}. Now,
you can see that D is a subset of C that we defined. How many such subsets D are
there of C? There are choose(n-1,r-1) subsets, since C has n-1 elements and D has
r-1 elements. So, the number of such subsets B is choose(n-1,r-1). This means
that the total number of sets B with or without a as an element is choose(n-1,r) +
choose(n-1,r-1). If we put this in recursive calls, the r and n will get reduced until
r equals zero or n equals r. We have already considered the case when n equals r,
that is, choose(n,n). When r equals zero, it means B is the null set. Since there is
only one null set, choose(n,0) equals 1. Now, we put this in code:
public long choose(long n, long r){
if(nx+1;
int y = sfi.modify(1);
Take note of the parentheses and the arrow sign. The parentheses contain all the
parameters. The types of parameters are not specified because they are already
specified in the interface method. There can be zero or more parameters.
There are two kinds of lambda syntax–one that has an expression as the body and
one that has one or more steps as the body. These lambdas look a bit different from
each other. A lambda that is implemented as a one liner looks like the one we just
saw. This is called an expression syntax. The expression syntax can be used if the
lambda expression is a one liner. For multi-line code, we use the block syntax as
shown below:
Thread t = new Thread(()->{for(int i=0;i<500;i++)
System.out.println(i);});
One can use block syntax for functions that return a value as well, especially when
using multiple lines of code. In that case, one just needs to use a return statement to
return a value.
[ 61 ]
Detour – Functional Programming
Since in a functional program all variables must not ever be
reassigned, we should declare them final to avoid accidentally
modifying them. However, since typing final for every
variable clutters the code a bit, we avoid doing so. In a purely
functional language, the variables are immutable by default.
Even in a semifunctional language, such as Scala, it is so if
it generally encourages the functional style. However, since
Java mostly prefers an imperative style, the final keyword is
necessary, causing a little clutter.
Now that we know about lambda, we can start learning about functional
data structures.
Functional data structures and monads
Functional data structures are data structures that follow the principle of immutability
and inductive (or recursive) definition. Immutability means that any modification of
the data structure would result in a new data structure, and any old reference to the
original version would still have access to the original version. Inductive definition
means that the definition of the structure is defined as a composition of smaller
versions of the same data structure. Take, for example, our linked list. When we add
an element to or remove an element from the beginning of the list, it will modify
the linked list. That means any reference to the linked list will now hold a reference
to the modified linked list. This doesn't conform to the principle of immutability. A
functional linked list would make sure that the older references still held reference to
an unmodified version. We will discuss how to do it in the next section.
Functional linked lists
To make a linked list that is immutable, we consider a linked list to be made of
two parts:
•
A head containing the first element of the list
•
A tail containing another linked list containing the rest of the elements
Note that we have now defined the linked list recursively, being true to our
functional design. This recursion says that a linked list is:
•
Either an empty list
•
Or a set of two objects, as follows:
°°
A head containing one element of its element type
°°
A tail containing another linked list of the same type
[ 62 ]
Chapter 4
This version of the definition is the same as the previous simplified one, except
that we have now specified how we represent where the list terminates. The list
terminates where there are no more elements, that is, when the tail is an empty list.
Let's put all these in code.
First, we define a version according to the simplified definition:
public class LinkedList {
private E head;
private LinkedList tail;
private LinkedList(){
}
private LinkedList(E head, LinkedList tail){
this.head = head;
this.tail = tail;
}
public E head(){
return head;
}
public LinkedList tail(){
return tail;
}
This is the core of immutability for our linked list. Note that every time we add a
new value to our linked list, we create a new linked list so that the old references still
hold references to the unmodified list:
public LinkedList add(E value){
return new LinkedList(value,this);
}
}
The code is self-explanatory, now that we already know how we think about our
linked list. But note that we have made the constructors private. We don't want
people to create inconsistent versions of our linked lists, such as a null tail or
something. We insist that everyone creates our linked list by first creating an empty
linked list and then adding elements to it. So, we add the following EmptyList class
and add() method:
public static final class EmptyList extends LinkedList{
@Override
public E head() {
[ 63 ]
Detour – Functional Programming
throw new NoValueException("head() invoked on empty list");
}
@Override
public LinkedList tail() {
throw new NoValueException("tail() invoked on empty list");
}
}
public static LinkedList emptyList(){
return new EmptyList<>();
}
Now we can use the linked list as follows:
LinkedList linkedList = LinkedList.emptyList()
.add(5).add(3).add(0);
while(!(linkedList instanceof LinkedList.EmptyList)){
System.out.println(linkedList.head());
linkedList = linkedList.tail();
}
But wait, did we just modify the linkedList variable in the while loop? Yes, but
that does not comply with the principle of immutability. To solve this, let's see what
we would mostly want to do with a list. In general, we would want to perform the
following operations:
•
Do something for each element of the list. For example, print all the elements
to the console.
•
Get a new list where each element is transformed using a function that is
provided.
•
Compute a function of all the elements in the list. This is an aggregation of
the elements. For example, find the sum of all the elements.
•
Create a new list containing only selected elements of the list. This is
called filtering.
We will deal with them one by one. At the end of the next section, you will be
prepared to learn about monads as well.
[ 64 ]
Chapter 4
The forEach method for a linked list
The forEach() method on a linked list would do something for each element of
the list. This something would be passed as a lambda. For this purpose, we will
first create a functional interface that consumes one parameter but does not return
anything:
@FunctionalInterface
public interface OneArgumentStatement {
void doSomething(E argument);
}
With this interface available, we will define the forEach() method for a list,
as follows:
public class LinkedList {
…
public static class EmptyList extends LinkedList{
…
@Override
public void forEach(OneArgumentStatement processor) {}
}
…
public void forEach(OneArgumentStatement processor){
processor.doSomething(head());
tail().forEach(processor);
}
}
The ellipsis represent more code that we have already discussed and need not be
repeated. The forEach() method simply processes the head and then recursively
calls itself on the tail. Note again that, true to our philosophy of recursion, we have
implemented the forEach() method using recursion. Of course, this will not work
on an empty list because the head and tail are null. The empty list represents when
the method needs to stop calling itself. We achieve this by overriding the forEach()
method in the EmptyList class to not do anything.
Now we can print all the elements using the following code:
linkedList.forEach((x) -> {System.out.println(x);});
[ 65 ]
Detour – Functional Programming
We pass a lambda that, given any element x, calls System.out.println on x. But, if
you see, this lambda just works as a delegation to the System.out.println method
that already has the required form of the lambda. Java allows you to use a method as
a lambda with the following syntax. The :: operator is used to tell the compiler that
you are not looking for a field with that name; instead you are looking for a method
with that name:
linkedList.forEach(System.out::println);
Note that this time we did not even modify the list while printing the elements,
unlike last time, when we did it using a loop.
Map for a linked list
Now we move on to the next thing we want to do with a list, which is to create a new
list where all the elements are transformed according to a lambda that is provided.
What I mean is that we want to do the following:
LinkedList tranformedList = linkedList.map((x)->x*2);
We need to implement the map() method in a way that transformedList holds all
the elements of linkedList multiplied by 2, in the same order. The following is the
implementation of the map() method:
public class LinkedList {
…
public static class EmptyList extends LinkedList{
…
@Override
public LinkedList map(OneArgumentExpression transformer) {
return LinkedList.emptyList();
}
}
…
public LinkedList map(OneArgumentExpression transformer){
return new LinkedList<>(transformer.compute(head()),
tail.map(transformer));
}
}
[ 66 ]
Chapter 4
As usual, the method is defined recursively. The transformed list is just the head
transformed followed by the tail transformed. We have also overridden the method
in the EmptyList class to return an empty list because an empty list transformed
is just another empty list of a possibly different type. With this implementation in
place, we can do the following:
LinkedList tranformedList = linkedList.map((x)->x*2);
tranformedList.forEach(System.out::println);
This should print a list with all the values multiplied by 2. You can even change the
type of the elements by transformation, such as the following:
LinkedList tranformedListString
= linkedList.map((x)->"x*2
= "+(x*2));
tranformedListString.forEach(System.out::println);
The tranformedListString list is a list of strings, and printing each element on the
next line shows the strings obtained.
Now we move on to the next thing we want to do with a list, which is to compute
some function that uses all the values in the list. This is called an aggregation
operation. But before looking at a general case, we will concentrate on a specific one,
called a fold operation.
Fold operation on a list
A fold operation on a list is an aggregation operation that can be done element by
element. For example, if we want to compute the sum of all the elements of a list, we
can do it by taking each element of the list and adding it to a moving sum, so when
we are done with processing all the elements, we will have the sum of all elements.
There are two operations that suit this purpose: foldLeft and foldRight. The
foldLeft operation aggregates the head first and moves on to the tail. The
foldRight method aggregates the tail first and then moves on to the head. Let's
start with foldLeft. But before doing anything, we need a functional interface that
represents an expression of two parameters:
@FunctionalInterface
public interface TwoArgumentExpression {
R compute(A lhs, B rhs);
}
[ 67 ]
Detour – Functional Programming
With this interface available, we define the foldLeft method in the following way:
public class LinkedList {
…
…
public static class EmptyList extends LinkedList{
…
@Override
public R foldLeft(R initialValue, TwoArgumentExpression computer) {
return initialValue;
}
}
…
public R foldLeft(R initialValue,
TwoArgumentExpression computer){
R newInitialValue = computer.compute(initialValue, head());
return tail().foldLeft(newInitialValue, computer);
}
}
We compute a new value from initialValue and the head using the lambda
passed, and then we use this updated value to compute foldLeft on the tail. The
empty list overrides this method to just return the initialValue itself because it just
marks the end of the list. Now we can compute the sum of all elements as follows:
int sum = linkedList.foldLeft(0,(a,b)->a+b);
System.out.println(sum);
We have passed 0 as the initial value and the lambda that sums up the values passed.
This looks complicated until you get used to this idea, but once you get used to it, it
is very simple. Let's see what is happening step by step; the list from head to tail is
{0,3,5}:
1. In the first invocation, we pass the initial value 0. The computed
newInitialValue is 0+0 = 0. Now, we pass this newInitialValue to the
tail to foldLeft, which is {3,5}.
2. The {3,5} has a head 3 and tail {5}. 3 is added to the initialValue 0 to
give a newInitialValue 0+3=3. Now, this new value 3 is passed to the tail
{5} to foldLeft.
[ 68 ]
Chapter 4
3. The {5} has a head 5 and tail and empty list. 5 is added to the
initialValue 3 to get 8. Now this 8 is passed as initialValue to the tail,
which is an empty list.
4. The empty list, of course, just returns the initial value for a foldLeft
operation. So it returns 8, and we get the sum.
Instead of computing one value, we can even compute a list as a result. The
following code reverses a list:
LinkedList reversedList =
linkedList.foldLeft(LinkedList.emptyList(),(l,b)->l.add(b) );
reversedList.forEach(System.out::println);
We have simply passed an empty list as an initial operation, and then our operation
simply adds a new element to the list. In the case of foldLeft, the head will be
added before the tail, causing it to be placed more in the tail side in the newly
constructed list.
What if we want to process the right-most end (or away from the head) first and
move to the left? This operation is called foldRight. This can be implemented in a
very similar manner, as follows:
public class LinkedList {
…
public static class EmptyList extends LinkedList{
…
@Override
public R foldRight(TwoArgumentExpression computer, R initialValue) {
return initialValue;
}
}
…
public R foldRight(TwoArgumentExpression computer,
R initialValue){
R computedValue = tail().foldRight(computer, initialValue);
return computer.compute(head(), computedValue);
}
}
[ 69 ]
Detour – Functional Programming
We have switched the order of the arguments to make it intuitive that the
initialValue is being combined from the right end of the list. The difference from
foldLeft is that we compute the value on the tail first, calling a foldRight on it.
Then we return the result of the computed value from the tail being combined with
the head to get the result. In the case of computing a sum, it does not make any
difference which fold you invoke because sum is commutative, that is, a+b always
equals b+a. We can call the foldRight operation for the computation of sum in the
following way, which will give the same sum:
int sum2 = linkedList.foldRight((a,b)->a+b, 0);
System.out.println(sum2);
However, if we use an operator that is not commutative, we will get a different
result. For example, if we try reversing the list with the foldRight method, it will
give the same list instead of being reversed:
LinkedList sameList = linkedList.foldRight((b,l)>l.add(b), LinkedList.emptyList());
sameList.forEach(System.out::println);
The final thing we wanted to do with a list was filtering. You will learn it in the
next subsection.
Filter operation for a linked list
Filter is an operation that takes a lambda as a condition and creates a new list that
has only those elements that satisfy the condition. To demonstrate this, we will create
a utility method that creates a list of a range of elements.
First, we create a helper method that appends a range of numbers to the head of an
existing list. This method can call itself recursively:
private static LinkedList ofRange(int start, int end,
LinkedList tailList){
if(start>=end){
return tailList;
}else{
return ofRange(start+1, end, tailList).add(start);
}
}
[ 70 ]
Chapter 4
Then we use the helper method to generate a list of a range of numbers:
public static LinkedList ofRange(int start, int end){
return ofRange(start,end, LinkedList.emptyList());
}
This will let us create a list of a range of integers. The range includes the start and
excludes the end. For example, the following code will create a list of numbers from
1 to 99 and then print the list:
LinkedList rangeList = LinkedList.ofRange(1,100);
rangeList.forEach(System.out::println);
We now want to create a list of all even numbers, say. For that, we create a filter
method in the LinkedList class:
public class LinkedList {
…
public static class EmptyList extends LinkedList{
…
@Override
public LinkedList filter(OneArgumentExpression selector) {
return this;
}
}
…
public LinkedList filter(OneArgumentExpression selector){
if(selector.compute(head())){
return new LinkedList(head(), tail().filter(selector));
}else{
return tail().filter(selector);
}
}
}
[ 71 ]
Detour – Functional Programming
The filter() method checks whether the the condition is met. If yes, then it includes
the head and calls the filter() method on the tail. If not, then it just calls the
filter() method on the tail. The EmptyList of course needs to override this method
to just return itself because all we need is an empty list. Now, we can do the following:
LinkedList evenList =
LinkedList.ofRange(1,100).filter((a)->a%2==0);
evenList.forEach(System.out::println);
This will print all the even numbers between 1 and 99. Let's go through some more
examples in order to get used to all this stuff. How do we add all numbers from 1 to
100? The following code will do that:
int sumOfRange = LinkedList.ofRange(1,101).foldLeft(0, (a,b)>a+b);
System.out.println(sumOfRange);
Note that we have used the range of (1,101) because the end number is not
included in the generated linked list.
How do we compute the factorial of a number using this? We define a factorial
method as follows:
public static BigInteger factorial(int x){
return LinkedList.ofRange(1,x+1)
.map((a)->BigInteger.valueOf(a))
.foldLeft(BigInteger.valueOf(1),(a,b)->a.multiply(b));
}
We have used Java's BigInteger class because factorials grow too fast and an int
or a long cannot hold much. This code demonstrates how we converted the list of
integers to a list of BigIntegers using the map method before multiplying them
with the foldLeft method. We can now compute the factorial of 100 with the
following code:
System.out.println(factorial(100));
This example also demonstrates the idea that we can combine the methods we
developed to solve more complicated problems. Once you get used to this, reading
a functional program and understanding what it does is a lot simpler than doing
the same for their imperative versions. We have even used one-character variable
names. Actually, we could use meaningful names, and in some cases, we should. But
here the program is so simple and the variables used are so close to where they are
defined that it's not even necessary to name them descriptively.
[ 72 ]
Chapter 4
Let's say we want to repeat a string. Given an integer, n, and a string, we want
the resultant string to be a repetition of the original string n number of times.
For example, given an integer 5 and a string Hello, we want the output to be
HelloHello HelloHello Hello. We can do this with the following function:
public static String repeatString(final String seed, int count){
return LinkedList.ofRange(1,count+1)
.map((a)->seed)
.foldLeft("",(a,b)->a+b);
}
What we are doing here is first creating a list of length count and then replacing all
its elements with the seed. This gives us a new list with all the elements equal to the
seed. This can be folded to get the desired repeated string. This is easy to understand
because it is very much like the sum method, except we are adding strings instead
of integers, which causes repetition of the string. But we don't even need to do this.
We can do this even without creating a new list with all the elements replaced. The
following will do it:
public static String repeatString2(final String seed, int count){
return LinkedList.ofRange(1,count+1)
.foldLeft("",(a,b)->a+seed);
}
Here, we just ignore the integer in the list and add the seed instead. In the first
iteration, a would be set to the initial value, which is an empty string. Every time, we
just ignore the content and instead add the seed to this string. Note that in this case,
variable a is of the String type and variable b is of the Integer type.
So, we can do a lot of things using a linked list, using its special methods with
lambda parameters. This is the power of functional programming. What we are
doing with lambda, though, is that we are passing the implementation of interfaces
as pluggable code. This is not a new concept in an object-oriented language.
However, without the lambda syntax, it would take a lot of code to define an
anonymous class to do the equivalent, which would clutter the code a lot, thus
undermining the simplicity. What has changed though is the immutability, leading
to chaining of methods and other concepts. We are not thinking about state while
analyzing the programs; we are simply thinking of it as a chain of transformations.
The variables are more like variables in algebra, where the value of x stays the same
throughout a formula.
[ 73 ]
Detour – Functional Programming
Append on a linked list
We have completed all the things that were in the list of the things we wanted to
do. There may be a few more. One important thing, for example, is append. This
operation sticks one list to another. This can be done using the foldRight method
that we have already defined:
public LinkedList append(LinkedList rhs){
return this.foldRight((x,l)->l.add(x),rhs);
}
Now, we perform the following:
LinkedList linkedList =
LinkedList.emptyList().add(5).add(3).add(0);
LinkedList linkedList2 =
LinkedList.emptyList().add(6).add(8).add(9);
linkedList.append(linkedList2).forEach(System.out::print);
This will output 035986, which is the first list stuck in front of the second list.
To understand how it works, first remember what a foldRight operation does. It
starts with an initial value–in this case, the right hand side (RHS). Then it takes one
element at a time from the tail end of the list and operates on that with the initial
list using the provided operation. In our case, the operation simply adds an element
to the head of the initial list. So, in the end, we get the entire list appended to the
beginning of the RHS.
There is one more thing that we want to do with a list, but we have not talked about
it until now. This concept requires an understanding of the earlier concepts. This is
called a flatMap operation, and we will explore it in the next subsection.
The flatMap method on a linked list
The flatMap operation is just like the map operation, except we expect the operation
passed to return a list itself instead of a value. The job of the flatMap operation is to
flatten the lists thus obtained and append them one after another. Take for example
the following code:
LinkedList funnyList
=LinkedList.ofRange(1,10)
.flatMap((x)->LinkedList.ofRange(0,x));
[ 74 ]
Chapter 4
The operation passed returns a range of numbers starting from 0 to x-1. Since we
started the flatMap on a list of numbers from 1 to 9, x will get values from 1 to 9.
Our operation will then return a list containing 0,x-1 for each value of x. The job
of the flatMap operation is to then flatten all these lists and stick them one after
another. Take a look at the following line of code, where we print funnyList:
funnyList.forEach(System.out::print);
It will print 001012012301234012345012345601234567012345678 on the output.
So, how do we implement the flatMap operation? Let's have a look:
public class LinkedList {
public static class EmptyList extends LinkedList{
…
@Override
public LinkedList flatMap(OneArgumentExpression> transformer) {
return LinkedList.emptyList();
}
}
…
public LinkedList flatMap(OneArgumentExpression> transformer){
return transformer.compute(head())
append(tail().flatMap(transformer));
}
}
So what is happening here? First, we compute the list obtained by the head and
the result of the flatMap operation on the tail. Then we append the result of the
operation on the head of the list in front of the list obtained by flatMap on the tail. In
case of an empty list, the flatMap operation just returns an empty list because there
is nothing for the transformation to be called on.
[ 75 ]
Detour – Functional Programming
The concept of a monad
In the previous section, we saw quite a few operations for a linked list. A few of
them, namely map and flatMap, are a common theme in many objects in functional
programming. They have a meaning outside of the list. The map and flatMap
methods, and a method to construct a monad from a value are what make such a
wrapper object a monad. A monad is a common design pattern that is followed
in functional programming. It is a sort of container, something that stores objects
of some other class. It can contain one object directly as we will see; it can contain
multiple objects as we have seen in the case of a linked list, it can contain objects
that are only going to be available in the future after calling some function, and
so on. There is a formal definition of monad, and different languages name its
methods differently. We will only consider the way Java defines the methods. A
monad must have two methods, called map() and flatMap(). The map() method
accepts a lambda that works as a transformation for all the contents of the monad.
The flatMap method also takes a method, but instead of returning the transformed
value, it returns another monad. The flatMap() method then extracts the output
from the monad and creates a transformed monad. We have already seen an example
of a monad in the form of a linked list. But the general theme does not become clear
until you have seen a few examples instead of just one. In the next section, we will
see another kind of monad: an option monad.
Option monad
An option monad is a monad containing a single value. The whole point of this is to
avoid handling null pointers in our code, which sort of masks the actual logic. The
point of an option monad is to be able to hold a null value in a way that null checks
are not required in every step. In some way, an option monad can be thought of as
a list of zero or one objects. If it contains just zero objects, then it represents a null
value. If it contains one object, then it works as the wrapper of that object. The map
and flatMap methods then behave exactly like they would behave in the case of a
one-argument list. The class that represents an empty option is called None. First, we
create an abstract class for an option monad. Then, we create two inner classes called
Some and None to represent an Option containing a value and one without a value,
respectively. This is a more general pattern for developing a monad and can cater to
the fact that the non-empty Option has to store a value. We could do this with a list
as well. Let's first see our abstract class:
public abstract class Option {
public abstract E get();
public abstract Option map(OneArgumentExpression
transformer);
public abstract Option flatMap(OneArgumentExpression> transformer);
[ 76 ]
Chapter 4
public abstract void forEach(OneArgumentStatement statement);
…
}
A static method optionOf returns the appropriate instance of the Option class:
public static Option optionOf(X value){
if(value == null){
return new None<>();
}else{
return new Some<>(value);
}
}
We now define the inner class, called None:
public static class None extends Option{
@Override
public Option flatMap(OneArgumentExpression> transformer) {
return new None<>();
}
@Override
public E get() {
throw new NoValueException("get() invoked on None");
}
@Override
public Option map(OneArgumentExpression transformer) {
return new None<>();
}
@Override
public void forEach(OneArgumentStatement statement) {
}
}
We create another class, Some, to represent a non-empty list. We store the value as a
single object in the class Some, and there is no recursive tail:
public static class Some extends Option{
E value;
public Some(E value){
[ 77 ]
Detour – Functional Programming
this.value = value;
}
public E get(){
return value;
}
…
}
The map and flatMap methods are pretty intuitive. The map method accepts a
transformer and returns a new Option where the value is transformed. The flatMap
method does the same, except it expects the transformer to wrap the returned value
inside another Option. This is useful when the transformer can sometimes return a
null value, in which case the map method will return an inconsistent Option. Instead,
the transformer should wrap it in an Option, for which we need to use a flatMap
operation. Have a look at the following code:
public static class Some extends Option{
…
public Option map(OneArgumentExpression transformer){
return Option.optionOf(transformer.compute(value));
}
public Option flatMap(OneArgumentExpression> transformer){
return transformer.compute(value);
}
public void forEach(OneArgumentStatement statement){
statement.doSomething(value);
}
}
To understand the usage of an Option monad, we will first create a JavaBean. A
JavaBean is an object exclusively intended to store data. It is the equivalent of a
structure in C. However, since encapsulation is a defining principle of Java, the
members of the JavaBean are not accessed directly. They are instead accessed
through special methods called getters and setters. However, our functional style
dictates that the beans be immutable, so there won't be any setter methods. The
following set of classes gives a few examples of JavaBeans:
public class Country {
private String name;
private String countryCode;
public Country(String countryCode, String name) {
this.countryCode = countryCode;
[ 78 ]
Chapter 4
this.name = name;
}
public String getCountryCode() {
return countryCode;
}
public String getName() {
return name;
}
}
public class City {
private String name;
private Country country;
public City(Country country, String name) {
this.country = country;
this.name = name;
}
public Country getCountry() {
return country;
}
public String getName() {
return name;
}
}
public class Address {
private String street;
private City city;
public Address(City city, String street) {
this.city = city;
this.street = street;
}
public City getCity() {
return city;
}
public String getStreet() {
return street;
[ 79 ]
Detour – Functional Programming
}
}
public class Person {
private String name;
private Address address;
public Person(Address address, String name) {
this.address = address;
this.name = name;
}
public Address getAddress() {
return address;
}
public String getName() {
return name;
}
}
There is not much to understand in these four classes. They are there to store a
person's data. In Java, it is not very uncommon to hit a case where you will hit a very
similar kind of object.
Now, let's say, given a variable person of type Person, we want to print the name of
the country he/she lives in. If the case is that any of the state variables can be null,
the correct way to do it with all null checks would look like the following:
if(person!=null
&& person.getAddress()!=null
&&
person.getAddress().getCity()!=null
&&
person.getAddress().getCity().getCountry()!=null){
System.out.println(person.getAddress().getCity().getCountry());
}
This code would work, but let's face it–it's a whole bunch of null checks. We can get
a hold of the address simply by using our Options class, as follows:
String countryName = Option.optionOf(person)
.map(Person::getAddress)
.map(Address::getCity)
.map(City::getCountry)
.map(Country::getName).get();
[ 80 ]
Chapter 4
Note that if we just print this address, there is a chance that we will print null. But it
would not result in a null-pointer exception. If we don't want to print null, we need a
forEach method just like the one in our linked list:
public class Option {
public static class None extends Option{
…
@Override
public void forEach(OneArgumentStatement statement) {
}
}
…
public void forEach(OneArgumentStatement statement){
statement.doSomething(value);
}
}
The forEach method just calls the lambda passed on the value it contains, and the
None class overrides it to do nothing. Now, we can do the following:
Option.optionOf(person)
.map(Person::getAddress)
.map(Address::getCity)
.map(City::getCountry)
.map(Country::getName)
.forEach(System.out::println);
This code will now not print anything in case of a null name in country.
Now, what happens if the Person class itself is functionally aware and returns
Options to avoid returning null values? This is where we need a flatMap. Let's
make a new version of all the classes that were a part of the Person class. For brevity,
I will only show the modifications in the Person class and show how it works. You
can then check the modifications on the other classes. Here's the code:
public class Person {
private String name;
private Address address;
public Person(Address address, String name) {
this.address = address;
this.name = name;
[ 81 ]
Detour – Functional Programming
}
public Option getAddress() {
return Option.optionOf(address);
}
public Option getName() {
return Option.optionOf(name);
}
}
Now, the code will be modified to use flatMap instead of map:
Option.optionOf(person)
.flatMap(Person::getAddress)
.flatMap(Address::getCity)
.flatMap(City::getCountry)
.flatMap(Country::getName)
.forEach(System.out::println);
The code now fully uses the Option monad.
Try monad
Another monad we can discuss is the Try monad. The point of this monad is to make
exception handing a lot more compact and avoid hiding the details of the actual
program logic. The semantics of the map and flatMap methods are self-evident.
Again, we create two subclasses, one for success and one for failure. The Success
class holds the value that was computed, and the Failure class holds the exception
that was thrown. As usual, Try is an abstract class here, containing one static method
to return the appropriate subclass:
public abstract class Try {
public abstract Try map(
OneArgumentExpressionWithException expression);
public abstract Try flatMap(
OneArgumentExpression> expression);
public abstract E get();
public abstract void forEach(
OneArgumentStatement statement);
public abstract Try processException(
[ 82 ]
Chapter 4
OneArgumentStatement statement);
…
public static Try of(
NoArgumentExpressionWithException expression) {
try {
return new Success<>(expression.evaluate());
} catch (Exception ex) {
return new Failure<>(ex);
}
}
…
}
We need a new NoArgumentExpressionWithException class and a
OneArgumentExpressionWithException class that allows exceptions in its body.
They are as follows:
@FunctionalInterface
public interface NoArgumentExpressionWithException {
R evaluate() throws Exception;
}
@FunctionalInterface
public interface OneArgumentExpressionWithException {
R compute(A a) throws Exception;
}
The Success class stores the value of the expression passed to the of() method.
Note that the of() method already executes the expression to extract the value.
protected static class Success extends Try {
protected E value;
public Success(E value) {
this.value = value;
}
The fact is that this is a class that represents the success of the earlier expression;
the flatMap has to only handle exceptions in the following expression, which the
following Try passed to it handles itself, so we can just return that Try instance itself:
@Override
public Try flatMap(
OneArgumentExpression> expression) {
return expression.compute(value);
}
[ 83 ]
Detour – Functional Programming
The map() method, however, has to execute the expression passed. If there is an
exception, it returns a Failure; otherwise it returns a Success:
@Override
public Try map(
OneArgumentExpressionWithException expression) {
try {
return new Success<>(
expression.compute(value));
} catch (Exception ex) {
return new Failure<>(ex);
}
}
The get() method returns the value as expected:
@Override
public E get() {
return value;
}
The forEach() method lets you run another piece of code on the value without
returning anything:
@Override
public void forEach(
OneArgumentStatement statement) {
statement.doSomething(value);
}
This method does not do anything. The same method on the Failure class runs
some code on the exception:
@Override
public Try processException(
OneArgumentStatement statement) {
return this;
}
}
Now, let's look at the Failure class:
protected static class Failure extends Try {
protected Exception exception;
public Failure(Exception exception) {
this.exception = exception;
}
[ 84 ]
Chapter 4
Here, in both the flatMap() and map() methods, we just change the type of
Failure, but return one with the same exception:
@Override
public Try flatMap(
OneArgumentExpression> expression) {
return new Failure<>(exception);
}
@Override
public Try map(
OneArgumentExpressionWithException expression) {
return new Failure<>(exception);
}
There is no value to be returned in the case of a Failure:
@Override
public E get() {
throw new NoValueException("get method invoked on Failure");
}
We don't do anything in the forEach() method because there is no value to be
worked on, as follows:
@Override
public void forEach(
OneArgumentStatement statement) {
…
}
The following method runs some code on the exception contained in the
Failure instance:
@Override
public Try processException(
OneArgumentStatement statement) {
statement.doSomething(exception);
return this;
}
}
[ 85 ]
Detour – Functional Programming
With this implementation of the Try monad, we can now go ahead and write some
code that involves handing exceptions. The following code will print the first line of
the file demo if it exists. Otherwise, it will print the exception. It will print any other
exception as well:
Try.of(() -> new FileInputStream("demo"))
.map((in)->new InputStreamReader(in))
.map((in)->new BufferedReader(in))
.map((in)->in.readLine())
.processException(System.err::println)
.forEach(System.out::println);
Note how it removes the clutter in handling exceptions. You should, at this stage,
be able to see what is going on. Each map() method, as usual, transforms a value
obtained earlier, only, in this case, the code in the map() method may throw an
exception and that would be gracefully contained. The first two map() methods
create a BufferedReader in from a FileInputStream, while the final map() method
reads a line from the Reader.
With this example, I am concluding the monad section. The monadic design pattern
is ubiquitous in functional programming and it's important to understand this
concept. We will see a few more monads and some related ideas in the next chapter.
Analysis of the complexity of a recursive
algorithm
Throughout the chapter, I have conveniently skipped over the complexity analysis
of the algorithms I have discussed. This was to ensure that you grasp the concepts of
functional programming before being distracted by something else. Now is the time
to get back to it.
Analyzing the complexity of a recursive algorithm involves first creating an
equation. This is naturally the case because the function is defined in terms of itself
for a smaller input, and the complexity is also expressed as a function of itself being
calculated for a smaller input.
For example, let's say we are trying to find the complexity of the foldLeft operation.
The foldLeft operation is actually two operations, the first one being a fixed operation
on the current initial value and the head of the list, and then a foldLeft operation on
the tail. Suppose T(n) represents the time taken to run a foldLeft operation on a list of
length n. Now, let's assume that the fixed operation takes a time A. Then, the definition
of the foldLeft operation suggests that T(n) = A + T(n-1). Now, we would try to find a
function that solves this equation. In this case, it is very simple:
[ 86 ]
Chapter 4
T(n) = A + T(n-1)
=> T(n) – T(n-1) = A
This means T(n) is an arithmetic progression and thus can be represented as
T(n) = An + C, where C is the initial starting point, or T(0).
This means T(n) = O(n). We have already seen how the foldLeft operation works in
linear time. Of course, we have assumed that the the operation involved is constant
with time. A more complex operation will result in a different complexity.
You are advised to try to compute the complexity of the other algorithms, which are
not very different from this one. However, I will provide a few more of these.
Earlier in this chapter, we implemented the choose function as follows:
choose(n,r) = choose(n-1,r) + choose(n-1, r-1)
If we assume that the time taken is given by the function T(n,r), then T(n,r) =
T(n-1,r) + T(n-1,r-1) + C, where C is a constant. Now we can do the following:
T(n,r) = T(n-1,r) + T(n-1,r-1) + C
=>T(n,r) 1) + C
T(n-1,r) = T(n-1,r-
Similarly, T(n-1,r) - T(n-2,r) = T(n-2,r-1) + C, by simply having n-1 in
place of n. By stacking such values, we have the following:
T(n,r) - T(n-1,r) =
T(n-1,r) - T(n-2,r)
T(n-2,r) - T(n-3,r)
…
T(r+1,r) - T(r,r) =
T(n-1,r-1) + C
= T(n-2,r-1) + C
= T(n-3,r-1) + C
T(r,r-1) + C
The preceding equation considers n-r such steps in total. If we sum both sides of the
stack, we have the following:
Of course, T(r,r) is constant time. Let's call it B. Hence, we have the following:
[ 87 ]
Detour – Functional Programming
Note that we can apply the same formula to T(i,r-1) too. This will give us the
following:
This gives the the following after simplification:
We can continue this way and we will eventually get an expression with multiple
nested summations, as follows:
Here A's and D's are also constants. When we are talking about asymptotic
complexity, we need to assume that a variable is sufficiently large. In this case,
there are two variables, with the condition that r is always less than or equal to n.
So, first we consider the case where r is fixed and n is being increased and being
made sufficiently large. In this case, there would be a total of r summations nested
in one another. T(t,0) is a constant time. The summation has r depth, each having a
maximum of (n-r) elements, so it is O((n-r)r). The other terms are O((n-r)r). Hence we
can say the following:
T(n,r) = O((n-r)r) = O(nr)
The size of the input is of course not n; it is log n = u (say). Then, we have the
complexity of computation of T(n,r) = O(2sr).
Another interesting case would be when we increase both r and n while also
increasing the difference between them. To do that, we may want a particular ratio
between the two, we assume r/n= k , k<1 always. Then we can see the asymptotic
growth of the function T(n, kn). But computing this requires calculus and is outside
the scope of this book.
[ 88 ]
Chapter 4
This shows that even though the analysis of algorithms in functional form can
be easier, the analysis of the time complexity can be fairly difficult. It is easy to
understand why it is more difficult to compute the complexity of a functional
algorithm. At the end of the day, computing complexity involves counting the
number of steps required to do the computation. In the imperative style, steps of
computation are direct, so it is easy to count them. On the other hand, a recursive
style is a higher level of abstraction, and hence, counting the number of steps is
harder. In the succeeding chapters, we will see more of these analyses.
Performance of functional programming
If we think about it, the whole point of functional programming is to have
immutability and recursive definitions (or inductive definitions) of programs so
that they can be analyzed easily. In general, adding additional constraints on your
program would make it simpler to analyze but would reduce what you can do with
it. Functional programming, of course, adds additional constraints on imperative
programming in the form of immutability, that is, you are no longer allowed
to reassign a variable. This is done so that the analysis of the program, that is,
understanding how the program works, is now simpler. It is also simpler to prove
theorems about the programs. However, we also lose some of the things that we
could do without such restrictions. It turns out that any program can be rewritten in
a functional style in a way to produce the same results. However, no guarantees are
made about their performance or complexity in general. So, a functional version of a
program can be a lot less efficient than its imperative counterpart. And indeed, in real
life, we face many such scenarios. So, it is really a tradeoff between performance and
simplicity. The general direction should then be that when working with a large input
size, it is better to do away with restrictions in order to be able to optimize more. On
the other hand, when the input sizes are small, it makes sense to stick to a functional
style because the performance is probably not affected much by it.
There are some cases, though, where the functional version has the same running
time complexity as the imperative version. In such a case, a functional version might
be preferred because of its simplicity. It should be noted that since Java does not
provide any explicit way of garbage collection and really, it happens by chance or
outside the control of the programmer, a functional programming style will fill up
the heap very quickly because of being immutable and thus being thrown away right
after being created. So, it will not be advisable to use them where performance is
really a problem.
[ 89 ]
Detour – Functional Programming
This would seem really contrary to the fact that many large data processing systems,
such as Spark, use a functional programming style. However, these systems only
have a specialized language that gives an appearance of a functional programming
style; they get translated to an almost non-functional form before they are even
executed. To elaborate a little more, a map method in a monad may not evaluate
anything at all; instead, it may just create a new object that contains this operator.
A general program can then analyze these structures and construct an imperative
program that does the same work. This provides a simple interface to the person
using the framework as well as keeping the resource usage under control. In the next
chapter, we will explore some of these ideas.
Summary
In this chapter, we learned a new way of looking at algorithms. The functional style
of writing a program can simplify the analysis of its correctness, that is, you can
easily understand why the program produces correct output. We saw a few patterns
in functional programming, especially monads. We also saw how Java provides
support for the functional style of programming through the syntax called lambda,
which has existed from version 9 of Java. Finally, we saw how to use lambda
effectively for functional programming.
Functional programs are, in general, easier to verify for correctness, but it is harder
to compute their complexity. They generally perform either at the same speed as
or slower than their imperative counterparts. It is a trade-off between development
effort and computational efficiency. For smaller inputs, it is thus desirable to have
a functional style of programming, whereas for processing large inputs, imperative
style may be preferred.
[ 90 ]
Efficient Searching – Binary
Search and Sorting
What is searching? Searching is trying to locate a given value in a collection of
values. For example, you are given an array of integers, and your problem is to check
whether the integer 5 is in that array. This is a search problem. In addition to just
deciding whether the element 5 is in the array, we may be interested in its location as
well when it is found. This is also a search problem.
Another interesting take on it would be to imagine a dictionary, that is, an array of
values and associated values. For example, you have an array of names of students
and their marks, as shown in the following table:
Name
Marks
Tom
63
Harry
70
Merry
65
Aisha
85
Abdullah
72
…
...
The list continues. Suppose, our system lets the student view his/her own marks.
They would type their name and the system would show their marks. For simplicity,
let's assume that there are no duplicate names. Now, we have to search for the name
provided and return the corresponding values. This is, thus, another search problem.
As we will see, search problems are quite ubiquitous in programming.
[ 91 ]
Efficient Searching – Binary Search and Sorting
In this chapter, you will learn the following:
•
Search algorithms
•
Efficient searching in a sorted list
•
Some sorting algorithms
Search algorithms
Suppose you are given an array of values and you are required to check whether a
particular value is in that array, what is the most natural way to find that element?
Well, it seems that the natural way is to go through each element one by one and
check whether they match the given value. If any one does, we have found that
element and we can return the index; if not, we can return -1 at the end of processing
all the elements to report that such an element could not be found. This is what we
would call a linear search. The following demonstrates a linear search algorithm in
an array:
public static int linearSearch(E[] values,
valueToLookup) {
for (int i = 0; i < values.length; i++) {
if (values[i].equals(valueToLookup)) {
return i;
}
}
return -1;
}
The function linearSearch takes an array of values and a value to search in it,
and returns the index if the value is found. If not, it returns a special value, -1. The
program simply goes through each element and checks whether the current element
matches with the value to lookup; if it does, then it just returns the current index,
otherwise it keeps looking. At the end of the array, it returns the special value, -1.
Now the following piece of code should return -1 in the first case and the value 5 in
the second case:
Integer[] integers = new Integer[]{232,54,1,213,654,23,
6,72,21};
System.out.println(ArraySearcher.linearSearch(integers,5));
System.out.println(ArraySearcher.linearSearch(integers,23));
[ 92 ]
Chapter 5
Now, if we want to solve the student-marks problem described in the introduction
of this chapter, we just need to have the marks of the students stored in a different
array in the same order, as follows:
static String[] students = new String[]{"Tom","Harry",
"Merry","Aisha", "Abdullah"};
static int[] marks = new int[]{63,70, 65, 85, 72};
Now we can write a function to search for a name:
public static Integer marksForName(String name){
int index = linearSearch(students, name);
if(index>=0){
return marks[index];
}else{
return null;
}
}
First, we look for the name of the students in the list of students. If the name is
found, the corresponding index would be assigned to the variable index and the
value would be greater than or equal to zero. In such a case, we return the marks
stored in the same index as of the marks array. If it is not found, we return null. To
lookup the marks for Merry, for example, we call as shown here:
System.out.println(marksForName("Merry"));
We correctly obtain her marks, that are, 65.
What is the complexity of linear search? We have a for loop that moves through
each element of an array of length n (say); in the worst case, we would go through
all the elements, so the worst case complexity is θ(n). Even on an average, we would
be visiting half the elements before we hit the correct element, so the average case
complexity is θ(n/2) = θ(n).
Binary search
Is a linear search the best we can do? Well, it turns out that if we are looking at an
arbitrary array, this is what we have to do. After all, in an arbitrary array, there is no
way to know whether an element is there without potentially looking at all of them.
More specifically, we cannot say for sure that some element does not exist, without
verifying all the elements. The reason is that the value of one element does not say
anything about the values of the other elements.
[ 93 ]
Efficient Searching – Binary Search and Sorting
But, what information can one element have about other elements in an array? One
way to make elements have information about the other elements is to have a sorted
array instead of just an arbitrary array. What is a sorted array? A sorted array is an
array that has all the elements arranged in order of their values. When an array is
sorted, every element contains the information that everything on the left is smaller
than that particular element, and everything on the right is bigger (or the other way
round if the order of the elements is opposite, but we will consider the arrays that
are sorted in an increasing order from left to right). This information can, amazingly,
make this search a lot faster. Here is what we do:
•
•
•
Check the middle element of the array. If it matches the element we are
searching for, we are done.
If the middle element is smaller than the value we are searching for, search
on the subarray on the right of the current array. This is because everything
on the left is even smaller.
If the middle element is bigger than the value we are searching for, search
only in the left sub-array.
To avoid creating copies of the array while creating a sub-array, we just pass on the
whole array, but we remember the start and end positions we are looking at. The
start is included in the range and end is excluded. So, only elements on the right of
the start position and the left of the end position are included in the subarray being
searched. The following figure gives a visual understanding of binary search:
Figure 1: Binary Search.
An arrow representing moving one element to another during the search.
[ 94 ]
Chapter 5
But, before implementing this algorithm, we need to understand the concept of
Comparable. Comparable is an interface in the Java standard library that looks
like this:
package java.lang;
public interface Comparable {
public int compareTo(T o);
}
Any class implementing this interface has to compare a different object with itself. It
is required that the type parameter, T, must be instantiated with the same class that
implements it, like this:
public class Integer implements Comparable{
public int compareTo(Integer o){
…
}
}
The compareTo method intends to compare an object of the same type. If the current
object (the one that the this reference refers to) is smaller than the object passed,
compareTo must return a negative value. If the object passed is smaller, the method
must return a positive value. Otherwise, if they are equal, it must return 0. The
following conditions are required to be fulfilled by the compareTo method:
•
If a.compareTo(b) == 0, then a.equals(b) must be true
•
If a.compareTo(b) < 0 and b.compareTo(c) < 0, then a.compareTo(c) <0
•
If a.compareTo(b) <0, then b.compareTo(a) > 0
•
If b.equals(c) is true and a.compareTo(b) <0, then a.compareTo(c) <0
•
If b.equals(c) is true and a.compareTo(b) >0, then a.compareTo(c) >0
Basically, the conditions are the same for a total order where equality is represented
by the equals method. It basically generalizes the concept of the < and <= operators,
which are there for numbers. Of course, the compareTo method for the Wrapper
objects are implemented exactly as the < and <= operators are on the primitives
inside them.
Now, we write the search function to do the search, as per the preceding steps:
private static ,
F extends E> int binarySearch( E[] sortedValues,
F valueToSearch, int start, int end) {
if(start>=end){
return -1;
}
[ 95 ]
Efficient Searching – Binary Search and Sorting
int midIndex = (end+start)/2;
int comparison = sortedValues[midIndex].compareTo(
valueToSearch);
if(comparison==0){
return midIndex;
}else if(comparison>0){
return binarySearch(sortedValues, valueToSearch,
start, midIndex);
}else{
return binarySearch(sortedValues, valueToSearch,
midIndex+1, end);
}
}
Note that in this case, we have mandated that the objects in the array must be
comparable so that we can know if an object is greater than or less than another
object. It does not matter exactly how this relationship is determined; the array must
be sorted using the same comparison – that the comparison between two consecutive
elements will make sure the element on the left is smaller than the one on the right,
as provided by Comparable.
The first if condition checks whether the array passed is empty, if so, obviously the
element to be searched is not found and we return -1 to represent this. Then, we find
the midIndex and recursively search for the element in either the left or the right
subarray. Once we have this function, we create another wrapper function to run the
search without having to mention the start and the end positions:
public static , F extends E>
int binarySearch(
E[] sortedValues, F valueToSearch) {
return binarySearch(sortedValues, valueToSearch, 0,
sortedValues.length);
}
Complexity of the binary search algorithm
In every step, we are partitioning the total array into two parts, barring the one element
that we are comparing. In the worst case, that is, the case where the element searched
is not present in the array, we will have to get down all the way to the point where we
are dealing with an empty array, in which case we return -1 and stop recursing. We
must have had an array of only one element in the previous step. For our analysis, we
will consider this step as the last step. So, let's have a sorted array of n elements and
T(.) is the time required for searching in the array. So, we have the following:
T(n) = T((n-1)/2) + C, where C is a constant.
[ 96 ]
Chapter 5
In general, the two search branches in every step would be of different sizes, one
potentially being of size one less than that of the other part. But we will ignore these
small differences, which hardly matter for a large n. Hence, we will work with the
following equation:
T(n) = T(n/2) + C
Now, let's assume that n is an integral power of 2 so that n = 2m for some integer m.
So, we have this:
T(2m) = T(2m-1) + C
Now we take another function S(.), such that S(m) = T(2m) for all m. Then, we have:
S(m) = S(m-1) + C
This is the formula for an arithmetic progression. And hence, we have this:
S(m) = mC + D, where D is also a constant.
=> T(2m) = mC + D
=> T(n) = C lg(n) + D
So, we have the asymptotic complexity of T(n):
T(n) = O(lg(n))
The function, T(n), grows only as fast as the logarithm of the size of the array passed,
which is really slow. This makes binary search an extremely efficient algorithm.
To sort of field test the algorithms, we run both linear and binary search algorithms
on an array of a hundred million elements with the following code:
int arraySize = 100000000;
Long array[] = new Long[arraySize];
array[0] = (long)(Math.random()*100);
for(int i=1;i T(n) – T(n-1) = Cn + D
Similarly, T(n-1) - T(n-2) = C(n-1) + D and so on. If we stack these equations, we get
the following:
T(n) – T(n-1) = Cn + D
T(n-1) – T(n-2) = C(n-1) + D
T(n-2) – T(n-3) = C(n-2) + D
T(n-3) – T(n-4) = C(n-3) + D
…
T(1) – T(0) = C(1) + D
[ 101 ]
Efficient Searching – Binary Search and Sorting
Adding both sides, we get this:
So, the selection sort has a complexity of θ(n2), where n is the size of the array being
sorted. Now, we will see the next sorting algorithm, which is the insertion sort.
Insertion sort
In selection sort, we first selected a position and then found the element that should
sit there. In the insertion sort, we do the opposite; we first select an element and then
insert the element into position where it should sit. So, for every element, we first
find out where it should be and then we insert the element in the right place. So, we
first see how to insert an element into a sorted array. The idea is that we are given an
array of sorted elements and we are supposed to insert another element in the correct
position, so that the resulting array remains sorted. We will consider a simpler
problem. We are given an array that is sorted except for the last element. Our job is
to insert the last element in the correct position. The recursive way to achieve this
insertion is as follows:
•
If the element to be inserted is bigger than the end element of the sorted
array, it belongs in the end and the insertion is complete.
•
Otherwise, we swap the last element with the element to be inserted and
recursively insert this element in the rest of the smaller array in front of it.
We do it with the following function. The function takes an array and a position that
represents this last position:
public static > void insertElementSorted(
E[] array, int valueIndex) {
if (valueIndex > 0 && array[valueIndex].compareTo(
array[valueIndex - 1]) < 0) {
swap(array, valueIndex, valueIndex - 1);
[ 102 ]
Chapter 5
insertElementSorted(array, valueIndex - 1);
}
}
If the last position or the valueIndex is 0, there is nothing to be done, as the element
is already in the correct position, that is, 0. There is no array to the left of valueIndex
in this case. If not, we compare the last element to the previous element. Since the
array on the left is presumed to be sorted, the previous element is the largest element
in the sorted part of the array. If the last element is bigger than even this one, there
is nothing more to be done. If not, we swap the last element with the previous one
and run the insertion recursively on the array with one less element. The last element
has moved to the previous position and it must now be compared with the element
before that, and so on.
With the insertion function available for sorted arrays, we are now ready to write
the algorithm for an insertion sort. In every step of the insertion sort, we consider
a boundary in the array. Everything on the left of the boundary has already been
sorted. Our job in the current step is to insert the element at the boundary index into
the left sorted array, which we achieve using the insertElementSorted function.
We implement this sort with the following simple strategy. In any step, we do
the following:
•
We first sort the left-hand side of the boundary so that our assumption about
it being sorted is achieved
•
Then we invoke the insertElementSorted function to insert the current
boundary element in the sorted array
Of course, when boundary is zero, it means that there is no array to be sorted and we
simply return:
public static > void insertionSort(
E[] array, int boundary) {
if(boundary==0){
return;
}
insertionSort(array, boundary-1);
insertElementSorted(array, boundary);
}
[ 103 ]
Efficient Searching – Binary Search and Sorting
Complexity of insertion sort
To compute the complexity of insertion sort, we must first compute it for the
insertElementSorted function. Let the time taken for an array of effective length
(that is, from zero to boundary-1), n be T(n). From there, we recursively call it with
n-1. So, we have the following:
T(n) = T(n-1) + C where C is a constant
=> T(n) = θ(n)
Let's now assume that the time taken for sorting an array of n elements is S(n).
Apart from the base case, it calls itself with one less argument and then calls the
insertElementSorted function with an array of effective length n-1. Thus, we
have this:
S(n) = S(n-1) + T(n) + D where D is a constant.
Again, when n is large, T(n) = θ(n); hence, it can be approximated by An where A is a
constant. So, we have this:
S(n) = S(n-1) + An + D
=> S(n) – S(n-1) = An + D,
Since this is true for all n, we have:
S(n) – S(n-1) = An + D
S(n-1) – S(n-2) = A(n-1) + D
S(n-2) – S(n-3) = A(n-2) + D
…
S(1) – S(0) = A + D
Summing both sides, we get the following:
Thus, insertion sort has the same asymptotic complexity as selection sort.
[ 104 ]
Chapter 5
Bubble sort
Another interesting sorting algorithm is a bubble sort. Unlike the previous
algorithms, this one works at a very local level. The strategy is as follows:
•
Scan through the array, searching pairs of consecutive elements that are
ordered wrongly. Then find a j, such that array[j+1] < array[j].
•
Whenever such a pair is found, swap them and continue searching until the
end of the array and then back from the beginning again.
•
Stop when a scan through the entire array does not even find a single
pair.
The code that does this is as follows:
public static