Notes on 📕Data Structures & Abstractions with Java by Frank M. Carrano

I use these notes to track thoughts I had, and things I found interesting, while reading Data Structures & Abstractions with Java

The notes are still in progress as I have not yet finished reading the book

Introduction

Abstract data types and data structures are contrasted in Wikipedia as as “an abstract data type (ADT) is a mathematical model for data types, defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user” and as “Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type”

1. Bags

A data type is defined in Wikipedia as “a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these values as machine types”
According to the Java documentation, “You cannot declare more than one method with the same name and the same number and type of arguments, because the compiler cannot tell them apart”
The book recommends writing code that uses and tests the interface before attempting to implement the interface
Encapsulation is definied in Wikipedia as “the bundling of data with the mechanisms or methods that operate on the data”
The book recommends designing an abstract data type by only worrying about how the user will use it, and not about the implementation. There can be a tendency to let the underlying algorithms influence the interface, but this recommendation would resist that

2. Bag Implementations That Uses Arrays

The final keyword in Java on a field ensures that the field cannot be changed after its initial assignment (though the contents of the field can change)
There are three ways (at least) to shallow copy arrays: Object.clone, System.arraycopy, and Arrays.copyOf. The latter two methods are useful for resizing arrays
This book has a style where they set a result in various branches and then return the result at the end of the method when all the branches have come back together, instead of returning early when and if necessary. I find the latter style easier to understand
The use of .equals as an equivalence relation has issues with nulls
The reason doubling is used in array resizing is it lets the adds have an amortized O(1) running time (each add banks a constant amount of time for copying during a resize)

3. A Bag Implementation That Links Data

Inner / nested class is defined in Wikipedia as “a class declared entirely within the body of another class or interface”
The book defines a nontraditional list remove method: it replaces the to-be-removed node’s data with the first node’s data, then pops the first node
The book defines a list clear method as continually popping from the list, with O(n) running time. But it seems simpler to set the head reference to null and let the garbage collector do the work
The Java documentation states “If a class has no modifier (the default, also known as package-private), it is visible only within its own package”, which the book points out is an alternative to inner classes
The Java documentation describes List implementations as follows: “ArrayList - Resizable array implementation of the List interface (an unsynchronized Vector). The best all-around implementation of the List interface. LinkedList - Doubly-linked list implementation of the List interface. Provides better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list”

4. The Efficiency of Algorithms

Complexity is defined in Wikipedia as “amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements”
Analysis of algorithms is defined in Wikipedia as “the process of finding the computational complexity of algorithms”
Big O notation is defined by Wikipedia as “mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity”

5. Stacks

