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; } }
  1. Finish the addIter method to add all the words from a Scanner to a linked list in the order they appear in the Scanner.

  2. Complete the print method to print out the nodes in a linked list. That is, print out the info field for each node.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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; } }

  1. 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?

  2. Complete the method printReverse to print the elements out in reverse order. Assume there is at least one node in the list.

  3. 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.