代写实现数据结构中的Circular Linked List.
Overview
A circular linked list is essentially a singly linked list in which the next
pointer of the tail node is set to point to the head node of the linked list
rather than set to null. The first figure below shows a linked list as a
singly linked list. The second figure below shows the singly linked list from
the first figure as a circular linked list. In this assignment, you will write
code for an implementation of a circular linked list.
Design
You will write the implementation for the CircularLinkedList class. Download
the files List.java and
CircularLinkedList.java for the framework for the CircularLinkedList class.
You will write the code for all the methods of the CircularLinkedList class
except for the methods:
public boolean add(AnyType newValue)
private Node
—|—
The definition of each method you have to implement in the CircularLinkedList
class:
- void clear() - Remove all values from the list, creating an empty list.
- int size() - Return the number of data values currently in the list.
- boolean isEmpty() - Return true if the list is empty; otherwise return false.
- AnyType get(int index) - Return the data value at position index in the list.
- AnyType set(int index, AnyType newValue) - Return the old data value at position index and replace it with the data value newValue.
- void add(int index, AnyType newValue) - Add data value newValue at the position specified by index; shifting to the right by one position all the values from position index to the end of the list.
- AnyType remove(int index) - Remove and return the data value at position index in the list.
- void rotate() - Moves the value at the head of the list to the tail of the list without removing and adding anything to the list.
- Node getNode(int index, int lower, int upper) - Return the pointer to the node at position index in the list.
If needed, you can write additional methods to help in your implementation of
any method of the CircularLinkedList class but they must be defined as
private. You cannot add any additional data members to the CircularLinkedList
class. You cannot add any nested classes to the CircularLinkedList class.
You cannot modify the nested Node class.
You will also write the code for all the methods of the nested
LinkedListIterator class. The definition of each method you have to implement
in the LinkedListIterator class: - boolean hasNext() - Returns true if the iteration has more elements.
- AnyType next() - Returns the next element in the interation.
- void remove() - Removes from the underlying list the last element returned by the Iterator.
You cannot add any additional data members and methods to the nested
LinkedListIterator class. You cannot add any nested classes to the
LinkedListIterator class.
The input to your program will be read from a plain text file called
assignment1.txt. This is the statement you’ll use to open the file:
FileInputStream fstream = new FileInputStream(“assignment1.txt”);
—|—
Assuming you’re using Eclipse to create your project, you will store the input
file assignment1.txt in the parent directory of your source code (.java files)
which happens to be the main directory of your project in Eclipse. If you’re
using some other development environment, you will have to figure out where to
store the input file.
The input consists of one or more commands (clear, size, is_empty, get, set,
add, add_last, remove, rotate, print_list) with each command on a separate
line. Each command can appear more than once in the input file.
The code you write to implement each command is NOT written in the
CircularLinkedList class but elsewhere in the program. The code for a command
will call the appropriate method of the CircularLinkedList class in order to
accomplish the goal of the command.
Have the output for each command print on a separate line. Print a blank line
after the output printed for the command.
The clear command has your program empty the contents of the circular linked
list and print the message The circular linked list is now empty.
For example: clear
The size command has your program print the number of values in the circular
linked list. For example, if the circular linked list contains 5 strings: size
Prints: The circular linked list contains 5 strings.
The is_empty command has your program print the message The circular linked
list is empty or The circular linked list is not empty.
For example: is_empty
The get command is the word get followed by a space followed by an integer.
The integer in the command is a position number. The get command has your
program print the string at that position in the circular linked list.
For example, if the string at position 5 is New York City: get 5
Prints: The string at position 5 in the circular linked list is “New York
City”.
The set command is the word set followed by a space followed by an integer
followed by a space followed by the rest of the characters on the line, a
string. The integer in the command is a position number. The set command has
your program replace the string at that position in the circular linked list
with the string given in the command.
For example, if the string at position 4 is New York City: set 4 Salt Lake
City
Prints: The string “Salt Lake City” replaces the string “New York City” at
position 4 in the circular linked list.
The add command is the word add followed by a space followed by an integer
followed by a space followed by the rest of the characters on the line, a
string. The integer in the command is a position number. The add command has
your program add that string at that position in the circular linked list.
For example: add 7 San Francisco
Prints: Added the string “San Francisco” at position 7 in the circular linked
list.
The add_last command is the word add_last followed by a space followed by the
rest of the characters on the line, a string. The add_last command has your
program add that string at the end of the circular linked list.
For example: add_last Washington, D.C.
Prints: Added the string “Washington, D.C.” to the end of the circular linked
list.
The remove command is the word remove followed by a space followed by an
integer. The integer in the command is a position number. The remove command
has your program remove the string at that position in the circular linked
list and print out that string.
For example, if the string at position 5 is New York City: remove 5
Prints: Removed the string “New York City” at position 5 from the circular
linked list.
The rotate command has your program move the value at the head of the circular
linked list to the tail of the circular linked list and print the message The
value at the head of the circular linked list was rotated to the tail of the
circular linked list.
For example: rotate
The print_list command has your program print the contents of the circular
linked list. For this command, the program creates an iterator of the circular
linked list and uses the iterator to get and print each string from the
circular linked list. The program prints The circular linked list contains: on
the first line followed by each string in the circular linked list printed on
a separate line.
For example: print_list
Create a driver class and make the name of the driver class Assignment1 and it
should only contain only one method:
public static void main(String args[]).
—|—
The main method will open the file assignment1.txt, create a
CircularLinkedList object which stores strings, and have a loop to process
each command in the file. The main method itself should be fairly short and
will pass the command to another class to perform the command.
Tip: Make your program as modular as possible, not placing all your code in
one .java file. You can create as many classes as you need in addition to the
classes described above. Methods should be reasonably small following the
guidance that “A function should do one thing, and do it well.”
Do NOT use your own packages in your program. If you see the keyword package
on the top line of any of your .java files then you created a package. Create
every .java file in the src folder of your Eclipse project
Do NOT use any graphical user interface code in your program!
