CSSE 230: LinkedLists

• Please ensure your code is well-written and takes maximum advantage of code-reuse.
• Please ensure your code follows the runtime requirements. While I have some test-code that attempts to assess the runtimes, I will inspect all code to verify runtimes.
• The following methods should run in constant time.
  1. boolean add(int e)
  2. void addFirst(int e)
  3. void addLast(int e)
  4. void clear()
  5. T element()
  6. T getFirst()
  7. T getLast()
  8. boolean offer(int e)
  9. boolean offerFirst(int e)
  10. boolean offerLast(int e)
  11. T peek()
  12. T peekFirst()
  13. T peekLast()
  14. T poll()
  15. T pollFirst()
  16. T pollLast()
  17. T pop()
  18. void push(int e)
  19. T remove()
  20. T removeFirst()
  21. T removeLast()
  22. int size()
  23. descendingIterator()
  24. iterator()
  25. hasNext(), next() and remove() in both of the iterators
• The following methods should run at worst in N+1 time
  1. contains(T element)
  2. indexOf(T element)
  3. lastIndexOf(T element)
  4. remove(T element)
  5. removeFirstOccurence(T element)
  6. removeLastOccurence(T element)
  7. toArray()
  8. toString()
  9. clone(), ensure it returns a shallow copy.
• The following methods should run at worst in (N/2)+1 time.
  1. add(int index, T Element)
  2. get(int index)
  3. remove(int index)
• Ensure DoublyLinkedList uses Generics and implements Iterable.
• The iterators should:
  1. Have the remove() method implemented
  2. be fail-fast
  3. throw the proper exceptions
• Here is the unit test code I will be using to score your code. Please ensure your code works with it.