Compsci 100e, Spring 2011, Classwork 11
This classwork focuses on implementing linked lists. Start by snarfing the
code
under classwork-rodger/11ClwkLinkedLists.
Turn this classwork by submitting it to Clwk11LinkedLists.
Part 1 - Linked List
The first code we will look at is LinkedStuff.java
which involves singly linked lists.
Here is a Node for a linked list.
public static class Node {
String info;
Node next;
public Node(String str, Node link)
{
info = str;
next = link;
}
}
- Finish the addIter method to add all the words from a Scanner
to a linked list in the order they appear in the Scanner.
- Complete the print method to print out the nodes in a linked
list. That is, print out the info field for each node.
- Complete the addRec method to add all the words from a Scanner to
a linked list in the order they appear in the Scanner. Make this a
recursive method.
- Complete the method reverseAddIter to add all the words from a
Scanner to a linked list in the reverse order they appear in the Scanner.
- Complete the method lastNode that returns a reference to the last
node
in a linked list, or null if the list is empty. Make this a recursive
method.
- Complete the method reverseAddRec to add all the words from a
Scanner to a linked list in the reverse order they appear in the Scanner.
Make this a recursive method.
- Complete the method doubleList that has a parameter to a linked
list and
returns the list with each node doubled. For example if the list is -> a ->
b -> c, then doubleList returns the list -> a -> a -> b -> b -> c
-> c.
Part 2 - Doubly Linked List
The next code we will look at is DoubleLinkStuff.java
which involves doubly linked lists.
Here is a Node for a doubly linked list.
public class DoubleLinkStuff {
public static class Node {
String info;
Node prev;
Node next;
public Node(String str, Node pv, Node nt)
{
info = str;
prev = pv;
next = nt;
}
}
- Complete the addIter method to add all the words from a Scanner
to a doubly linked list in the order they appear in the Scanner.
Note the print and print detailed methods are given to you.
What does the printDetail method do?
- Complete the method printReverse to print the elements out in reverse
order. Assume there is at least one node in the list.
- Complete the method moveToFront that is given a word. If that word is
in the linked list, then that node is moved to the front of the linked
list. If it is not in the linked list, then the list is returned
with
no changes in the list.
Submit
Turn this classwork by submitting it to Clwk11LinkedLists.