CS Notes

15 Linked Lists, Inner Classes, Methods, Recursive Methods, Built-in Lists

Jan 17, 202510 min read

Lecture from: 12.11.2024 | Video: Videos ETHZ

Linked Lists

Continuation from our intro to Linked Lists from last lecture…

Last time we looked at examples that demonstrate basic linked list manipulation. However, working directly with ListNode objects can become cumbersome and error-prone, especially for more complex operations. It’s better to encapsulate the internal node structure within a LinkedList class and provide methods to interact with the list. Before we introduce that class, let’s discuss another essential operation: outputting the elements of a linked list.

Outputting Linked List Elements

A frequent task is to print the elements of a linked list. A naive approach might lead to a common pitfall.

Incorrect Approach (Modifies the List)

// DON'T DO THIS! (Modifies the original list)
public void printList(ListNode head) { // Assuming head is the start of the list
    while (head != null) {
        System.out.print(head.value + " ");
        head = head.next;  // This modifies the original list!
    }
    System.out.println();
}

This approach has a significant problem: it modifies the original list. After calling this method, the original list will be empty because the head reference is moved through the list and eventually becomes null.

Correct Approach (Using a Temporary Variable)

To avoid modifying the original list, we use a temporary variable (current) for traversal:

public void printList(ListNode head) {
    ListNode current = head;  // Assign head to current
    while (current != null) {
        System.out.print(current.value + " ");
        current = current.next;
    }
    System.out.println();
}

This version preserves the original list structure because the head reference remains unchanged. The current variable is used for traversal, leaving the original list intact.

Now, before moving on to implementing a full LinkedList class, let’s have a short intro on inner/nested classes, as these will be useful in our LinkedList implementation.

The LinkedList Class: Encapsulation and Inner Classes

As discussed, directly manipulating ListNode objects is not ideal. We’ll create a LinkedList class to encapsulate the nodes and provide a cleaner interface. Before that, a brief look at inner classes:

Inner/Nested Classes

Before defining the LinkedList class, let’s introduce inner/nested classes. These are classes defined inside another class. They’re particularly useful for encapsulation and organization, especially when a helper class (like ListNode) is only used by the enclosing class (like LinkedList).

  • Access to Outer Class Members: Inner classes have access to all members (fields and methods) of the outer class, even private ones.
  • Visibility: The visibility of the inner class itself can be controlled (e.g., private, public, etc.). A private inner class is only accessible within the outer class.
  • OuterClass.this: To disambiguate between members of the inner and outer class with the same name, use OuterClass.this.memberName to refer to the outer class’s member.
Example
class OuterClass {
    private int x = 3;
 
    String foo() {
        InnerClass inner = new InnerClass(9);
        return inner.bar();
    }
 
 
    private class InnerClass {
        private int x;
 
        private InnerClass(int a) { x = a; }
 
        private String bar() {
            return x + " " + OuterClass.this.x; // Accesses outer x
        }
    }
}
 
OuterClass outer = new OuterClass();
System.out.println(outer.foo()); // Output: 9 3

Important Note: Instantiation of Inner Classes

Inner class instances can only exist within an instance of the outer class. You cannot create an inner class object directly from a static method (like main) without first having an instance of the outer class.

//This is incorrect: Trying to instatiate an InnerClass inside main() is not allowed.
public class OuterClass {
    // ...
 
    public static void main(String[] args) {
        InnerClass inner = new InnerClass(9); // Compiler Error!
    }
 
    private class InnerClass { //...
 
    }
}
 
//This is correct:
public class OuterClass {
    // ...
 
        public static void main(String[] args) {
 
           OuterClass oc = new OuterClass(); // First create outer class
 
           InnerClass inner = oc.new InnerClass(9); // Now you create the inner class.
           // ...
        }
 
    private class InnerClass { //...
    }
}

LinkedList Class (Using a Nested Inner Class)

public class LinkedList {
 
    private class ListNode { // ListNode is now a private inner class
        private int value;
        private ListNode next;
 
        ListNode(int value) {
            this.value = value;
        }
 
        ListNode(int value, ListNode next) {
            this(value);
            this.next = next;
        }
 
        // Recursive functions here...
    }
 
    private ListNode front; // Reference to the first node (head)
    //private ListNode back; // We *could* also store a back reference (more on this later)
 
    public LinkedList() {
        front = null;
       // back = null;
    }
 
    // ... public methods for list operations (size(), get(), add(), remove(), etc.)
}

Notice that ListNode and front are now private. Clients cannot directly access or manipulate nodes; they must use the public methods of LinkedList.

Basic LinkedList Operations

1. size()

