Question I. $(40$ points$)$ Consider a variation of the singly linked list that always has a "dummy node" at the

beginning of the list with no data $($i$.$e$.$ the info field is always null$).$ An empty list contains the dummy node

only. A list with n elements has $n+1$ nodes, the first node is the dummy node.

a$.$ Rewrite the constructor for SinglyLinkedList so that it creates an "empty" list consisting of the one

dummy node.

b$.$ Rewrite the methods addToHead$(),$ addToTail$(),$ deleteFromHead$(),$ deleteFromTail$(),$ search$()$ and

isEmpty$().$

c$.$ Implement a new method reverse$()$ that reverses the nodes on the singly linked list.

Question II $(40$ points$)$: Using the provided Stack class implementation in the lab, you will create a parser to

identify a secret message hidden within another string. These secret messages are enclosed in curly braces

within otherwise readable text $($e$.$g$.,$ "This sentence contains a $\{$terces$\}$ message"$).$ The secret messages are just

words in reverse, which we can use a stack to flip back into a readable format. Write a method decode$()$ that

prints all secret messages between $\text{'}\text{'}$ and $\text{'}\}\text{'}$ characters. Below are some sample outputs.