Building Java Programs

Lab: Linked Lists

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

Lab goals

Goals for this problem set:

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

LinkedIntList

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

LinkedIntList.java

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

• LinkedIntList.java

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 -> [1] -> [2] /

Into this sequence of ListNode objects:

list -> [1] -> [2] -> [3] /

Exercise : linkedNodes2

Write the code necessary to convert the following sequence of ListNode objects:

list -> [1] -> [2] /

Into this sequence of ListNode objects:

list -> [3] -> [1] -> [2] /

Exercise : linkedNodes3

Write the code necessary to convert the following sequences of ListNode objects:

list -> [1] -> [2] /
temp -> [3] -> [4] /

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

list -> [1] -> [3] -> [4] -> [2] /

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 ArrayLists 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 ArrayLists to solve this problem. Your method should run in O(N) time where N is the number of nodes in the list.