The book points out that pushing items onto, and then popping all items from a stack, reverses the order
The book points out that infix operators require precedence and parentheses to process as expected, but prefix and postfix bake the precedence into the expression 1+2*4 vs. 1 2 4 * +`
Shunting yard algorithm is defined in Wikipedia as “method for parsing arithmetical or logical expressions, or a combination of both, specified in infix notation… The input is processed one symbol at a time: if a variable or number is found, it is copied directly to the output… If the symbol is an operator, it is pushed onto the operator stack… If the operator’s precedence is lower than that of the operators at the top of the stack or the precedences are equal and the operator is left associative, then that operator is popped off the stack and added to the output… Finally, any remaining operators are popped off the stack and added to the output”
The book explains that instead of outputting the result of the shunting yard algorithm as a postfix expression, you can evaluate it on the fly by using an operand stack
Frame is defined in the Java documentation as “used to store data and partial results, as well as to perform dynamic linking, return values for methods, and dispatch exceptions”
Java Virtual Machine stack is defined in the Java documentation as “stores frames… it holds local variables and partial results, and plays a part in method invocation and return. Because the Java Virtual Machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated. The memory for a Java Virtual Machine stack does not need to be contiguous”
java.util.ArrayDeque<E> is defined by the Java documentation as “efficient, resizable array implementation of the Deque interface”

6. Stack Implementations

Stacks using linked lists are described in Wikipedia as “Another option for implementing stacks is to use a singly linked list. A stack is then a pointer to the “head” of the list, with perhaps a counter to keep track of the size of the list…Pushing and popping items happens at the head of the list”
Stacks using arrays are described in Wikipedia as “The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted…. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O(1) time”
java.util.Arrays.copyof is described in the Java documentation as “Copies the specified array, truncating or padding with nulls (if necessary) so the copy has the specified length”
The book makes sure to set the stack array to null upon pop or clear, so that garbage collection can kick in
The book uses a Vector, but the current version is java.util.ArrayList which is described in the Java documentation as “Resizable-array implementation of the List interface…. The size, isEmpty, get, set, getFirst, getLast, removeLast, iterator, listIterator, and reversed operations run in constant time. The add, and addLast operations runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations [e.g. addFirst] run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation”
The book advises that a stack should not inherit from a vector because a stack has-a vector, not is-a vector
Is-a is defined in Wikipedia as “subsumptive relationship between abstractions (e.g., types, classes), wherein one class A is a subclass of another class B (and so B is a superclass of A). In other words, type A is a subtype of type B when A’s specification implies B’s specification. That is, any object (or class) that satisfies A’s specification also satisfies B’s specification, because B’s specification is weaker”
Has-a is defined in Wikipedia as “composition relationship where one object (often called the constituted object, or part/constituent/member object) ‘belongs to’ (is part or member of) another object (called the composite type), and behaves according to the rules of ownership. In simple words, has-a relationship in an object is called a member field of an object”

7. Recursion

Recursion is defined in Wikipedia as “method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem…. Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for certain problems, algorithmic or compiler-optimization techniques such as tail call optimization may improve computational performance over a naive recursive implementation…. A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself)… Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit call stack, while iteration can be replaced with tail recursion”
Frame is defined in the Java documentation as “used to store data and partial results, as well as to perform dynamic linking, return values for methods, and dispatch exceptions. A new frame is created each time a method is invoked. A frame is destroyed when its method invocation completes, whether that completion is normal or abrupt (it throws an uncaught exception). Frames are allocated from the Java Virtual Machine stack…”
The book points out that some problems, like traversing a linked list in reverse order, are expressed more naturally with recursion than iteration
The book points out that recursive methods are often private because their signature often reveals information about the implementation of the class. As such, they are called by more general public method
Recurrence relation is defined in Wikipedia as “equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms”
Proof by induction is defined in Wikipedia as “consists of two cases. The first, the base case, proves the statement for n=0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n=k, then it must also hold for the next case n=k+1…. The method can be extended to prove statements about more general well-founded structures, such as trees” Tail call is defined in Wikipedia as “a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive…. Tail calls can be implemented without adding a new stack frame to the call stack…. Tail recursion can be related to the while statement, an explicit iteration”
The book points out that Java does not implement tail call optimization. I believe one reason is that the Java security mechanism does stack inspection
The book presents a partially iterative version of towers of hanoi, but it’s hard to understand so it’s clear why the recursive version is preferred
Indirect recursion is defined in Wikipedia as “function is called not by itself but by another function that it called (either directly or indirectly)… Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion”. This is different from the book, which regards mutual recursion as a special case of indirect recursion
The book points out that to convert a recursive function to an iterative one with an explicit stack, you should push the first recursive call onto the stack, and then set up a while loop that pops a recursive call off the stack and processes it. The processing can push new recursive calls onto the stack as necessary. The book points out that the resulting code is often not that clean.

8. An Introduction to Sorting

Comparable<T> is defined in the Java documentation as “This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class’s natural ordering, and the class’s compareTo method is referred to as its natural comparison method. Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort)”
Lower bounded wildcards with Comparable are discussed in the Java documentation: “It isn’t necessary that T be comparable to exactly itself. All that’s required is that T be comparable to one of its supertypes… This reasoning applies to almost any usage of Comparable that is intended to work for arbitrary types: You always want to use Comparable<? super T>. In general, if you have an API that only uses a type parameter T as an argument, its uses should take advantage of lower bounded wildcards (? super T). Conversely, if the API only returns T, you’ll give your clients more flexibility by using upper bounded wildcards (? extends T)”
Selection sort is defined in Wikipedia as “in-place comparison sorting algorithm. It has a O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort…. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right”. It’s not stable due to the swaps
Insertion sort is defined in Wikipedia as “Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position…. typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position…. While some divide-and-conquer algorithms such as quicksort and mergesort outperform insertion sort for larger arrays, non-recursive sorting algorithms such as insertion sort or selection sort are generally faster for very small arrays (the exact size varies by environment and implementation, but is typically between 7 and 50 elements). Therefore, a useful optimization in the implementation of those algorithms is a hybrid approach, using the simpler algorithm when the array has been divided to a small size…. If a more sophisticated data structure (e.g., heap or binary tree) is used, the time required for searching and insertion can be reduced significantly; this is the essence of heap sort and binary tree sort”
The book points out that insertion sort on linked lists is unlike arrays, instead you make a new linked list with the head of the old linked list, then repeatedly step through the old linked list and add each node to the new linked list in the correct position
Shellsort is defined in Wikipedia as “can be understood as…a generalization of…sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange…. effectively finishing with an ordinary insertion sort”

9. Faster Sorting Methods

Merge sort is defined in Wikipedia as “Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list”
Divide-and-conquer algorithm is defined in Wikipedia as “recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem”
Bottom-up implementation is defined in Wikipedia as “treats the list as an array of n sublists (called runs in this example) of size 1, and iteratively merges sub-lists back and forth between two buffers”
java.util.Arrays.sort for reference types is described in the Java documentation as “stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays… The implementation was adapted from Tim Peters’s list sort for Python (TimSort)”
java.util.Arrays.parallelsort for reference types is described in the Java documentation as “The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method… The algorithm requires a working space no greater than the size of the original array”
Stable sort algorithm is defined in Wikipedia as “sort equal elements in the same order that they appear in the input”
Quicksort is defined in Wikipedia as “selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot… The sub-arrays are then sorted recursively”
The book points out that elements equal to the pivot can be put in either partition because doing otherwise might tilt the partition
The book presents a variant of the Hoare partition scheme which is defined in Wikipedia as “uses two pointers (indices into the range) that start at both ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot at the first pointer, and one less than the pivot at the second pointer; if at this point the first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged. After this the pointers are moved inwards, and the search for an inversion is repeated; when eventually the pointers cross (the first points after the second), no exchange is performed; a valid partition is found, with the point of division between the crossed pointers (any entries that might be strictly between the crossed pointers are equal to the pivot and can be excluded from both sub-ranges formed)”
Median-of-three pivot is described in Wikipedia as “choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick). This “median-of-three” rule counters the case of sorted (or reverse-sorted) input, and gives a better estimate of the optimal pivot (the true median) than selecting any single element, when no information about the ordering of the input is known”
java.util.Arrays.sort and .parallelsort for primitive types are described in the Java documentation as “Dual-Pivot Quicksort… This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations”
Radix sort is defined in Wikipedia as “avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered”. The book presents an implemenentation with a queue for each bucket
The book recommends insertion sort for small and almost-sorted arrays, quick sort for typical arrays, and merge sort for arrays too large to fit in memory

10. Queues, Dequeues & Priority Queues

Queue is defined in Wikipedia as “collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence”
Poisson distribution is defined in Wikipedia as “discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time if these events occur with a known constant mean rate and independently of the time since the last event
Double-ended queue / deque is defined in Wikipedia as “generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail)”. The book points out that a deque is a queue and a stack
I always want to prounounce deque as “deke” and have to force myself to pronounce it as “deck”
Queues are described in the Java documentation as “ArrayDeque - Efficient, resizable array implementation of the Deque interface. LinkedList - Doubly-linked list implementation of the List interface. Provides better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list. Also implements the Deque interface. When accessed through the Queue interface, LinkedList acts as a FIFO queue”
The book contains a good diagram about how the stack, queue, and deque operations relate to each other
The Java documentation has a summary of Deque methods. You can see that queue operations enqueue to the tail of the deque, and dequeue from the head, while stack operations push to and pop from the head of the deque. Neither queue nor stack operations get or remove from the tail of the deque–that is a deque-specific operation.

	First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

Queue Method	Equivalent Deque Method
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

Stack Method	Equivalent Deque Method
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

The book presents a fun example of typing and pressing backspace as an example of where you need a deque, because you are adding characters to the tail, but also removing them from the tail when backspacing, then reading them from the head at the end
Priority queue is defined in Wikipedia as “each element has an associated priority, which determines its order of service…serves highest priority items first”
java.util.PriorityQueue<E> is described in the Java documentation as “The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used…. The head of this queue is the least element with respect to the specified ordering”
The book says that the elements of PriorityQueue must be Comparable, but I’m not sure that is true, you can pass in a Comparator to the constructor

11. Queue, Deque & Priority Queue Implementations

The book points out that the general idea of queue implementations is to dequeue from the front, and enqueue to the back.
The book points out that the easiest location to remove from a singly linked list is the head–adding to a singly linked list is easy at either the front or back
java.util.LinkedList is described in the Java documentation as “Doubly-linked list implementation of the List and Deque interfaces…. All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index”
java.util.ArrayDeque is described in the Java documentation as “Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage… This class is likely to be faster than…LinkedList when used as a queue. Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time”
System.arraycopy is described in the Java documentation as “Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array”
The book presents a fun implementation of a queue using a circularly linked list with a single point to the tail (you can get the head by stepping forward from the tail). Sometimes using circularly linked list allows simpler code without much of the null checking that non-circularly linked lists require
When writing linked list implementations, it’s sometimes less confusing to write the null and normal cases separately, then combine/optimize them afterwards