Data Structures

Language Constructs #

Types #

In Java, there are two kinds of types: primitive types and reference types. Primitive types are lowercase, and we named the ones that we care about in Part A: boolean, int, char, double. Pretty much every other type is a reference type, such as String. If a type starts with a capital letter, it is likely a reference type.

You will learn more about the distinction between primitive and reference types in Lecture 4, but for this homework, you will need to know that each primitive has a corresponding reference type (Boolean, Integer, Character, Double). If you are using “generics” to declare a data structure, you must use the reference type. You can seamlessly convert between a primitive type and its reference type.

null #

Java also has null, which is the approximate equivalent of None in Python. Any reference type can be assigned a value of null. If we try to access an instance member or call an instance method from a value of null, we will see an error called a NullPointerException.

Arrays (fixed-size) #

Java arrays are a lot like Python lists. However, Java arrays are fixed-size, so we can’t add or remove elements (that is, no append, remove, etc.).

Python Java
zeroedLst = [0, 0, 0]
lst = [4, 7, 10]
lst[0] = 5
int[] zeroedArray = new int[3];
int[] array = {4, 7, 10};
array[0] = 5;
  • In new int[3], the int is the type in the array; and 3 is the length. With this syntax, all elements take on their “default value”. For int, this is 0.
  • Arrays do not print nicely, for reasons beyond the scope of HW 0. To print an array, you can call Arrays.toString(array).
  • Arrays do not have a length method. It is an instance variable, so it does not have parentheses.
  • Java does not support negative indexing or slicing.

Foreach Loop #

Python Java
lst = [1, 2, 3]
for i in lst:

int[] array = {1, 2, 3};
for (int i : array) {
  • Notice the type declaration of the iterating variable, as well as the usage of : instead of in.
  • We can also use this syntax on certain other types, such as Lists and Sets.

Lists (resizable) #

Python Java
lst = []
lst[0] = "zed"
if "one" in lst:
    print("one in lst")

for elem in lst:

List<String> lst = new ArrayList<>();
lst.set(0, "zed");
if (lst.contains("one")) {
    System.out.println("one in lst");
for (String elem : lst) {
  • Java has the List interface. We largely use the ArrayList implementation.
  • The List interface is parameterized by the type it holds, using the angle brackets < and >.
  • Lists, again, do not support slicing or negative indexing.

Sets #

Python Java
s = set()
if 1 in s:
    print("1 in s")

for elem in s:

Set<Integer> set = new HashSet<>();
if (set.contains(1)) {
    System.out.println("1 in set");
for (int elem : set) {
  • Java has the Set interface. There are two main implementations: TreeSet, and HashSet. TreeSet keeps its elements in “sorted” order, and is “fast.” In contrast, HashSet does not have a defined “order”, but is (usually) really “fast.”
  • A Set canot contain duplicate items. If we try to add a duplicate item, it simply does nothing.

Dictionaries / Maps #

Python Java
d = {}
d["hello"] = "hi"
d["hello"] = "goodbye"
if "hello" in d:
    print("\"hello\" in d")

for key in d.keys():

Map<String, String> map = new HashMap<>();
map.put("hello", "hi");
map.put("hello", "goodbye");
if (map.containsKey("hello")) {
    System.out.println("\"hello\" in map");
for (String key : map.keySet()) {
  • Java has the Map interface. There are two main implementations: TreeMap, and HashMap. Similarly to sets, TreeMap keeps its keys sorted and is fast; HashMap has no defined order and is (usually) really fast.
  • In the angled brackets, we have the “key type” first, followed by the “value type”.
  • Maps cannot directly be used with the : for loop. Typically, we call keySet to iterate over a set of the keys.

Classes #

Python Java
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distanceTo(self, other):
        return math.sqrt(
            (self.x - other.x) ** 2 +
            (self.y - other.y) ** 2

    def translate(self, dx, dy):
        self.x += dx
        self.y += dy
public class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    public Point() {
        this(0, 0);
    public double distanceTo(Point other) {
        return Math.sqrt(
            Math.pow(this.x - other.x, 2) +
            Math.pow(this.y - other.y, 2)
    public void translate(int dx, int dy) {
        this.x += dx;
        this.y += dy;

We can use these classes as follows:

Python Java
p1 = Point(5, 9)
p2 = Point(-3, 3)
print(f"Point 1: ({p1.x}, {p1.y})")
print("Distance:", p1.distanceTo(p2))
p1.translate(2, 2)
print(f"Point 1: ({p1.x}, {p1.y})")
Point p1 = new Point(5, 9);
Point p2 = new Point(-3, 3);
System.out.println("Point 1: ( " + p1.x
    + ", " + p1.y + ")");
System.out.println("Distance: "
    + p1.distanceTo(p2));
p1.translate(2, 2);
System.out.println("Point 1: ( " + p1.x
    + ", " + p1.y + ")");

Programs #

Let’s look at some Java programs that use data structures and classes. Here are some simple ones that you might find yourself referring to if you forget how to do something.

Index of Minimum of a List of Numbers #

Python Java
def min_index(numbers):
    # Assume len(numbers) >= 1
    m = numbers[0]
    idx = 0
    for i in range(len(numbers)):
        if numbers[i] < m:
            m = numbers[i]
            idx = i
    return idx
public static int minIndex(int[] numbers) {
    // Assume numbers.length >= 1
    int m = numbers[0];
    int idx = 0;
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] < m) {
            m = numbers[i];
            idx = i;
    return idx;

Exceptions #

Lastly, let’s look at how we can throw exceptions in Java compared to Python with previous example.

def minIndex(numbers):
    if len(numbers) == 0:
        raise Exception("There are no elements in the list!")
    m = numbers[0]
    idx = 0


    return m
public static int minIndex(int[] numbers) {
    if (numbers.length == 0) {
        throw new Exception("There are no elements in the array!");
    int m = numbers[0];
    int idx = 0;


    return m;
Last built: 2023-12-02 09:53 UTC