Insertion Sort #2

12 points

Recall that an insertion sort performs a sort by correctly inserting one element at a time into a list.  For example, these 6 names are sorted through insertion sort:
Paul
Paul Steven
Beth Paul Steven
Beth Mary Paul Steven
Beth David Mary Paul Steven
Beth David Mary Paul Steven Zack

You may do an insertion sort when you're playing cards.  You may correctly position each card in your hand as it is dealt to you.

In this program, you generate a series of names.  Then you perform an insertion sort into a linked list, so that the names stored in the linked list are in alphabetical order.

Here is the output from my program, a printing of the names stored in the sorted linked list:

Delhi Beth A
Delhi Beth F
Delhi Beth R
Delhi Beth X
Delhi Jorge A
Delhi Jorge F
Delhi Jorge R
Delhi Jorge X
Delhi Paul A
Delhi Paul F
Delhi Paul R
Delhi Paul X
Delhi Steven A
Delhi Steven F
Delhi Steven R
Delhi Steven X
London Beth A
London Beth F
London Beth R
London Beth X
London Jorge A
London Jorge F
London Jorge R
London Jorge X
London Paul A
London Paul F
London Paul R
London Paul X
London Steven A
London Steven F
London Steven R
London Steven X
Paris Beth A
Paris Beth F
Paris Beth R
Paris Beth X
Paris Jorge A
Paris Jorge F
Paris Jorge R
Paris Jorge X
Paris Paul A
Paris Paul F
Paris Paul R
Paris Paul X
Paris Steven A
Paris Steven F
Paris Steven R
Paris Steven X
Rome Beth A
Rome Beth F
Rome Beth R
Rome Beth X
Rome Jorge A
Rome Jorge F
Rome Jorge R
Rome Jorge X
Rome Paul A
Rome Paul F
Rome Paul R
Rome Paul X
Rome Steven A
Rome Steven F
Rome Steven R
Rome Steven X

Starting Point

You can download PhoneList2.java to use as a starting point in writing your program. (Right-click on the link, choose 'Save Target As' and add the '.java' extension to the file name.)  PhoneList2.java contains instructions on writing code. To generate a linked list, you can just use the LinkedList class that is a part of the Java library.

Thanks to Ian Fairclough '15 for his help with this program.