Chapter 7:  "The List ADT"

Data Structures with Java, Rick Mercer

Answers to Self-Check Questions


7-1 which throws an exception? a, b, and c
	  -a- / by 0 
	  -b- NullPointerException because names[1] is null
	  -c- No runtim error, but this is a compiletime error because names is not intialized
	
7-2 read in from a file

    public void readAndPrint(String fileName) {

        Scanner inputFile = null; // To avoid compiletime error later
        try {
            inputFile = new Scanner(new File(fileName));
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        while (inputFile.hasNextLine()) {
            System.out.println(inputFile.nextLine());
        }
    }
	
7-3 O(n) since add is a linear operation.

7-4 b.  The list has [C, B, A]
	
7-5 removeElementAt is O(n);

7-6 remove is O(n)

7-7 O(n^2)  removeAll has an O(n) operation preformed n/2 times 

7-8 O(1) Java initializes all 20 elements of data, but n is not a factor


7-10 (change to 7-9)  prefered most likely: O(n)
 

7-11 (change to 7-10)  

    // Add these test methods to the unit test first
    
    @Test(expected = IllegalArgumentException.class)
    public void removeElementAtShouldThrow() {
        OurList<String> list = new OurArrayList<String>();
        list.removeElementAt(0);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void removeElementAtShouldThrow2() {
        OurList<String> list = new OurArrayList<String>();
        list.insertElementAt(0, "anything");
        list.removeElementAt(1);   // must throw exception
    }

    @Test
    public void testRemoveElementAt() {
        OurList<String> list = new OurArrayList<String>();
        assertEquals(0, list.size());
        list.insertElementAt(0, "A");
        list.insertElementAt(1, "B");
        list.insertElementAt(2, "C");
        list.insertElementAt(3, "D");
        list.removeElementAt(0);
        assertEquals("B", list.get(0));
        assertEquals("C", list.get(1));
        assertEquals("D", list.get(2));
        list.removeElementAt(2);
        assertEquals("B", list.get(0));
        assertEquals("C", list.get(1));
        list.removeElementAt(0);
        assertEquals("C", list.get(0));
    }

    public void removeElementAt(int removalIndex)
            throws IllegalArgumentException {
        if (removalIndex < 0 || removalIndex >= size)
            throw new IllegalArgumentException();

        for(int i = removalIndex; i < size-1; i++)
            elements[i] = elements[i + 1];
    }


7-12 (change to 7-11)  

    // Add this to the unit test first
    @Test
    public void testRemove() {
        OurList<String> list = new OurArrayList<String>();
        assertEquals(0, list.size());
        list.insertElementAt(0, "A");
        list.insertElementAt(1, "B");
        list.insertElementAt(2, "C");
        list.insertElementAt(3, "D");

        assertFalse(list.remove("Not here"));
        
        assertEquals(4, list.size());
        assertTrue(list.remove("A"));
        assertEquals(3, list.size());
        assertEquals("B", list.get(0));
        assertEquals("C", list.get(1));
        assertEquals("D", list.get(2));
        
        assertTrue(list.remove("D"));
        assertEquals(2, list.size());
        assertEquals("B", list.get(0));
        assertEquals("C", list.get(1));

        assertTrue(list.remove("B"));
        assertTrue(list.remove("C"));
        assertEquals(0, list.size());
    }
    

    public boolean remove(E element) {
        int spot = -1;
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i]))
                spot = i;
        }

        if (spot == -1)
            return false;

        for (int i = spot; i < size - 1; i++)
            elements[i] = elements[i + 1];
        size--;
        return true;
    }