Computer data structure. Please Help!!!

CIS 256 Lab 1

The files in the directory lab1/ contain the classes SList and SListNode, which

implement a singly-linked list. Compile SList.java with "javac -g SList.java".

Run the test code with

java SList

The main() method of SList includes test code, which can be used to help debug

the list code before SLists are used in other programs.

Read SList.java to find out what methods are available to help you modify

SLists. Items in our SLists are indexed starting from 1, unlike Java arrays.

Part I: Using SLists (1 point)

-------------------------------

In the main() method, construct a list that looks like:

[ 6 9 12 ]

and print the resulting list.

Add more lines to change this list to:

[ 3 6 9 12 15 ]

and print the resulting list.

Part II: Adding to the End of a SList (3 points)

--------------------------------------------------

A method called insertEnd() exists, but it runs in linear time, because every

time it is called, it walks down the list to find the end. Without changing

the meaning of this method or any other, modify the representation of a SList

and whatever methods are necessary to make insertEnd() run in constant time.

Your SList class will need to continually maintain a record of the last (tail)

SListNode in an SList, and all SList's methods will have to ensure that this

record stays current.

Check-off

---------

Show your main() and insertEnd() methods and run the

program.

1 point: Show your main() method, and show that it is printing the proper

output for Part I.

3 points: Show your insertEnd() method, and explain how you got it to work in

constant time. Show that your program still prints the right

output. Which other methods had to be modified?

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

* SList.java

/* SList.java */

/** * The SList class is a singly-linked implementation of the linked list * abstraction. SLists are mutable data structures, which can grow at either * end. * * @author Kathy Yelick and Jonathan Shewchuk **/

