Quiz 2 Practice Problems

Solutions will be posted under Other Content on Blackboard as we get closer to the exam.

These problems are not comprehensive, so make sure to review all of the relevant materials.

Questions 1 and 2 involve linked lists of integers that are constructed from nodes whose class definition begins as follows:

public class Node {
    private int val;
    private Node next;

    public Node() {
        this.val = 0;
        this.next = null;
    }
    ...
}

1. You want to add a method to the Node class that takes two parameters:

   • a reference to the first node in a linked list (or null if the list is empty)

   • an integer x

   The method should insert a node containing x at the front of the list, and it should return a reference to the new front of the list.

   Which of these methods does this correctly?

   option I:

   public static Node insertFront(Node first, int x) {
       first = new Node();
       first.val = x;
       first.next = first;
       return first;
   }
   

   option II:

   public static Node insertFront(Node first, int x) {
       Node n = new Node();
       n.val = x;
       n.next = first;
       return n;
   }
   

   option III:

   public static Node insertFront(Node first, int x) {
       Node n = new Node();
       first = n;
       n.val = x;
       n.next = first;
       return first;
   }
   

   1. only I
   2. only II
   3. only III
   4. I and II, but not III
   5. II and III, but not I

2. The intent of the method below is to delete the last node in the linked list to which the parameter first refers:

   public static void removeLast(Node first) {
       Node p = first;
       Node q = p.next;
   
       while (q.next != null) {
           p = q;
           q = q.next;
       }
   
       p.next = null;
   }
   

   Which of the following describes the subset of linked lists for which this method works correctly?

   1. no linked lists
   2. all nonempty linked lists
   3. all linked lists with more than one node
   4. the empty list and all linked lists with more than one node
   5. all linked lists

3. A doubly linked list is constructed from nodes that are instances of the following class:

   public class DNode {
       private char ch;
       private DNode next;
       private DNode prev;
   }
   

   The next field holds a reference to the next node in the linked list, and the prev field holds a reference to the previous node in the linked list.

   Below is a list of three of these nodes, along with two reference variables, n and p, that refer to specific nodes in the list:

   

   Which of the following expressions does not refer to the third node in the list?

   1. p.next
   2. n.next.next
   3. p.prev.next
   4. p.prev.next.next
   5. n.next.next.prev.next

4. The diagram below suggests how we could implement a linked list in which we maintain a reference to both the first and last nodes in the linked list:

   

   Which of the following operations would be inefficient to carry out when there are a large number of elements in the linked list?

   1. insertion at the end to which front refers
   2. insertion at the end to which rear refers
   3. deletion from the end to which front refers
   4. deletion from the end to which rear refers

5. The diagram below shows a linked list of characters that is constructed from instances of the StringNode class from lecture:

   

   In addition, we have included two variables that each store a reference to one of the nodes in the linked list, along with the memory address of each node. You should assume that the ch field has the same address as the node itself, and that the address of the next field is 2 bytes after the beginning of the node.

   1. What is the memory address of the field given by the expression head.next.next?

   2. What is the value of the expression head.next.next?

   3. Write one or more lines of code that remove the node containing the character 's' from the list.

   4. Modify the diagram to reflect the results of executing the following lines on the original version of the list (before the 's' was removed):

      q = q.next;
      q.next = head;
      

6. This question involves linked lists of integers that are constructed from nodes of the following class:

   public class Node {
       private int val;
       private Node next;
   }
   

   1. Write a static method named numEvenRec() that takes a reference to the first node in a linked list of integers and uses recursion to determine and return the number of even values in the list.

   2. Write a static method named numEvenIter() that takes a reference to the first node in a linked list of integers and uses iteration to determine and return the number of even values in the list.

7. Write a static method called everyOther() that is a member of the StringNode class. It should take a reference to the first node in a linked-list string, and it should create and return a reference to a new linked-list string that contains every other character from the original string. The original linked list should not be modified. You may use either recursion or iteration.

8. Consider the following method:

   public static void addAllTo(String[] names, List myList) {
       for (int i = 0; i < names.length; i++) {
           myList.addItem(names[i], i);
       }
   }
   

   The method takes an array of strings and an instance of one of the classes that implement the List interface from lecture – either an ArrayList or an LLList – and it adds all of the strings in the array to the list.

   You may assume that the list is initially empty, and that it is possible to successfully add all of the strings in the array to the list without running out of room.

   From the perspective of time efficiency, does it matter which type of List is passed in – ArrayList or LLList? Explain your answer briefly.

Last updated on April 18, 2026.