Java程序辅导

G52APR Lab 
13/10/2011 – version 1.1 
 
The linked list is a simple and commonly used data structure. A linked list consists of a group of 
nodes, each of which stores some value of data, and a pointer to the next node in the list. (The 
nodes of a doubly linked list additionally each have a pointer to the previous node in the list; linked 
lists without this backwards pointer are known as singly linked.) 
Linked lists are advantageous in that they allow arbitrary (and fast) insertion and deletion of nodes, 
unlike arrays, where, if you want to insert a value near the start of the array, you must shift each 
subsequent value back a place. In a linked list, you can simply point the preceding node at the new 
one, and the new node at the node to which the preceding node used to point. 
If, however, you wish to access the 1000th element of a linked list, you must traverse through each 
element from the head of the list until you reach it. In an array, which is stored contiguously in 
memory, accessing arbitrary elements is very fast, as it is simply a case of calculating an offset of 
1000 (say) ints. 
In any case, the fast insertion and deletion properties of linked lists make them particularly 
amenable for simulating stacks and queues: nodes can be inserted and removed at both ends of the 
list, allowing both FIFO (queue) and LIFO (stack) behaviour. 
Part 1 
A simple linked list implementation has been provided for you at 
http://cs.nott.ac.uk/~azp/teaching/intlist.zip 
Note that it may contain bugs! This is a doubly linked list that stores Integers. A simple test 
program is provided for you in LinkedListTest.java, which creates a new LinkedList object, 
inserts 10,000 random numbers, and prints the list to the console. It then calls the LinkedList’s 
sort method, and prints the list again. 
Currently the sort method is not implemented – your first task, after familiarising yourself with the 
three provided classes, is to implement a method to sort the list. 
The algorithm you use is entirely your choice (although I recommend avoiding bogosort – see 
Wikipedia). The simplest, although far from best way is to use bubble sort (again see Wikipedia), 
where you simply swap pairs of elements if they are in the wrong order. Another reasonably simple 
algorithm is insertion sort, where you take one element at a time, and insert it in the correct place in 
a new list. This will probably require you to create a new insertion method in the LinkedList 
class, called something like insertSorted, which assumes the list is already sorted, and when 
inserting elements, traverses through the list and inserts the element in the correct place. More 
complex (but more efficient) algorithms such as merge sort or quicksort may be useful too.  
Part 2 
One shortcoming of the approach used by the classes provided is that it can only store Integers. It 
would be nice if we could use it to store any type of object, eg Doubles, Strings etc. 
In fact, with Java this is not too tricky, using a thing called generics. One thing to bear in mind is that 
if we are to have a sort method, we must ensure that any objects we allow in the linked list can be 
ordered. Java has an interface called Comparable which guarantees that any class that 
implements it has a compareTo method.  
You may find http://download.oracle.com/javase/7/docs/api/java/lang/Comparable.html useful. 
An updated version of the classes you have already seen is available at 
http://cs.nott.ac.uk/~azp/teaching/genericlist.zip 
This has updated the class to be generic, but to only allow comparable objects. (Note that you will 
need to update your sort method to make it generic – in particular, anywhere you refer to 
LinkedListNode should now read LinkedListNode. Also, ensure you use compareTo 
to compare the values of elements, rather than, say <.) The test class now imports a list of randomly 
ordered words (from sowpods-random.txt, provided in the zip file), inserting them one at a 
time into a list. Again, it prints the list, sorts it, and prints it again. If you have implemented bubble 
sort or insertion sort, you will probably find it’s painfully slow, as the text file contains approximately 
270,000 words (the entire official scrabble dictionary). You could either use a subset of the text file 
to test, or implement a more efficient sorting algorithm.