CSCI162 - Lab 08 1 Lab 08: Linked List Sequence 1 Objective In this assignment you will get more...

Question

CSCI162 - Lab 08 1 Lab 08: Linked List Sequence 1 Objective In this assignment you will get more practice with linked lists, see another example of implementing an ADT two very different ways, and write a generic class. 2 Setup Create a new Java Project (Lab08). Download the Lab08Files.zip file, unzip it, and place the files it contains into your project’s source folder. You should have the following classes: Sequence An interface like the DoubleSequence that we used in Lab 06, but made generic. LinkedSequence An incomplete class that uses a linked list to store a sequence. You will do all of your work in this class, and this is the one that you will submit to me. TestSeqLL Some unit tests for the LinkedSequence class. These are not the ones that AutoLab uses, but you may find them useful for debugging your own code. SequenceProgram A program that you can also use to interactively test your class. It is a slightly modified version of the class with the same name in Lab 06. 3 Instructions / Specifications Complete the LinkedSequence class:  Do not make any changes to Node, Sequence, or any of the tests – only to LinkedSequence .  Do not add, remove, or rename fields in LinkedSequence.  Do not remove, rename, or alter the headers of any constructors or methods in LinkedSequence .  Do not alter the body of the toString method, but instead read it carefully to understand what it produces. All of my tests will use the output of this method to tell you what it was doing when your class did not work correctly.  Do add yourself as an author to LinkedSequence.  Do read carefully the class invariants for LinkedSequence and the specifications of its methods.  Do not attempt to write any code until you have drawn some diagrams demonstrating what the method should do in every different case. CSCI162 - Lab 08 2  Remember that the class has five fields, and many methods may need to change all of them in different cases.  Consider creating a helper method that adds a new value in between two nodes that are provided as parameters. 4 Grading AutoLab Problem Points Autograded Description 01 structure 1 yes Do you have the correct fields? 02 functionality 89 yes Do the methods work correctly? 03 style 10 partial Is the program written with good style? 5 Submitting Your Work Make sure that you have submitted your final version of your file to AutoLab, and that you have 100/100 autograded points. You do not need to submit your work through D2L – I will look at whatever your last AutoLab submission is.

Arun Shankar · Accepted Answer

/**
 * A sequence implemented using a (singly-) linked list (without dummy nodes).
 * 
 * @author Michael Main, Beth Katz, Chad Hogg, ????? ???
 * @param  The type of element stored in this sequence.
 */
public class LinkedSequence implements Sequence {
	
	/**
	 * A generic node in a single-linked list.
	 * 
	 * @author Michael Main, Beth Katz, Chad Hogg
	 * @param  The type of element stored in the node.
	 */
	public static class Node {
		// Invariant of the Node class:
		//   1. The node's data is in the instance variable data.
		//   2. For the final node of a list, the link is null.
		//      Otherwise, link is a reference to the next node of the list.
		
		/** The element stored in this node. */
		public E value;
		/** A reference to the next node, or null if this is the last one. */
		public Node next;
	   
		/**
		 * Initialize a node with given initial data and link to the next node.
		 * 
		 * The initialNext may be the null reference, which indicates that the
		 *   new node has nothing after it.
		 *   
		 * @param initialValue The initial data of this new node.
		 * @param initialNext A reference to the node after this new node.
		 */
		public Node(E initialValue, Node initialNext) {
			value = initialValue;
			next = initialNext;
		}
	}
	
	// Invariants of the LinkedSequence class:
	// 1. the number of items in the sequence is maintained in size.  
	// 2. head points to the first node, if any, or it is null.
	// 3. tail points to the last node, if any, or it is null.
	// 4. if there is a current item, cursor points to it and
	//    precursor points to the node before it, if any.
	// 5. if there is no current item, cursor and precursor are both null.
	/** A reference to the first node, or null if there are none. */
	private Node head;
	/** A reference to the last node, or null if there are none. */
	private Node tail;
	/** A reference to the current node, or null if there is none. */
	private Node cursor;
	/** A reference to the node before the current node, or null if there is none. */
	private Node precursor;
	/** The number of elements in the sequence. */
	private int size;

CSCI162 - Lab 08 1 Lab 08: Linked List Sequence 1 Objective In this assignment you will get more practice with linked lists, see another example of implementing an ADT two very different ways, and...

Answer To: CSCI162 - Lab 08 1 Lab 08: Linked List Sequence 1 Objective In this assignment you will get more...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment