Short-circuit evaluation of booleans

 By now, you may have noticed this already, but it’s so important that it merits an article of its own: there are some instances in which you don’t care—so you don’t even compute—what certain expressions’ values are.

Suppose you have something like:

if(isMonday  || isWednesday || isFriday){
// stuff
}

Then, knowing that || means logical-or (so this means, in English, “if today is Monday, Wednesday, or Friday…”), one might look at the truth table for OR. The truth table contains all the possible inputs and their corresponding outputs:

For “OR”, that looks like:

Var1	Var2	Result
TRUE	TRUE	TRUE
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

That is, 2-way logical OR is false only if BOTH are false (3-, 4-way, etc., would only be false if ALL are false). Put another way, if ANY are true, then OR is true.

AND, likewise, has a table.

Var1	Var2	Result
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	FALSE
FALSE	FALSE	FALSE

For a logical AND to return true, both things being AND-ed must be true (likewise for multi-way AND, ALL must be true for it to be true; any falses cause an overall false). If BOTH are true, then AND is true; if ANY are false, then AND is false.

Back to our day-of-the-week example, once we see that any day matches with today, we don’t have to look at any of the other checks, since the expression is entirely OR-based. Just the fact that one of those is true, provided that they’re all connected by OR, is enough to make the whole expression true, and we can jump into whatever code is prescribed for that case.

Similarly, in a situation where

if(is16OrOlder && hasLicense && noRestrictions && carIsWorking){
// do stuff

}

If any of these are found to be false, we don’t need to check the others. AND works in such a way that, unless all chained ANDs are true, the whole thing is false.

This is a simple and incredibly common logical optimization in Java performed at the compiler level, known as short-circuit evaluation. If you have a sophisticated IDE, it will also probably tell you if it finds any variables that can be short-circuited. IntelliJ, at least in light mode, highlights such expressions in a sepia-like color (which it also uses for infinite loops, or loops that don’t loop).

 

Break and Continue

 Sometimes, it might be necessary to either stop a loop prematurely—without returning from a method—or skip over an iteration of a loop.

It is for this reason that Java has two special keywords: break (for the former case), and continue (for the latter).

Suppose we want to exit a loop early. The break keyword would be used to do that, like so:

public class BreakExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 10; i++) {

            if (i == 5) {

                break; // Exit the loop when i is 5

            }

            System.out.println("i = " + i);

        }

        System.out.println("Loop ended.");

    }

}

(Never mind that, in this instance, the loop was written very badly—why loop from 1 to 10, if you’re going to break out of the loop and stop it completely, at 5? Poor design as this may be, it serves our purpose of illustrating how break is used.)

This works for any loop—even those for which the index is not exposed (the for-each/enhanced-for loop):

public class BreakForEachExample {

    public static void main(String[] args) {

        String[] laptops = {"Windows", "Samsung", "Apple", "Dell", "Asus"};

 

        for (String laptop : laptops) {

            if (laptop.equals("Apple")) {

                System.out.println("Yes, we want an Apple company laptop");

                break; // Exit the loop when "Apple" is found

            }

        }

    }

}

The “continue” keyword, meanwhile, keeps the loop running, but skips over one particular iteration.

Here, we see continue used in a while loop—just to drive home the point that both these keywords can be used (meaning the same thing), regardless of what particular loop they’re in: continue skips one, break comes out.

public class ContinueWhileExample {

    public static void main(String[] args) {

        int i = 0;

        while (i < 5) {

            i++;

            if (i == 3) {

                continue; // Skip the rest of the loop when i is 3

            }

            System.out.println("i = " + i);

        }

    }

}

Now, that’s all well and good if all we have is one loop to deal with—if that’s true, then the behavior of these breakpoints is straightforward—but what happens if we have nested loops, that is, loops inside loops, inside loops, inside loops…?

This, for example, is a nested loop:

public class NestedLoopExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop for rows

            for (int j = 1; j <= 5; j++) { // Inner loop for columns

                System.out.print("* ");

            }

            System.out.println(); // Move to the next line after each row

        }

    }

}

For each of the 3 rows, the program prints 5 * characters—producing something like

*****
*****
*****

If someone were to break or continue in a situation like this, where there are nested loops—which can be of mixed types (for inside while, while inside do-while, indexed-for inside for-each, while inside for-each, etc.)—break and continue only apply to the innermost loop in which they could:

For example, the following code:

