COMP251 - Week3 - Lab
Jan 18, 2016
Goal: This lab will give you practice with linked lists.
Getting Started
You can have a partner for this lab, but make sure to submit to blackboard individually.
Downloadthefilesforthislabfromblackboard.ClassesSListandSListNodeimplement
a singly-linkedlist. CreateanemptyprojectinEclipseandcallit‘SList’.Addclasses:
SList, SListNode and TestHelper.
Run the test code with.
Themain()methodofSListincludestestcode,whichcanbeusedtohelpdebugthe
list code before SLists are used in other programs.
ReadSList.javatofindoutwhatmethodsareavailabletohelpyoumodifySLists.Items
in our SLists are indexed starting from 1, unlike Java arrays.
Part I: Using SLists (15 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 (45 points)
--------------------------------------------------
AmethodcalledinsertEnd()exists,butitrunsinlineartime,becauseeverytimeitis
called,it walksdownthelistto findtheend. Withoutchangingthemeaningofthis
methodoranyother,modifytherepresentationofa SListandwhatevermethodsare
necessary to make insertEnd() run in constant time.
YourSListclasswillneedtocontinuallymaintainarecordofthelast(tail)SListNodein
an SList, and all SList's methods will have to ensure that this record stays current.
Check-off
---------
ShowyourInstructororLabAssistantyourmain()andinsertEnd()methodsand
run the program.
1 point: your main() should print the proper output for Part I.
3 points:yourinsertEnd()methodshouldworkin constanttime.Yourprogram
shouldstillprinttherightoutput(Youcanusetestcodeinthemain()methodofSList
-- testEmpty(), testAfterInsertFront(), testAfterInsertEnd()-- to test
your solution). Which other methods had to be modified?
Submission
---------
Create a single zip file of your project, submit to blackboard individually .