Link Menu Search Expand Document

Advanced LinkedIntList

ed Lesson

Table of contents


Special constructor

So far, the constructors we’ve written have only performed simple field assignments.

Implementer

public LinkedIntList() {
    front = null;
}

In reality, constructors can have complicated behaviors as well. Let’s define a new constructor LinkedIntList that accepts an integer n as a parameter and constructs a list of integers from n to 0 (decreasing order).

There are a couple ways to approach this problem. So far, we’ve been focusing on adding elements to the end of the list, and we could certainly also do that here too by just calling the add method repeatedly with smaller and smaller values.

Implementer

public LinkedIntList(int n) {
    for (int i = n; i >= 0; i--) {
        add(i);
    }
}

However, it turns out that this code is very slow. Remember that add appends the value to the end of the list, which requires traversing the entire list from the front all the way to the node at the end.

A better way to do this is to repeatedly add larger and larger values to the very front of the list. The add(int index, int value) method can help us here!

Implementer

public LinkedIntList(int n) {
    for (int i = 0; i <= n; i++) {
        add(0, i);
    }
}

But remember that our implementation for add(int index, int value) handled inserting a value at the front of the list as a separate case. Since we’re always calling add(0, i) in the loop above, we can replace it with just the code for handling the special case.

Implementer

public LinkedIntList(int n) {
    for (int i = 0; i <= n; i++) {
        front = new ListNode(i, front);
    }
}