public class NestedLoopBreakExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop

            for (int j = 1; j <= 5; j++) { // Inner loop

                if (j == 3) {

                    break; // Exit the inner loop when j is 3

                }

                System.out.println("i = " + i + ", j = " + j);

            }

        }

    }

}

has this output:

i = 1, j = 1

i = 1, j = 2

i = 2, j = 1

i = 2, j = 2

i = 3, j = 1

i = 3, j = 2

But if we use “continue” in the outer loop, then something like this might happen:

public class OuterContinueExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop

            if (i == 2) {

                continue; // Skip the rest of this outer loop iteration when i is 2

            }

            for (int j = 1; j <= 3; j++) { // Inner loop

                System.out.println("i = " + i + ", j = " + j);

            }

        }

    }

}

i = 1, j = 1

i = 1, j = 2

i = 1, j = 3

i = 3, j = 1

i = 3, j = 2

i = 3, j = 3

Both break and continue are vitally important logical flow controllers—so be sure you understand how each works (and is different from the other!). Don’t just stick to these code examples; write your own, or modify these, and see how the behavior changes as you make changes to your code.

Stacks

 Imagine you’ve just unloaded the dishwasher, and you’ve created a stack of plates. What can you do? You can see what the top plate is, you can add plates to the top, you can count how many plates there are, and you can remove the top plate to get access to plates underneath it.

Java has a data structure that behaves exactly like the stack of plates—the Stack. A stack has several operations like we’ve already seen with other data structures: you can add and you can remove, but, just like we saw with queues, how you do that (where you have access) has special meaning.

As I alluded to last time, looking at queues, some data structures preserve special ordering: the FIFO queue of people at the checkout counter, or the LIFO stack of plates in the cupboard. You can’t see the bottom plate, nor can you add, remove, or check out some random plate in the middle—everything you do must be done to the top visible plate. It's for this reason that a stack is LIFO-- the last thing to be added is the first to come off.

A queue, recall, lets you access only the oldest thing. A stack, by contrast, allows you to access only the newest thing. Think about it - again, with the stack of plates. (Go get a literal stack of plates or maybe books, and put numbers on sticky notes on each plate or book; I promise it’ll help.) When you add to a stack, you can only do so to the top. When you take away from a stack, you can only do so from the top. When you look at a value in a stack, you can only see the top element’s value, not the values of anything under it. 

Stacks call the “add” operation “push,” and the “remove” operation “pop.”  There are certainly problems in which asking if there is anything left in the stack (Think about why? perhaps… because a loop has been running?), so you can do so by calling isEmpty(), which, naturally, returns a Boolean: true if it’s empty, and false otherwise. (This can make working with this call quite annoying, since the resulting Boolean answers “is there nothing?” when the more natural question is probably “is there anything here?”, which is exactly the opposite)

import java.util.Stack;

 

public class StackExample {

    public static void main(String[] args) {

        // Create a stack

        Stack<Integer> stack = new Stack<>();

 

        // Push elements onto the stack

        stack.push(1);

        stack.push(2);

        stack.push(3);

 

        System.out.println("Stack: " + stack);

 

        // Peek at the top element (without removing)

        System.out.println("Top element (peek): " + stack.peek());

 

        // Pop the top element (remove and return)

        int poppedItem = stack.pop();

        System.out.println("Popped element: " + poppedItem);

 

        System.out.println("Stack after pop: " + stack);

    }

}

By now, I’m sure you’ve been working with imports for a while, so seeing that you have to pick it up from java.util should be nothing new. Get in the habit, at least in the beginning of typing out that import yourself, if only so you commit to memory that Stack lives in util. Once you’ve really got stacks down, you can save a second or two by not typing it yourself, writing the rest of your code, and letting the IDE realize for you that you need to put in the import (which the IDE will either do automatically, or which you’ll approve by the click of a button).

Stacks, again, use generics, including the wrapper classes for the primitive types. They’ll be covered in the next post! Stay tuned!

Queues: Just like at the grocery store

 A Queue is another data structure that operates with many similar functions as Lists do, but with a key difference. In a List (as in an array—either with arr[37] or list.get(41) or whatever you want), it’s easy to get to any particular element and do something with it: check its value, change its value, remove it, add it, and so on.

But a queue is different. A queue is, really, just an implementation of “I’m in line at the grocery store to check out, and there’s an order of the people who got here.” Social norms dictate that the cashier only helps the first person in line—the person who has been in line longer than anyone else. They got there because the person ahead of them cleared the queue, and the person before that cleared before them, and the person before that, and so on.

