Lab 8

Due Friday, May 4, 5:00pm

String Linked Lists

For lab 8, you will redo lab 4, using a linked list instead of an array. You will create a class StringLinkedList, which will maintain a linked list of strings, and provides the same functionality as the StringList code you wrote earlier. Note that you are not allowed to use arrays (or ArrayLists!) for this assignment -- you must use linked lists.

Your class, called StringLinkedList, will maintain a linked list of Strings and provide most of the functionality of the Java class LinkedList (which is very similar to the java class ArrayList). In particular, you must implement the following components in your StringList class:

      1. A data member that stores the head of the linked list
      2. A constructor that takes no input and will create an empty linked list.
      3. The following methods that behave exactly as specified in the LinkedList documentation:
      4. public void addFirst(String s) - adds the new String s to the front of the linked list.
      5. public void addLast(String s) - adds the new String s to the end of the linked list.
      6. public void add(int index, String s) - adds the new String s at the specified position in the list. If index == size(), then s is added at the end of the list. If index < 0 or index > size(), throw and IndexOutOfBounds exception
      7. public boolean contains(String s) - returns true if the linked list contains the string s
      8. public void clear() - removes all of the elements from the list
      9. public int size() - returns the number of elements in the list
      10. public String get(int index) - returns the String at the specified index in the list. This method should throw an IndexOutOfBounds exception if index < 0 or index >= size of the list.
      11. public int indexOf(String s) - returns the index of the first occurrence of the given string, or -1 if the element is not in the list.
      12. public int lastIndexOf(String s) - returns the last index of the given String, returns -1 if not found
      13. public String set(int index, String s) - replaces the element at index with the given string. Return the item that was replaced. If index < 0 or index >= size of the list, this method should throw IndexOutOfBounds exception.
      14. public String remove(int index) - removes the item at the given index and returns it, should throw IndexOutOfBounds exception if index < 0 or index >= size of the list
      15. public boolean remove(String s) - removes the first occurrence of the given string, returns true if successful.
      16. public boolean removeLast(String s) - remove the last occurrence of the given string, return true if successful.
      17. public String[] toArray() - returns an array containing a list of all the strings in the list. The returned array should have a length exactly equal to the size of the list.
    1. Your grade will partially depend on whether the tests outlined in StringLinkedListTester pass when using your StringLinkedList class.

Submission

Please submit your work in an SVN directory https://www.cs.usfca.edu/svn/<username>/cs112/lab8.

Submission Instructions