public class SList {

private SListNode head; private int size;

/** * SList() constructs an empty list. **/

public SList() { size = 0; head = null; }

/** * isEmpty() indicates whether the list is empty. * @return true if the list is empty, false otherwise. **/

public boolean isEmpty() { return size == 0; }

/** * length() returns the length of this list. * @return the length of this list. **/

public int length() { return size; }

/** * insertFront() inserts item "obj" at the beginning of this list. * @param obj the item to be inserted. **/

public void insertFront(Object obj) { head = new SListNode(obj, head); size++; }

/** * insertEnd() inserts item "obj" at the end of this list. * @param obj the item to be inserted. **/

public void insertEnd(Object obj) { if (head == null) { head = new SListNode(obj); } else { SListNode node = head; while (node.next != null) { node = node.next; } node.next = new SListNode(obj); } size++; }

/** * nth() returns the item at the specified position. If position < 1 or * position > this.length(), null is returned. Otherwise, the item at * position "position" is returned. The list does not change. * @param position the desired position, from 1 to length(), in the list. * @return the item at the given position in the list. **/

public Object nth(int position) { SListNode currentNode;

if ((position < 1) || (head == null)) { return null; } else { currentNode = head; while (position > 1) { currentNode = currentNode.next; if (currentNode == null) { return null; } position--; } return currentNode.item; } }

/** * toString() converts the list to a String. * @return a String representation of the list. **/

public String toString() { int i; Object obj; String result = "[ ";

SListNode cur = head;

while (cur != null) { obj = cur.item; result = result + obj.toString() + " "; cur = cur.next; } result = result + "]"; return result; }

/** * main() runs test cases on the SList class. Prints summary * information on basic operations and halts with an error (and a stack * trace) if any of the tests fail. **/

public static void main (String[] args) { // Fill in your solution for Part I here. System.out.println("Kamran Eftekhari"); //testEmpty(); //testAfterInsertFront(); //testAfterInsertEnd(); }

/** * testEmpty() tests toString(), isEmpty(), length(), insertFront(), and * insertEnd() on an empty list. Prints summary information of the tests * and halts the program if errors are detected. **/

private static void testEmpty() { SList lst1 = new SList(); SList lst2 = new SList(); System.out.println(); System.out.println("Here is a list after construction: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ ]"), "toString on newly constructed list failed");

System.out.println("isEmpty() should be true. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == true, "isEmpty() on newly constructed list failed");

System.out.println("length() should be 0. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 0, "length on newly constructed list failed"); lst1.insertFront(new Integer(3)); System.out.println("Here is a list after insertFront(3) to an empty list: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 3 ]"), "InsertFront on empty list failed"); lst2.insertEnd(new Integer(5)); System.out.println("Here is a list after insertEnd(5) on an empty list: " + lst2.toString()); TestHelper.verify(lst2.toString().equals("[ 5 ]"), "insertEnd on empty list failed"); }

/** * testAfterInsertFront() tests toString(), isEmpty(), length(), * insertFront(), and insertEnd() after insertFront(). Prints summary * information of the tests and halts the program if errors are detected. **/

private static void testAfterInsertFront() { SList lst1 = new SList(); lst1.insertFront(new Integer(3)); lst1.insertFront(new Integer(2)); lst1.insertFront(new Integer(1)); System.out.println(); System.out.println("Here is a list after insertFront 3, 2, 1: " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 1 2 3 ]"), "InsertFronts on non-empty list failed"); System.out.println("isEmpty() should be false. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == false, "isEmpty() after insertFront failed"); System.out.println("length() should be 3. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 3, "length() after insertFront failed"); lst1.insertEnd(new Integer(4)); System.out.println("Here is the same list after insertEnd(4): " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 1 2 3 4 ]"), "insertEnd on non-empty list failed"); }

/** * testAfterInsertEnd() tests toString(), isEmpty(), length(), * insertFront(), and insertEnd() after insertEnd(). Prints summary * information of the tests and halts the program if errors are detected. **/

private static void testAfterInsertEnd() { SList lst1 = new SList(); lst1.insertEnd(new Integer(6)); lst1.insertEnd(new Integer(7)); System.out.println(); System.out.println("Here is a list after insertEnd 6, 7: " + lst1.toString()); System.out.println("isEmpty() should be false. It is: " + lst1.isEmpty()); TestHelper.verify(lst1.isEmpty() == false, "isEmpty() after insertEnd failed"); System.out.println("length() should be 2. It is: " + lst1.length()); TestHelper.verify(lst1.length() == 2, "length() after insertEndfailed"); lst1.insertFront(new Integer(5)); System.out.println("Here is the same list after insertFront(5): " + lst1.toString()); TestHelper.verify(lst1.toString().equals("[ 5 6 7 ]"), "insertFront after insertEnd failed"); } }

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

* SListnode.java

/* SListNode.java */

/** * SListNode is a class used internally by the SList class. An SList object * is a singly-linked list, and an SListNode is a node of a singly-linked * list. Each SListNode has two references: one to an object, and one to * the next node in the list. * * @author Kathy Yelick and Jonathan Shewchuk */

class SListNode { Object item; SListNode next;

/** * SListNode() (with one parameter) constructs a list node referencing the * item "obj". */

SListNode(Object obj) { item = obj; next = null; }

/** * SListNode() (with two parameters) constructs a list node referencing the * item "obj", whose next list node is to be "next". */

SListNode(Object obj, SListNode next) { item = obj; this.next = next; }

}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

* TestHelper.java

/* TestHelper.java */

/** * This class is based on code from Arnow/Dexter/Weiss. Its verify() method * exits with an error message if an invariant fails to hold true. * * The purpose of this class is to provide a shorthand for writing and testing * invariants in any program. **/

public class TestHelper {

/** * verify() checks an invariant and prints an error message if it fails. * If invariant is true, this method does nothing. If invariant is false, * the message is printed, followed by a dump of the program call stack. * * @param invariant the condition to be verified * @param message the error message to be printed if the invariant fails to * hold true. **/

static void verify(boolean invariant, String message) { if (!invariant) { System.out.println("*** ERROR: " + message); Thread.dumpStack(); } } }