The line only shrinks from the cashier end of the line, and only grows from the back end of the line. The longer you’ve been in line, the sooner you’ll get the cashier’s attention. If you just arrived, you have to wait for everyone ahead of you. Jumping ahead (technically possible with real people) is not allowed with a Queue.

Queues implement the “first-in-first-out” principle, which we call “FIFO” for short. (There is also a “LIFO”—you may have guessed “last-in-first-out”—structure called a Stack. We’ll cover it very soon.)

To add to a queue, you use add(). Queues are like Lists—they take generics, so you make a Queue<Puppy> to store a queue of (only) Puppy objects, or Queue<Student> to store a queue of Student objects. To remove from a queue, you use remove(). Under certain circumstances, you may remove with poll().

You may not want to outright add or remove an element, just look at something—remember, only the front element is visible—and, to do this (again, only for the front element), you can use poll().

Look at this example:

import java.util.Queue;

import java.util.LinkedList;

 

public class QueueExample {

    public static void main(String[] args) {

        // Create a queue using LinkedList

        Queue<Integer> queue = new LinkedList<>();

 

        // Enqueue (add) elements to the queue

        queue.offer(1);  // offer() is preferred for adding elements

        queue.offer(2);

        queue.offer(3);

 

        System.out.println("Queue: " + queue);

 

        // Dequeue (remove) the front element

        int removedItem = queue.poll();

        System.out.println("Removed element: " + removedItem);

 

        System.out.println("Queue after dequeue: " + queue);

    }

}

Adding an element is called “enqueueing,” and removing is also called “dequeueing.” Notice the declaration Queue<Integer> queue = new LinkedList<>();. What does that tell us? Recall from our discussion of inheritance that this is valid, if and only if (and this is true), a Queue is implemented as a LinkedList, since every Queue is a LinkedList, but not every LinkedList is a Queue.

On account of this, the element indexed 0—the “first” element—is the element at the head of the queue, or, the next one to be processed (the person being checked out by the cashier in our earlier story). The highest index in the queue, therefore, lies at the opposite end, at the tail of the queue.

This queue we have shown here is the simplest kind of queue. Later, we’ll get to a more specialized queue called a priority queue. Priority queues aren’t that much different, so don’t be too scared; in essence, they keep elements in the proper order, by some priority (“keep the seniors above the juniors above the sophomores above the freshmen”; or “keep the oldest people at the back of the queue.”)

The general queue imposes no such restriction, and you’re free to enqueue and dequeue as much as you want—add 3 things, remove 1, add 57, remove 48, add 1, take away 2, and so on—without messing with order.

Play around with building your own queue of an object of your choice (or the wrapper classes of primitives like Integer for integers), and have fun enqueueing and dequeing. 

LinkedLists and ArrayLists

 The first data structure we’ll look at is the List. List is an interface in Java, so there are many implementations. We will focus on the two most commonly used, the ArrayList and the LinkedList.

An ArrayList can be thought of, essentially, as a self-resizing array. Regular arrays are declared with the type of thing they’ll hold and how many they can hold. ArrayList declarations look a little different:

List<Integer> myList = new ArrayList();

Remember from our discussion of inheritance a few posts ago how this works, even if the class names aren’t the same. Every ArrayList is a List, so this declaration is fine. (We would run into trouble if List and ArrayList were reversed, since not every List is an ArrayList.) The use of “Integer” here is both a generic and a wrapper class. For now, I’ll be handwavy about this and say that, to create a list of integers, you use these and not the int primitive type, but I promise I’ll address this very soon and link back to the explanation as soon as it is posted.

Imagine a real list you’re making when you go shopping. There are certain things you might want to do:

• Add or remove an item from the beginning
• Add or remove an item from somewhere in the middle
• Add or remove an item from the end
• Figure out how many items you have
• Figure out if you have any items at all
• Find out what the item at some position is

These are all things you can do thanks to the way List is implemented.

There are methods to add(), remove(), and get(). Now, contrary to arrays—of the int[] myArray = new int[20]; variety—the way to access the number of things in a List is not with length (which is a property, so it really is length, and not length()), is actually with the method call to size(). This, again, unlike arrays, is an actual method call, so don’t forget the parentheses! Lists start counting from index 0, just like arrays.

