代写双向循环链表，数据结构中的基础作业。
Requirement
In chapter seven of the textbook is a discussion of the Java LinkedList class.
On Canvas you were given a partial implementation of a SimpleLinkedList class.
Your task is to now modify that code to turn it into a doubly-linked circular
list, to “fill out” the implementation and, of course. to test your new
creation. A doubly-linked list is made up of nodes that contain a reference to
the previous node as well as the next node–allowing for traversal in either
direction.
A circular doubly-linked list has the next reference of the last node refer to
the first node (instead of null), and has the previous reference of the first
node refer to the last node (instead of null)–thus making a circle (a list
with only one node would have both references refer to itself).
The new class should contain all of the same public methods as in
SimpleLinkedList re-written to take advantage of the capabilities of the new
construction. It should be re-written to be zero-based (i.e., theList.get(0)
should return the data in the very first node, if it exists; theList.add(0,
entry) should insert the entry in the very first node, if it exists, etc. ).
It should also be able to take in either negative or non-negative numbers for
a position (i.e., theList.get(-1) should return the data in the very last
node, if it exists, theList.add(-1, entry) should insert the entry in the very
last node, if it exists, etc. Also, an index beyond the size of the list
should be allowed e.g., theList.get(5) for a list of size 4 would return the
same as theList.get(1)). It should also fully impement the listIterator method
(and define the corresponding inner class). In the same spirit, any method
that moves linearly through the list should be optimized so that it will start
at the front or back, depending on which is closer to the index requested
(e.g., if theList has 5 elements, theList.get(1) should start looking from the
front, while theList.get(3) should start looking from the back).
You will also need to make this class implement Iterable, and it should
contain as inner classes both Iterator and ListIterator.. The Iterator should
stop at the end of the list (i.e., hasNext() should return false at the “end”
of the list, although next() would still work), so that it will allow a for
each loop to work; the ListIterator should continue on unless the list is
empty (i.e., hasNext() and hasPrevious()should return true on any non-empty
list). Be sure to fully implement ALL methods for these two classes–including
the “optional” operations.
Finish implementing the following methods:
- addAll(Collection<? extends E> c)
- addAll(int index, Collection<? extends E> c)
- containsAll(Collection<?> c)
- equals(Object o)
- listIterator()
- listIterator(int index)
- remove(Object o)
- set(int index, E element)
- subList(int fromIndex, int toIndex)
- toArray()
- toArray(T[] a)
You may want to change, add, or even eliminate the protected “helper” methods.
Many methods will require only minor modification. Others will require more
thinking (e.g. clear will need a major re-write – you will need to make sure
ALL references in the chain are removed ). You will also need to rewrite the
test driver for the class to test all the methods of the class and nested
classes. This may be a command-line or GUI program–your choice. It should test
all of the methods of the class, either directly or indirectly. It is up to
you how it goes about doing this. You may use any class that makes sense as
the data implementation (CircularDoublyLinkedList<String>works nicely).
Deliverables
Electronic:
- All .class, .jar, .html (javadocs) and .java files. The project will not be graded if source files are missing. Sample Output (as .rtf – run the program, copy the window using [Alt|PrtScn], paste into Wordpad, paste, save.)
- A simple test plan including explanations of any discrepancies and reasons for each test. Show actual input and ALL values output as well as ALL expected output. Test each possible action. Save as .xls, xlsx, .doc or .docx file
- Zip all of the above files together. Do not use rar or any archive format other than zip. Rename the file: “[YourName]_p2.zip”.
- Submit this single zip file by going to Canvas, select this class, select the Assignment tab on the left, select the Assignment 2, select the submission tab at the top, find the file, and Submit.
