Description
In this assignment, you extend the doubly linked list class DList given in the textbook. The subclass is named MyDlist.
You need to implement the following constructors and methods of MyDlist:
1. public MyDlist(). This constructor creates an empty doubly linked list.
2. public MyDlist(String f). This constructor creates a doubly linked list by reading all strings from a text file
named f. Assume that adjacent strings in the file f are separated by one or more white space characters. If f is
“stdin”, MyDlist(“stdin”) creates a doubly linked list by reading all strings from the standard input. Assume
that each input line is a string and an empty line denotes end of input.
3. public static void printList(MyDlist u). This class method prints all elements of a list on the standard output,
one element per line.
4. public static MyDlist cloneList(MyDlist u). This class method creates an identical copy of a doubly linked list
u and returns the resulting doubly linked list.
5. public static MyDlist union(MyDlist u, MyDlist v). This class method computes the union of the two sets that
are stored in the doubly linked lists u and v, respectively, and returns a doubly linked list that stores the union.
Each element of a set is stored in a node of the corresponding doubly linked list. Given two sets A and B, the
union of A and B is a set that contains all the distinct element of A and B. Include the detailed time complexity
analysis of this method in big O notation immediately above the source code of this method as comments.
6. public static MyDlist intersection(MyDlist u, MyDlist v). This class method computes the intersection of the
two sets that are stored in the doubly linked lists u and v, respectively, and returns a doubly linked list that
stores the intersection. Each element of a set is stored in a node of the corresponding doubly linked list.
Given
two sets A and B, the intersection of A and B is a set that contains all the elements of A that are also in B.
Include the detailed time complexity analysis of this method in big O notation immediately above the source
code of this method as comments.
You may assume that in the above methods all the elements of each input set are distinct.
You are not allowed to use any data structures of Java you have not learned so far. In other words, you can use only
the arrays, strings and primitive data types of Java.
Major steps
1. Download the latest JAVA IDE Eclipse.
2. Create a project.
3. Create DList class and copy the code of DList to the class file.
4. Create DNode class and copy the code of DNode to the class file.
5. Create MyDlist class, and copy the sample main method to the class file.
How to submit your code?
Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php? Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn1.
3. Submit your MyDlist.java file that contains only the class MyDlist.
Marking
The full mark of this assignment is 6. Marking is based on the correctness and efficiency of your code. Your code must
be well commented.
Deadline
The deadline is 11:59:59 pm, 1 April.
Late submission
No late submission will be accepted.