# Building Java Programs

Except where otherwise noted, the contents of this document are Copyright 2019 Stuart Reges and Marty Stepp.

# Lab goals

Goals for this problem set:

• write traversals over a linked list
• practice removing and inserting nodes

In this chapter, we implement a collection called `LinkedIntList`. • Similar to an `ArrayList` or `ArrayIntList` of `int` values, but implemented using a sequence of linked node objects.
• Each node object stores an integer `data` and a reference to the `next` node.
• The overall list object stores a reference to the front node of the list (`null` if empty).

Here is the code for `LinkedIntList` as written in this chapter:

The class uses the following data field (refer to it in your exercise solutions):

```public class LinkedIntList {
private ListNode front;   // first value in the list; null if empty
...
}
```
```public class ListNode {
public int data;        // data stored in this node
public ListNode next;   // link to next node in the list
...
}
```

# Exercise : `linkedNodes` Write the code necessary to convert the following sequence of `ListNode` objects:

```list ->  ->  /
```

Into this sequence of `ListNode` objects:

```list ->  ->  ->  /
```

# Exercise : `linkedNodes2` Write the code necessary to convert the following sequence of `ListNode` objects:

```list ->  ->  /
```

Into this sequence of `ListNode` objects:

```list ->  ->  ->  /
```

# Exercise : `linkedNodes3` Write the code necessary to convert the following sequences of `ListNode` objects:

```list ->  ->  /
temp ->  ->  /
```

Into this sequence of `ListNode` objects: (It does not matter what `temp` refers to at the end of your code.)

```list ->  ->  ->  ->  /
```

# Recall: Looping over a list

Most linked list algorithms create a "current" list node variable that refers to a given node and walks through the list.

```// post: returns the current number of elements in the list
public int size() {
int count = 0;
ListNode current = front;
while (current != null) {
current = current.next;
count++;
}
return count;
}
```

# Exercise : `min` Write a method `min` to be added to the `LinkedIntList` class. Your method should find and return the minimum value in the list of integers.

For example, if a `LinkedIntList` variable `list` stores `[42, 17, 29, 8, 54, 36]`, the call of `list.min()` should return `8`. If the list is empty, throw a `NoSuchElementException`.

# Exercise : `hasTwoConsecutive` Write a method `hasTwoConsecutive` to be added to the `LinkedIntList` class. Your method should return `true` if the list of integers has two adjacent numbers that are consecutive integers, and `false` if not.

For example, if a `LinkedIntList` variable `list` stores `[1, 18, 2, 7, 8, 39, 18, 40]`, then the call `list.hasTwoConsecutive()` should return `true` because the list contains the adjacent numbers (7, 8), which are a pair of consecutive numbers.

# Recall: Manipulating a Linked List

When adding or removing a node in a linked list, you need a reference to the node before the node of interest. This allows you to modify the `next` reference of that node to point somewhere else, thus adding or removing.

Example: To remove the node 8 below, need a `curr` reference to the node 3 before it.

```                                    curr
|
|
v
data next    data next   data next   data next   data next
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+
front --> | 7 | --+--> | 2 | --+-->| 3 | --+-->| 8 | --+-->| 1 | / |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+
```
```// remove the node
curr.next = curr.next.next;   // 3 -> 1
```
```                                    curr
|
|        ___________
v       /           \
data next    data next   data next/  data next  \ data next
+---+---+    +---+---+   +---+---/   +---+---+   v+---+---+
front --> | 7 | --+--> | 2 | --+-->| 3 |  /|   | 8 |   |    | 1 | / |
+---+---+    +---+---+   +---+---+   +---+---+    +---+---+

```

# Exercise : `deleteBack` Write a method `deleteBack` to be added to the `LinkedIntList` class. Your method should delete the last value (the value at the back of the list) and return the deleted value.

For example, if a `LinkedIntList` variable `list` stores `[7, 4, 2, 5]`, then the call `list.deleteBack()` should modify the list to store `[7, 4, 2]` and should return `5`. If the list is empty, throw a `NoSuchElementException`.

# Exercise : `removeAll` Write a method `removeAll` to be added to the `LinkedIntList` class. Your method should accept an integer value as a parameter and remove all occurrences of that value from the list.

For example, if a `LinkedIntList` variable `list` stores `[3, 9, 4, 2, 3, 8, 17, 4, 3, 18]`, the call of `list.removeAll(3);` would change the list to store `[9, 4, 2, 8, 17, 4, 18]`.

# Exercise : `doubleList` Write a method `doubleList` to be added to the `LinkedIntList` class. Your method should double the size of the list by appending a copy of the original sequence to the end of the list.

For example, if a `LinkedIntList` variable `list` stores `[1, 3, 2, 7]` and we make the call of `list.doubleList();` then after the call it should store `[1, 3, 2, 7, 1, 3, 2, 7]`.

Constraints: You may not call any methods of the class to solve this problem. You may not use any auxiliary data structures such as arrays or `ArrayList`s to solve this problem. Your method should run in O(N) time where N is the number of nodes in the list.

# Exercise : `reverse` Write a method `reverse` to be added to the `LinkedIntList` class. Your method should reverse the order of the elements in the list. (This is very challenging!)

For example, if a `LinkedIntList` variable `list` initially stores the values `[3, 8, 29, 4, 17]`, the call of `list.reverse();` should change the list to store `[17, 4, 29, 8, 3]`.

Constraints: You should build the reversed list by rearranging `next` references between existing nodes, not by creating new `ListNode` objects. (You may create `ListNode` variables to refer to existing objects as needed.) You may not use any auxiliary data structures such as arrays or `ArrayList`s to solve this problem. Your method should run in O(N) time where N is the number of nodes in the list.