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.
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.
Adding an element to the front of such a list is done as shown below,
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
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
since the value of list1 would not be modified by the insertion, merely the value of one its instance variables.
Insertion of a new ListNode into the middle of a list is done by manipulating pointers as shown below:-
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.
|add, addLast, addAfter||3|