April:03(Fri)

CS 163(M) Assignment #4

Due Friday, April 10

Acknowledgement: Some of these exercises are derived from "A Practical Introduction to Data Structures and Algorithm Analysis" by Clifford A. Shaffer.




1. [5 points]   Suppose we're using the first linkList.java code, and suppose at some point in main(), theList contains five elements, as follows:

   [V, W, X, Y, Z]

   E.g. V might be {88, 8.99}, W might be {77, 7.99}, etc.  Write a series of Java statements to be used in main() to delete just the third element here, X, so theList will be as follows.

   [V, W, Y, Z]

   Do NOT use delete(int key) which is supposed to be in the second linked-list program linkList2.java; use only methods provided in the first linked-list program.

   
   

2. [6 points]   Augment the second linked-list program linkList2.java with a method interchange_with_next(int key) to interchange the element specified by key with the one immediately following it in the list. (Note that you can do this without changing any next-links. Consider an analogous situation: to swap elements in an array, do you need to really make any changes to the structure of the array itself?)
   All you need to submit for this exercise is the text of your new method; don't bother printing all the given parts of linkList2.java .
   You may assume that the list does have an element containing key and a following element.

3. [8 points]   Add to class LinkList a method concatenate() that takes another LinkList as an argument and returns the result of adding the given list to the end of the one for which the method is invoked.  E.g. if list1 is [A,B,C] and list2 is [D,E,F], then list1.concatenate(list2) should return [A,B,C,D,E,F].
   All you need to submit for this exercise is the text of your new method; don't bother printing all the other parts of linkList2.java .

   
   

4. [10 points]  Consider the following sequence of stack operations (assuming the stack here is a version that can store integers directly):
   push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop(), pop(), pop(), pop().
   Show how the stack looks before the first operation and after each of these operations, noting values returned by pop() or exceptions thrown. Show the stack in the format specified in lectures, e.g. as follows:

   |   |           |   |           |   |           |   |
   |   |           |   |           | 4 |           |   |
   |   |  push(6)  | 6 |  push(4)  | 6 |  pop():4  | 6 |  ...
   +---+           +---+           +---+           +---+