**Name:** ___________________________________________________________________

1-2. The code below is an **incorrect** implementation of the
`search(T)`

method of the class
`LinkedListClass`

described in the textbook.

public void search(T searchItem) { LinkedListNodecurrent; boolean found; current = first; found = false; while (!found) {if (current.info.equals(SearchItem)) found = true; else current = current.link;} return found; }

- Trace the execution of the code above and explain why it is not always correct.
- Write a correct implementation of the
`search(T)`

method.

3. In the array and linked list implementations of a stack, write pieces of code for pushing an element "Monday" onto an arbitrary stack of strings. Trace both your codes on the example of a stack which originally has elements "Saturday" and "Sunday", with "Sunday" being the top element.

4-5. Consider the following arithmetic expression:

- Rewrite the expression above using postfix notation
- Using the
`peek()`

,`pop()`

, and`push()`

methods, show how a stack can be used to support the evaluation of the expression in its postfix representation.

6. The implementation of the

`LinkedListClass`

in the
textbook includes instance variables `count`

of type `int`

and `last`

of type
`LinkedListNode`

- Explain the role of these instance variable in supporting methods in the class.
- Explain the consequence(s) of
`LinkedListClass`

not having these instance variables.

7. Let us have a queue that represents the order in which a student prepares for tests at different classes. Let us assume that this queue is implemented as an array of size 4. Originally, the queue is empty. Show, step-by-step, what will happen if we first add, to the queue, elements "CS 2401", "Discrete Math", and "History", then delete "CS 2401" (test is over), then delete "Discrete Math" (test is over), and then again add "CS 2401" and "Discrete Math" (test 2 is coming).

8. Using the class

`UnorderedLinkedList`

as defined in
the textbook, consider the following Java statements:
UnorderedLinkedListWhat is the output of this program segment?list = new UnorderedLinkedList (); list.insertLast("Saturday"); list.insertFirst(list.back()); list.insertLast("Sunday"); list.insertFirst("Monday"); list.insertFirst("Tuesday"); list.print(); list.insertLast(list.front());