CS Notes

16 Java Built-in Lists, LinkedList, ArrayList, Wrapper Classes, Inheritance Basics

Jan 17, 202510 min read

Lecture from: 15.11.2024 | Video: Videos ETHZ

Java’s Built-in Lists: java.util.LinkedList and java.util.ArrayList

Recall from last time…

Java provides implementations of common data structures in the java.util package.

1. java.util.LinkedList

  • Doubly Linked List: Java’s LinkedList is a doubly linked list, meaning each node has references to both the next and the previous node. This allows for efficient traversal in both directions.
  • Methods: Offers methods like addFirst(), addLast(), removeFirst(), removeLast(), getFirst(), getLast(), etc.

Example Usage:

import java.util.LinkedList;
 
LinkedList<String> names = new LinkedList<>(); // Note the use of generics (more later)
names.addFirst("Ann");
names.addFirst("Ben"); // Ben is now at the front
names.addLast("Clara");
// ... other operations ...

2. java.util.ArrayList

  • Dynamic Array: ArrayList uses a dynamic array (a resizable array) internally. It provides fast random access (accessing elements by index) but can be less efficient for insertions or deletions, especially at the beginning of the list.

Example Usage:

import java.util.ArrayList;
 
ArrayList<String> names = new ArrayList<>();
names.add("Ann");
names.add("Ben");
// ... other operations ...

Java Collections Framework

The java.util.Collections class provides utility methods for working with collections (including lists), like sorting, searching, finding min/max, etc. We will learn more about generics and collections in a later lecture.

Wrapper Classes

Java collections (like LinkedList and ArrayList) can only store objects, not primitive types (like int, double, boolean). To store primitive types in collections, we use wrapper classes.

  • Wrapper Classes: Each primitive type has a corresponding wrapper class: Integer for int, Double for double, Boolean for boolean, etc. These wrapper classes are part of the java.lang package.

Boxing and Unboxing

  • Boxing: Converting a primitive value to its corresponding wrapper object.
  • Unboxing: Converting a wrapper object back to its primitive value.

Example:

Integer x = 3;       // Boxing (implicit in this case, with Autoboxing)
int y = x + 1;     // Unboxing (also implicit, with Auto(un)boxing)
Integer z = Integer.valueOf(5); // Explicit boxing (less common now with Autoboxing)
int w = z.intValue();   // Explicit unboxing (also less common)

Autoboxing and Auto-unboxing

Java automatically performs boxing and unboxing in many situations, which simplifies the code.

Example:

ArrayList<Integer> data = new ArrayList<>();
data.add(10); // Autoboxing: int 10 is automatically boxed to Integer
int first = data.get(0); // Auto-unboxing: Integer is converted back to int

Important Note: No Implicit Type Conversions with Wrapper Classes

Autoboxing and unboxing only work between a primitive type and its corresponding wrapper class. There are no implicit type conversions between different wrapper classes (or from one wrapper class to the primitive type of another.) For example:

Integer i = 1;
Double d = 3.0;
Double e = i; // Compiler error! 
// No implicit conversion from Integer to Double. 
// You need an explicit cast like:  Double e = Double.valueOf(i);

Inheritance in Java

Inheritance is a powerful mechanism in object-oriented programming that allows you to create new classes (subclasses or derived classes) based on existing classes (superclasses or base classes). The subclass inherits the attributes and methods of the superclass, promoting code reuse and establishing a hierarchical relationship between classes. This “is-a” relationship is fundamental to inheritance. A subclass is a specialized type of its superclass.

Motivating Example: FastLinkedList

Imagine we want to create a FastLinkedList that improves upon our previous LinkedList by adding a direct reference to the last element (back). This avoids traversing the whole list when adding elements to the end. Instead of rewriting all the LinkedList code, we can use inheritance to reuse the existing functionality and extend it with the new back reference.

Problem: Adding to the end of a regular linked list is inefficient because it requires traversing the entire list to find the last node.

Solution: FastLinkedList will inherit from LinkedList and add a back pointer for direct access to the last element.

The Power of Inheritance: Inheritance enables code reuse. We don’t have to copy and paste the LinkedList code; we inherit it and add the specific enhancements needed for FastLinkedList.

