LinkedIntList nodes

ed Lesson

Table of contents

• ArrayList analysis
• Computer memory
• Linked nodes
• Constructors

ArrayList analysis

One of the drawbacks of using ArrayList is that making changes to the list can be costly. When we implemented removeFront, we saw that it required moving every element in the list over by 1 space. In the same way, inserting an element at a given index can also require a significant amount of time. (We’ll formalize these ideas of how long it takes to run a program in a later lesson.)

In an ArrayList, the element at index i in the list ADT is guaranteed to be stored at index i of the underlying data array. Even though removeFront and add at an index aren’t as fast they could be, it turns out that this array-based representation is a natural fit for the way that computers represent data in memory. However, arrays aren’t the only way to represent list structures. This week, we’ll study another way of implementing the List interface with an entirely different set of design principles that optimizes for adding and removing at the front or back of the list.

Computer memory

In the context of programming, main memory most often refers to the digital workspace that is made available to running programs.

Main memory functions like a very large array. When we create a new int[10], Java communicates with the computer’s operating system to reserve a chunk of main memory large enough to fit 10 integers. This chunk of memory is contiguous: all of the items are next to each other with no gaps in between.

Say we want to represent a list of the following numbers, [42, -3, 17, 9].

Contiguous memory

42

-3

17

9

In an ArrayIntList, the i-th element of the list is always stored at array index i. We maintained this assumption through implementing every method in the ArrayIntList class. As a result, contiguous memory data structures like the ArrayIntList typically provides fast access to the value at any particular index, such as in the get method. (On the other hand, we know that ArrayIntList.removeFront is quite slow.)

Let’s say we don’t require contiguous memory. In non-contiguous memory, elements can be stored anywhere in memory.

Non-contiguous memory

42

9

-3

17

Non-contiguous memory provides more flexibility since an item can be added anywhere. However, it’s now much more difficult to know where the next element in the sequence is stored. In an ArrayList, the next element is always stored right next to the current element. If we want to represent a list in non-contiguous memory, we won’t know which element comes before or after the current element unless we follow a reference to the next element in the list.

An analogy that might be helpful is to think of contiguous memory as a book and non-contiguous memory as a choose-your-own-adventure novel. Pages in a book (elements in the list) are read from the beginning to the end, so it’s not too hard to estimate where the middle page lies. In a choose-your-own-adventure, the novel is not organized so that it can be read from the beginning to the end. Instead, the reader must follow directions to determine the next page to read. It’s much harder to determine the “middle page” in a choose-your-own-adventure novel since we would need to go page-by-page, following the directions on each page to know where to go next.

Linked nodes

Linked nodes are a non-contiguous memory data structure. In Java, we’ll design a ListNode class to represent the concept of a “page” in a choose-your-own-adventure novel. There are two pieces of information that are key to the ListNode class.

1. The data for the linked node.
2. The directions to the next linked node.

Implementer

public class ListNode {
    int data;
    ListNode next;
}

We oftentimes design the ListNode class such that its fields are public. Note that for most every other use, this would be an example of poor style since it exposes the ListNode internals to the client. But in this case, we can make sure that the client never knows that the ListNode class exists. As a direct example, last week we used the LinkedList class as an implementation of the Queue interface without knowing about the existence of linked nodes.

Implementer

public class ListNode {
    public int data;
    public ListNode next;
}

As the implementer for a LinkedIntList that uses the ListNode class as a building block, we can create a new ListNode instance, assign it to the variable list, and set its data field to 42. This represents the beginning of our list [42].

ListNode list = new ListNode();
list.data = 42;

If we want to add the element -3 to the end of the list, we’ll need to modify the next field.

ListNode list = new ListNode();
list.data = 42;
list.next = new ListNode();
list.next.data = -3;

Constructors

We can simplify our ListNode code by introducing additional constructors.

Implementer

public ListNode(int data) {
    this.data = data;
}

The one-argument ListNode constructor saves us the work of having to set the data field manually.

ListNode list = new ListNode(42);
list.next = new ListNode(-3);
list.next.next = new ListNode(17);

We can further simplify this code by providing a constructor that also sets next field.

Implementer

public ListNode(int data, ListNode next) {
    this.data = data;
    this.next = next;
}

By using the two-argument constructor, we can create a ListNode sequence in a single statement by chaining together new instances.

ListNode list = new ListNode(42, new ListNode(-3, new ListNode(17)));