Answers to Self-Study Questions for Linked-Lists

Test Yourself #1

Test Yourself #2

Question 1. = "cat";

Question 2. = new Listnode("rat",;

Test Yourself #3

The list begins:

and after the code looks like:

and this is correct.

Test Yourself #4


linked list


remove first



remove last



For linked list: To remove the first node you only have to do L = so this is O(1). To remove the last node you must traverse the list from the first node to get to the next to last node to do the delete so this is O(N).

For arrays: To remove the first item you must shift all the remaining items one array location to the left to fill in the hole so this is O(N). To remove the last item there are no shifts because no items are to the right so this is O(1).

Test Yourself #5

    // Note: this code has excessive comments to help you understand it in detail.
    // returns true if val is in circular linked list L; otherwise returns false
    if (L == null) return false;  // no items on list so not found
    if ( return true;  // val is in first node on list
    Listnode tmp =;
    while (tmp != L) {  // stops from going past first node and going in circles
        if ( return true;  // found val at this node
        tmp =;
    return false;  // did not find val in list