Motivation: Input Streams in Java

Another motivational example is how Java handles input streams. Different sources of input (keyboard, file, microphone) require different handling. However, they share common functionalities (reading data). Java uses inheritance to create a hierarchy of input stream classes:

  • InputStream (abstract base class): Defines the common interface for reading data.
  • FileInputStream, AudioInputStream, etc. (subclasses): Implement the specifics for reading from files, audio sources, etc.

This allows you to write code that works with any input stream, regardless of the specific source, thanks to polymorphism (we’ll get to this later).

void readData(InputStream source) { // Can handle any type of InputStream
    // ... code to read data ...
}
 
// Usage examples:
InputStream console = System.in;     //Standard input
InputStream file = new FileInputStream("my_file.txt");
InputStream audio = new AudioInputStream(...); // Some audio source
 
readData(console); // all work polymorphically
readData(file);
readData(audio);

This demonstrates the flexibility and code reuse enabled by inheritance and polymorphism. The readData method can handle various input types without modification because they all inherit from InputStream.

Basic Syntax and Concepts

In Java, inheritance is implemented using the extends keyword.

class Subclass extends Superclass {
    // Subclass members (attributes and methods)
}
  • extends Keyword: Indicates that Subclass inherits from Superclass.
  • Inheritance and “is-a” Relationship: Subclass is a specialized type of Superclass.
  • Inherited Members: Subclass automatically inherits all the non-private members (attributes and methods) of Superclass.
  • Adding New Members: Subclass can add its own unique attributes and methods.
  • Code Reuse: Inheritance promotes code reuse by avoiding code duplication.

Classic Example: Dog and Cat

Let’s illustrate with the classic “Animal, Dog, Cat” example.

public class Animal {
    public String name;
    public int age;
 
    public void eat() { System.out.println("Yummy!"); }
    public void sleep() { System.out.println("Zzzzz!"); }
}
 
public class Dog extends Animal {
    public void bark() { System.out.println("Woof!"); }
}
 
public class Cat extends Animal {
    public void meow() { System.out.println("Meow!"); }
}
  • Dog and Cat inherit name, age, eat(), and sleep() from Animal.
  • Dog adds bark(), and Cat adds meow().

This structure avoids redundant code (defining name, age, eat(), and sleep() in both Dog and Cat).

Inheritance Hierarchies and Chains

  • Inheritance Hierarchy: A tree-like structure formed by classes and their subclasses. The root of the hierarchy is usually a general class (like Animal), and subclasses become more specialized as you go down the tree. Java supports single inheritance: a class can only directly inherit from one superclass. However, you can create inheritance chains:
     Animal
       /  \
    Dog   Cat
      |
    Husky

In this example, Husky inherits from Dog, which inherits from Animal. So, Husky implicitly inherits from Animal as well.

  • Terminology:
    • The inheriting classes (e.g., Dog, Cat, Husky) are called subclasses or subtypes.
    • The classes being inherited from (e.g., Animal, Dog) are superclasses or supertypes.