ArrayLists essentially hide from you the process of copying arrays and adding in items whenever you exceed the maximum allocated space. LinkedLists, however, are a little different. Whereas arrays took some fixed chunk of memory (let’s say, 80 bytes to store 20 integers at 4 bytes each) and found a chunk of unused memory of that size, all in sequence, LinkedLists don’t care about that consecutive memory constraint.
There are generally two types of LinkedLists: singly-linked, and doubly-linked. Your browser is probably implementing a doubly-linked list, since you can go backward in a tab and you can go forward: there are links to the previous thing, and to the next thing, as opposed to links in only one direction.

Typically, you’ll probably see LinkedLists made of Nodes (again, with those angle-brackets we’ll discuss very shortly), looking something like this:

// Node class

class Node<T> {

    T data;

    Node<T> next;

 

    Node(T data) {

        this.data = data;

        this.next = null;

    }

}

 

// LinkedList class

class LinkedList<T> {

    Node<T> head;

 

    // Add a new node at the end

    void add(T data) {

        Node<T> newNode = new Node<>(data);

        if (head == null) {

            head = newNode;

        } else {

            Node<T> current = head;

            while (current.next != null) {

                current = current.next;

            }

            current.next = newNode;

        }

    }

 

    // Print all nodes

    void printList() {

        Node<T> current = head;

        while (current != null) {

            System.out.print(current.data + " ");

            current = current.next;

        }

        System.out.println();

    }

}

 

// Example usage

public class Main {

    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();

        list.add(1);

        list.add(2);

        list.add(3);

 

        list.printList(); // Output: 1 2 3

    }

}

 
A “Node” object has two things in it: a piece of data of type T, and a pointer to the next node in the list. It does not matter where in memory that is, and, say, the item at index 3 need not be earlier in memory than the item at index 327. As long as there’s a pointer from 3 to 4 to 5 to 6… to 325 to 326 to 327—as long as you can follow the trail of breadcrumbs left by those “next” Node objects—you can find your way around a list. (If the list were doubly-linked, you would have your payload, plus links to both “next” and “prev” Nodes.)

Intro to Interfaces and More Advanced Data Structures

 We are almost ready to take a deep dive into some more data structures—so far we have seen an array—but before we do, we need to talk about what an interface is in Java. The way the common person uses “interface” when dealing with computers, what is typically meant is the GUI, or the “graphical user interface.” These are all the displays, and buttons and arrows, and icons you click on, scroll through, and interact with to do things with a computer. There is a command much lower level than the typical user (that is, closer to the CPU) that starts a browser window, but you don’t need to know it; double-clicking on the browser icon gets interpreted as “the user wants to run the command to start the browser” because that information gets passed through the GUI down the right channels.

Every class we have written or used so far has been “concrete.” In Java, the opposite of this is “abstract,” which is a reserved word (“concrete” is not). When a class is abstract—Puppy, for example—you cannot create any Puppy objects. These classes can have methods that have no bodies, which are called abstract methods (declared, as with the classes, with the keyword “abstract”, as in public abstract class Puppy, and so on). Abstract methods have signatures that include “abstract” in the position after the access modifier, and they end with a semicolon. They include no implementation.

Abstract classes, on their own, are useless. They need other classes to extend them. Those that do must implement the abstract methods in the abstract class they extend. Not every method in an abstract class must be abstract; abstract classes, therefore, can have some concrete methods, which are implemented normally as we have always done. 

Interfaces, on the other hand, are (by default) entirely abstract contracts to implement certain methods to create some object. There is a key difference between interfaces and abstract classes, beyond the fact that everything is abstract in one but not necessarily in the other: while you can only extend (inherit from) one class, you can implement as many interfaces as you would like. Simply comma-separate the interfaces, like so:

public class MyClass implements InterfaceA, InterfaceB {

    @Override

    public void methodA() {

        // Implementation for InterfaceA's method

    }

    @Override

    public void methodB() {

        // Implementation for InterfaceB's method

    }

}

By doing this, whoever wrote the code is committing to implement all the methods in InterfaceA and InterfaceB. I don’t particularly need to know or care what they are—I just know that’s true, since that’s the contract you make when you declare you’re implementing an interface. 

Some of the most important ones you’ll use—which are all data structures—are the following:

• List
• Queue
• Map 

This is the order in which we’ll go through these fundamental data structures—and then we’ll go through the Stack class (which is concrete) for a fourth critical data structure.

Factorials

 Let me return now to the basics of recursion to bring up another simple, classic problem: the calculation of the factorial. You may have heard some urban legend about Gauss, who was in class, and someone misbehaved, so the teacher said “You can’t go to recess until you find the sum of 1+2+3+…+100,” thinking this would keep the students busy a long while.

