import java.awt.*;
public class PlayList extends EasyApp
{
public static void main(String[] args)
{
new PlayList();
}
Button bAddFirst = addButton("Add First",50,50,100,50,this);
Button bAddLast = addButton("Add Last",50,100,100,50,this);
Button bShowAll = addButton("Show all",50,150,100,50,this);
Song start = null; // this will point to first NODE in the list
public void actions(Object source,String command)
{
if (source == bAddFirst) { addFirstSong(); }
if (source == bAddLast) { addLastSong(); }
if (source == bShowAll) { showAllSongs(); }
}
public void addFirstSong()
{
Song newSong = new Song(); // make a new NODE
newSong.next = start; // new NODE points to previous start
newSong.title = input("First song title:");
start = newSong; // start now points to new NODE
}
public void addLastSong()
{
Song temp = start; // temp points at first node
while (temp.next != null) // find last node
{
temp = temp.next; // move to next node
}
Song newSong = new Song(); // make a new NODE
newSong.title = input("Last song title:");
temp.next = newSong; // attach new NODE at end of list
}
public void showAllSongs()
{
Song temp = start; // point at first node
while (temp != null) // stop at end of list
{
output(temp.title); // output this title
temp = temp.next; // move to next node
}
}
class Song // this "inner class" is used to hold
{ // a NODE for the list, including
String title = ""; // the TITLE of the song and
Song next = null; // a pointer to NEXT node in the list
}
}
/***********************************************************************
== Song Play List ==
A LINKED-LIST is a data-structure for storing lists of ARBITRARY LENGTH.
The structure is DYNAMIC, meaning the size and structure can be
changed when the program is running. As well as the ability to grow
and shrink to any size, Linked-Lists are very efficient for applications
where there is lots of INSERTING and DELETING.
A Song Play-List for a CD player or MP3 player doesn't really need lots
of storage, but is a simple application requiring a changing list,
including inserting and deleting.
The sample program allows the user to add new songs either at the
beginning or the end of the list. It does not support inserting or
deleting. These methods need to be added.
The method addFirstSong adds songs to the start of the list.
This means the LAST song added is the FIRST played - e.g. LIFO.
So this is like PUSH in a Stack.
The method addLastSong adds songs to the end of the list.
This means the LAST song added will be played last - e.g. FIFO.
This is like ENQUEUE for a Queue.
Here is a picture showing the list as 3 songs are added:
Begin with an empty list : start --x
+ addFirstSong "Jingle" : start --> "Jingle" --x
+ addLastSong "ZZtop" : start --> "Jingle" --> "ZZtop" --x
+ addFirstSong "Help" : start --> "Help" --> "Jingle" --> "ZZtop" --x
The arrows ending with --x indicate a NULL value - it points nowhere.
At the end of the list, the last node points to NULL,
indicating the end of the list.
--------------------------------------------------------------------------
(1) Assume the list now contains the 3 songs shown above.
Predict what the following commands will do (don't run the program):
output( start.title );
output( start.next.title );
output( start.next.next.title);
start.next.title = "Yankee";
start = start.next ;
start.next.next = start;
Node temp = start;
while (temp != null)
{
output(temp.title);
temp = temp.next;
}
(2) The following command should DELETE the FIRST Song:
start = start.next;
This is very similar to the command:
temp = temp.next;
Explain why the "temp" command does NOT delete anything,
whereas the "start" command DOES delete something.
(3) Which of the following code segments correctly DELETES the LAST Song?
Identify the correct code fragment, and explain
why the others do NOT work properly.
(A) while (start != null)
{ start = start.next; }
start.next = null;
(B) Song temp = start;
while (temp != null)
{ temp = temp.next; }
temp.next = null;
(C) Song temp = start;
for (int x=0; x<3; x++)
{ temp = temp.next; }
temp.next = null;
(D) Song temp = start;
while (temp.next.next != null)
{ temp = temp.next; }
temp.next = null;
(4) Assume that the Linked-List contains the 3 words above.
Predict what the Linked-List will contain after these commands:
Song extra = new Song();
extra.title = "Ketchup";
extra.next = start.next.next;
start.next.next = extra;
(5) Fill in the blanks in this code so that it searches for a title
and then prints the NEXT title in the list:
String target = input("Type a title");
_______ temp = start;
while ( !_______________.equals(target) )
{ temp = ____________; }
output( temp.next.title );
What happens if this algorithm runs and the user types
a title that is not found in the list?
(6) Look back at what you did for #5. There is a loop to search through
the list. Now write a TRUNCATE method that searches for a title,
and then removes all the subsequent nodes. It can do this by setting
the NEXT pointer to NULL. Then that's the end of the list, and the
rest of the nodes will be garbage-collected by the Java Virtual Machine.
Now explain why this method CANNOT be used to remove ALL the nodes,
e.g. removing the first node and all subsequent nodes.
(7) This one is a bit trickier. We wish to remove just ONE node.
Let's say it is the node following "Elvis". Then we search for Elvis,
and we change the NEXT node to "jump over" the next node. The command
for this is : temp.next = temp.next.next
(8) Now make a proper DELETENODE method. It should search for a specific
title and delete THAT node, not the following node. This is a bit
tricky. The loop must stop "early", at the node BEFORE the chosen one.
************************************************************************/