CS210 ALGORITHMS & DATA STRUCTURES I
LABORATORY 5
18
& 25/11/05
Mr. T. Lysaght
LINKED LISTS SELECTION AND
INSERTION SORT
The purpose of this Laboratory session is the implementation of the LINKED
LIST data structure and REVISION of INSERTION SORT.
- Implement a stack data
structure using a linked list. The
StackList class
should use the (non-iterator) code from
LinkedList.java to
implement the stack. The StackList class should
include a new instance variable numItems
to keep count of the number of items in the stack and implement the IsFull() and IsEmpty() methods. The StackList class should add data of type Object in the stack.
- The linked list class in the
Java Library supports operations addLast
and removeLast. To carry out these operations efficiently,
the LinkedList class has an
added reference last
(similar to first) to the last node in the list. Implement a queue data structure using
a linked list by implementing the added method addLast.
- Study the selection sort SelectionSorter.java code on the
public drive in the \CS210\selsort folder and alter the code so that it
begins by finding the largest element and moving it to the end of the
array. Study the code for the StopWatch class and the SelectionSortTimer
class. Run this program on the modified
selection sort class.
- The linked list class in the
Java Library supports bi-directional iterators. To go backwards efficiently, each Node has an added reference, precede, (similar to next)
to the predecessor node in the linked list. Alter the ListIterator
and LinkedList methods to
implement this doubly-linked list by including code for the precede operator. The code for the addFirst and removeFirst methods is given in
the \CS210\linkedlists folder and called Linkedlist_double.
- Modify insertion sort SelectionSorter.java code on the
public drive in the \CS210\insertsort folder to sort an array of Measurable. The InsertionSortTester program
should then sort both an array of Coin
and of BankAccounts.
The classes needed for the program are all in \CS210\insertsort.