Gauss, the legendary mathematician he was, found the answer in seconds: 1+100 is a pari that sums to 101; and so is 2+99; and so is 3+98; and so is 4+97; and so on. We’re going from 1 to 100, so we have 100/2 = 50 pairs. The sum of the pair is 101, and we have 50 pairs, so the sum of 1+2+3+…+100 is 50*101 = 5050. (And indeed this generalizes for any upper bound: for some bound n, the sum ofthe first n numbers is n*(n+1)/2.)

That sequence grows quickly—1, 3, 6, 10, 15, 21, 28, and so on. But we are after a sequence that grows much, much more quickly.

In fact, let’s call the additive version of 1[operator]2[operator]3[operator]4… Gauss(n). Now let’s look at what happens when the operation is not addition, but multiplication: 1, 2, 6, 4, 120, 720, … etc. For now, let’s call this Mystery(n). It has a proper name and a real definition, but let’s just keep it vague for now as we appreciate how insanely quickly this number is growing.

 I claim—and by the end of this article, you’ll be able to prove me right—that Gauss(10) is 55, but Mystery(10) is more than 3 million; Gauss(20) is 210, but Mystery(20) is 2.4 billion billion. Put another way, Mystery() grows much, much faster than Gauss(). No, that isn’t a typo: Mystery(20) is somewhere in the ballpark of 2,400,000,000,000,000,000.  You can count to Gauss(20) in about 3 and a half minutes, at one number per second. You would need about 6 times the age of the universe to count to Mystery(20) at one number per second.

Mystery(), in fact, is the factorial function—what you get when you replace every + in the Gauss sequence with a *.

Imagine you’re a teacher, and you want to line up your students. You have Alice, Bob, and Charlie in your class. How many ways are there to arrange them?

Alice can come first. Then either Bob or Charlie. Then whoever wasn’t second must come third.

Bob can come first. Alice or Charlie can follow. Whoever wasn’t picked completes the triple.

Charlie can lead. Alice or Bob can be next. Whoever is left necessarily must come here.

Expressed as a set, we have ABC, ACB, BAC, BCA, CAB, CBA: six choices.

Now, let’s remove Charlie. {Alice, Bob} is possible; and so is {Bob, Alice}.

Now, let’s remove Bob. {Alice} is the only ordering.

Now, let’s do something strange: remove Alice. {} is the only ordering.

We can express this function in one of two ways: in a loop, like what the students might have done if the punishment problem had been to multiply: 1*2, 1*2*3, 1*2*3*4, and so on…

and the pseudocode looks like:

FUNCTION factorial(n)

    result ← 1

    FOR i FROM 2 TO n

        result ← result * i

    END FOR

    RETURN result

END FUNCTION

This correctly computes the value, but there’s a better, more classic, more elegant way.

Notice that 6! (“six factorial,” not “SIX!!!!!!!!”) is 6 times 5!; 5! Is 5 * 4!; and so on.

This allows us to very neatly, recursively define factorial().

 

Recall from our student-ordering experiment that, after we get rid of Alice, there is still one way to put no students in order: {}. Do nothing. That actually matters here because it gives us a defined value at 0.

Factorials are used to count the number of ways to arrange some number of objects, so, naturally, there is one way to arrange 0 objects: do nothing. That is one intuitive way to get to the fact that 0! Is 1, but we’ll see another by the end of this article.

To define something recursively, we need a base case—we have it, that 0!=1—and a rule, that the factorial of some number is the factorial of the previous number, times the number (5! = 5 * 4!; 100!  = 100 * 99!; and so on).

Armed with these two pieces of information, we can arrive at the following recursive definition:

FUNCTION factorial(n)

    IF n = 0 OR n = 1 THEN

        RETURN 1

    ELSE

        RETURN n × factorial(n - 1)

    END IF

END FUNCTION


The other way to get to the fact that 0! Is 1 is the following:

·       10! is 3628800

·       9!  Is 10!/10, or 362880

·       8! Is 9!/9, or 40320

·       7! Is 8!/8, or 5040

·       6! Is 7!/7, or 720

·       5! Is 6!/6, or 120

·       4! Is 5!/5, or 24

·       3! Is 4!/4, or 6

·       2! Is 3!/3, or 2

·       1! Is 2!/2, or 1—and up to this point, there should be no argument, since I am just applying the pattern that n! = n * (n-1)! In reverse

·       So naturally, 0! Is 1!/1, which is 1.