Overriding Methods

  • Overriding: A subclass can override (redefine) an inherited method to provide a specialized implementation. The overriding method in the subclass must have the same signature (method name, parameters, and return type) as the method in the superclass.
  • @Override Annotation: (Optional, but recommended.) Indicates that a method is intended to override a superclass method. It helps catch errors if the signature doesn’t match. (More here: https://stackoverflow.com/questions/94361/when-do-you-use-javas-override-annotation-and-why)

Example:

public class Cat extends Animal {
    @Override
    public void eat() { System.out.println("Tuna, yay!"); }
}
 
public class Dog extends Animal {
	// Dog overrides eat() as well.
	@Override
	public void eat() { System.out.println("Sausage!!"); } 
 
}
 
Animal a = new Animal();
Cat c = new Cat();
Dog d = new Dog();
 
a.eat(); // Output: Yummy!
c.eat(); // Output: Tuna, yay!
d.eat(); // Output: Sausage!!

When eat() is called on a Cat object, the overridden version in Cat is executed. When called on an Animal or a Dog object, their respective versions are called. This is a fundamental example of polymorphism. (More details on polymorphism in a later part.)

Constructors and Default Constructors

Recall how constructors work:

  • Default Constructor: If you don’t define any constructors for a class, Java provides a default constructor (no arguments). It initializes instance variables to their default values (0 for numbers, false for booleans, null for objects).
  • User-Defined Constructors: If you define any constructor, the default constructor is not automatically provided. You have to explicitly define a no-argument constructor if you need one.

Inheritance and Default Constructors

  • Subclass Default Constructors: If a subclass doesn’t define any constructors, it gets a default constructor. This default constructor implicitly calls the superclass’s no-argument constructor. This ensures that the superclass part of the subclass object is properly initialized.
class A {
  int x;
  String y;
 
  public A() {
    x = 0;
    y = null;
  }
}
 
 
class B extends A {
  int z;
  // Compiler automatically adds
  // public B() {
  //   super(); //Calls the constructor A() from A
  //   z = 0;
  // }
}
  • Super Class with User-defined constructor: However, if the superclass only has constructors with parameters (and no no-argument constructor), and the subclass doesn’t define any constructors, the subclass will not compile. This is because subclass default constructors implicitly look for the superclass’s no argument constructor to call and if such one doesn’t exist, an error is thrown. To fix this, you must explicitly write a constructor for B, which calls the appropriate constructor from A using super()

Example

 
public class Animal {
  public String name;
  public int age;
 
  public Animal(String n) {
    name = n;
    age = 0;
  }
  // ... other methods ...
}
 
public class Cat extends Animal {
  int mice;
 
  public Cat(String n) {
    //Calls constructor from Animal, to set cat's name and age
    super(n); 
    mice = 0;
  }
  // ... other methods ...
}
 
// Assume that Dog’s only constructor has a parameter for its name
public class Dog extends Animal {
 
  public Dog(String n){
    //Calls constructor from Animal, to set dog's name and age
    super(n); 
  }
}

super() Keyword

  • Calling Superclass Constructors: To call a specific superclass constructor from a subclass constructor, use super(arguments). This must be the first statement in the subclass constructor.

  • Implicit super(): If you don’t explicitly call super() in a subclass constructor, Java automatically inserts a call to the superclass’s no-argument constructor (if one exists). If you’ve explicitly defined a constructor with parameters in the super class but no no-argument constructor exists, the code does not compile. In other words, the compiler only implicitly adds super(); to your sub class’s constructors if the super class has a no-argument constructor.

  • Constructor Chaining in Inheritance: When a subclass object is created, constructors are called in a chain, starting from the top of the inheritance hierarchy (the most general superclass) down to the specific subclass.

Example: (Extending the Dog/Animal example)

 
public class Animal {
 
 //...
}
 
 
public class Dog extends Animal {
 
  //...
}
 
public class Husky extends Dog {
  public Husky() {  // Husky's constructor
        // Implicit call to super()
        // which is Dog(), which itself calls Animal("Bello")
    //...
  }
}
 
// Creating a Husky object:
 
Husky h = new Husky();
// This results in the following constructor calls:
// 1. Animal("Bello") (called from Dog())
// 2. Dog() (called implicitly from Husky() 
	// if Husky() had no explicit super() call)
// 3. Husky()

Visibility Modifiers

Recall the visibility modifiers in Java:

  • public: Accessible from anywhere.
  • protected: Accessible within the same package and by subclasses (even if in a different package).
  • (package-private, no modifier): Accessible only within the same package.
  • private: Accessible only within the same class.

Inheritance and Visibility

  • Inheriting Members: A subclass inherits all the non-private members of its superclass. private members are not directly accessible in the subclass.

  • private Members and Encapsulation: private members are part of the superclass’s internal implementation and are hidden from subclasses. This supports encapsulation. The subclass should not be dependent on the superclass’s private implementation details.

Example: (Illustrating how private members aren’t accessible)

public class Animal {
    private String name;  // Private attribute
 
    // ... other methods ...
}
 
 
public class Cat extends Animal {
    public void eat() {
        System.out.println(name + " eats tuna!"); 
        // Compiler error! name is private in Animal
 
    }
}

Continue here: 17 Visibility Modifiers, Sub Typing, Typecasts, Dynamic Binding, Polymorphism

Graph View