Site hosted by Angelfire.com: Build your free website today!
next up previous
Next: CS2012 Lab 2: Timing Up: CS2012. Algorithms and Data Previous: CS2012. Algorithms and Data

Subsections

CS2012 Lab 1: Linked Lists (1 lab session)

Purpose

This is an exercise in programming algorithms for list processing. You will be required to implement Java classes and methods which use a recursively defined Linked List class.

Background

The Linked List, which was introduced in CS1092, is a widely used data structure with the property that data can be inserted at any point in the list. The list grows and diminishes in size as items are added and deleted. Each object in the list consists of a piece of data (an object reference) and a reference (or pointer) to the next object in the list, as shown below. You should define a class ListNode, to implement such objects.

\includegraphics[width=0.6\textwidth]{fig/listnodes}

Adding an element to the front of such a list is done as shown below,

\includegraphics[width=0.8\textwidth]{fig/add}

Note that an insertion at the front of the list will always modify the value of the reference to the first element in the list (denoted in the diagrams by front). This means that, if the method were to be called add, we would have to invoke it as
\begin{alltt}
front = front.add(''five'');
\end{alltt}

In order to create an object which encapsulates the list we need to introduce a LinkedList object, which contains a reference to a ListNode, giving the structure shown below:-

If an object of this type were called list1, we could then safely write
\begin{alltt}
list1.add(''five'');
\end{alltt}
since the value of list1 would not be modified by the insertion, merely the value of one its instance variables.

\includegraphics[width=0.8\textwidth]{fig/llist}

Insertion of a new ListNode into the middle of a list is done by manipulating pointers as shown below:-

\includegraphics[width=0.8\textwidth]{fig/insert}

Tasks

You are required to implement the classes ListNode and LinkedList together with the following methods in the LinkedList class, all of which should be suitably tested.

  1. isEmpty - tests whether a list is empty; returns boolean

  2. add - adds a new entry at the front of the list, containing a reference to the Object x; return type void.

  3. makeEmpty - makes an existing list empty; return type void.

  4. printList - prints the contents of the list. You can choose the exact format to be used; return type void.

  5. remove - remove the first occurrence in the list of an entry containing a reference to an object equal to the Object x; return type void.

  6. removeAll - remove all occurrences in the list of entries containing a reference to an object equal to to the Object x; return type void.

  7. addLast - adds a new entry at the end of the list, containing a reference to the Object x; return type void. (You may want to consider a modification of the class definition to optimise this operation.)

  8. addAfter - adds a new entry containing a reference to the Object x after the first occurrence of an element containing a reference to the Object y (or at the end of the list if no such occurrence exists); return type void.

  9. append - appends the contents of the LinkedList other to the end of the list; return type void.

  10. printListRev - prints the contents of the list in reverse order; return type void. This must be implemented without modifying the internal structure of the list (Hint: think recursion)

Marking scheme

Class structure 2
isEmpty, makeEmpty 2
add, addLast, addAfter 3
remove, removeAll 2
append 1
printList, printListRev 2
Suitable tests 3
Total 15


next up previous
Next: CS2012 Lab 2: Timing Up: CS2012. Algorithms and Data Previous: CS2012. Algorithms and Data
Graham Gough
2004-04-30