public int size() {
    int count = 0;
    ListNode current = front;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

Note that the size can be stored as a separate attribute too to improve performance.

2. get(int index)

public int get(int index) {
    assert 0 <= index && index < size();
    ListNode current = front;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.value;
}

3. back()

private ListNode back() {  // Note: private, as clients don't need direct access
    ListNode current = front;
    while (current != null && current.next != null) {
        current = current.next;
    }
    return current; 
}

This version avoids potential NullPointerException issues.

Example of a (subtly) faulty implementation:

Adding Elements

Now, let’s implement methods to add elements to our LinkedList.

add(int value, int index)

Inserts a new node with the given value at the specified index.

public void add(int value, int index) {
    assert 0 <= index && index < size(); //Enforces the index to be within bounds.
 
    if (index == 0) {
        front = new ListNode(value, front); // Adding at the beginning is a special case
    } else {
        ListNode current = front;
        for (int i = 0; i < index - 1; i++) { // Traverse to the node *before* the insertion point
            current = current.next;
        }
        current.next = new ListNode(value, current.next); // Insert the new node
    }
}

addBack(int value) (Adding at the End)

Adds a new node with the given value at the end of the list. This uses our back() method.

public void addBack(int value) {
    ListNode newNode = new ListNode(value);
    if (back() == null) {  // If the list is empty
        front = newNode;   // The new node becomes the front
    } else {
        back().next = newNode; // Append to the end
    }
}

Removing Elements

remove(int value)

Removes the first occurrence of a node with the given value.

public void remove(int value) {
    if (front == null) return; // Nothing to do if the list is empty
 
 
    if (front.value == value) { // Special case: removing the first node
        front = front.next;
        return;
    }
 
 
    ListNode current = front;
 
    while (current.next != null && current.next.value != value) { // Find node before one we want to delete
        current = current.next;
    }
 
 
    if (current.next != null) {  //Check to see if there was even a node to remove
        current.next = current.next.next; // Remove node
    } 
 
}

removeAt(int index)

Removes the node at the given index.

public void removeAt(int index) {
    assert 0 <= index && index < size();
 
    if (index == 0) {
        front = front.next; // Removing the first element
    } else {
        ListNode current = front;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;  // Removing the element at index
    }
}

merge(LinkedList other)

Appends the other list to the end of the current list.

public void merge(LinkedList other) {
    if (front == null) {
        front = other.front;  // If this list is empty, just take the other list
    } else {
        back().next = other.front; // Append the other list
    }
    other.front = null; // The other list is now empty
}

Object Invariants for LinkedList

Invariants are essential for ensuring data structure integrity. For our LinkedList, key invariants include:

  • size() returns the correct number of reachable nodes.
  • back() returns a reachable node (or null if the list is empty).
  • The list contains no cycles (each node can be reached at most once starting from front).

Sorted Linked Lists

A sorted linked list maintains its elements in sorted order (e.g., ascending). This adds an additional object invariant: the values in the list must always be in increasing (or decreasing) order.

SortedLinkedList Class

public class SortedLinkedList {
    // Invariant: elements are sorted in increasing order
    private ListNode front;
 
 
    private class ListNode { // Inner class as before
        // ... attributes and methods (same as LinkedList, so omitted here)
    }
 
    // ... constructor and other methods ...
}

add(int value) for SortedLinkedList

The add() method for a sorted linked list must ensure that the new element is inserted in the correct position to maintain the sorted order.

public void add(int value) {
    if (front == null || value <= front.value) { //Check if the list is empty or new value comes at the front.
        front = new ListNode(value, front);  // Special case: adding at the beginning
    } else {
        ListNode current = front;
        while (current.next != null && current.next.value < value) { //Find the appropriate place to insert.
            current = current.next;
        }
        current.next = new ListNode(value, current.next); // Insert new node
    }
}

Recursive Methods for Linked Lists

Recursive methods can provide elegant and concise solutions when working with recursive data structures like linked lists and trees.

Recursive Methods in ListNode

We can add recursive methods directly to our inner ListNode class. This allows the outer LinkedList class to call them, but they remain hidden and inaccessible from external code.

public class LinkedList { // LinkedList is now our outer class
   // ... (other methods for LinkedList as defined before)
 
    private class ListNode {
        // ... (attributes and constructors as before)
 
        public int size() { // Recursive size
            return (next == null) ? 1 : 1 + next.size();
        }
 
 
        public void addBack(int v) {  // Recursive addBack
            if (next != null) {
                next.addBack(v);
            } else {
                next = new ListNode(v);
            }
        }
 
 
        public void visit() { // Recursive traversal (example from slide 42)
            System.out.println(value);
            if (next != null) next.visit();
        }
    }
 
    // ... (other methods for LinkedList)
 
    private ListNode front;
    // ...
}
 
 
 
// Example usage from within LinkedList
public int sizeRecursive() {
    if (front == null) {
        return 0; // Empty list
    } else {
        return front.size();  // Call the recursive size() method of ListNode
    }
}
 
 
public void visitAll() {
    if(front != null) front.visit();
}

Recursive Methods in BinaryTreeNode

The same principles apply to trees. Here’s a recursive visit() method for a BinaryTreeNode:

class BinaryTreeNode {
    // ... attributes (value, left, right) ...
 
 
    void visit() {
        System.out.println(value);        // Visit the current node
        if (left != null) left.visit();    // Recursively visit the left subtree
        if (right != null) right.visit(); // Recursively visit the right subtree
    }
}

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

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 ...

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

Graph View