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.

 

  1. 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.

 

  1. 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.

 

  1. 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.

 

  1. 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.

 

  1. 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.