//-- Linked List ----------------------------------------------------
// A very simple linked-list program, which adds nodes to the list
// and displays them. It does nothing useful - it's only a demo.
//-------------------------------------------------------------------
import java.awt.*;
import java.awt.event.*;
public class LinkList extends EasyApp
{
public static void main(String[] args)
{ new LinkList(); }
Button bFirstNode = addButton("First Word",40,50,100,50,this);
Button bAddNode = addButton("Add Word",40,100,100,50,this);
Button bShowHead = addButton("Show Head",40,150,100,50,this);
Button bShowTail = addButton("Show Tail",40,200,100,50,this);
Button bShowList = addButton("Show List",40,250,100,50,this);
Button bQuit = addButton("Quit",40,300,100,50,this);
public LinkList()
{ bQuit.setBackground(Color.red);
setSize(200,400);
setVisible(true);
}
public void actions(Object source,String command)
{
if (source == bQuit){ System.exit(0); }
else if (source == bFirstNode) { firstNode();}
else if (source == bAddNode ) { addNode(); }
else if (source == bShowList ) { showList(); }
else if (source == bShowHead ) { showHead(); }
else if (source == bShowTail ) { showTail(); }
}
//-- Pointers Head,Tail --//
Node head = null; // Points to first node in Linked-List
Node tail = null; // Points to last node in Linked-List
//-- NODE inner class --//
class Node // INNER class - used as a "record" structure
{ String name=""; // USER-DEVINED data-structure
int age=0;
Node next;
}
//-- firstNode method --------------------------------------------
// Initialize list with a single node.
//----------------------------------------------------------------
public void firstNode()
{ head = new Node(); // Allocates memory, returns ADDRESS (number)
head.next = null;
String word = input("First word");
head.name = word;
tail = head;
}
//-- addNode method ----------------------------------------------
// Adds a new node, attaching it after the TAIL node.
//----------------------------------------------------------------
public void addNode() // EVERY TIME YOU CREATE A NEW NODE
{ tail.next = new Node(); // set NEXT to equal NULL
tail.next.next = null;
tail = tail.next;
tail.name = input("Another word");
}
public void showHead() // Prints the first node in the list
{ output( head.name );
}
public void showTail() // displays the last node in the list
{ output( tail.name );
}
//--- showList ---------------------------------------------------
// Prints the entire list. A temporary pointer must start at the
// HEAD node, then move along to each node.
// The loop stops when TEMP equals null - after the last node.
//----------------------------------------------------------------
public void showList()
{ Node temp = head;
do
{ output( temp.name );
temp = temp.next;
} while ( temp != null );
}
}
/******************************************************
Simple Linked-List
In this simple Linked-List program, HEAD points at the first node
in the list, and TAIL points at the last node in the list.
This makes it easier to add a new node at the end -
it is not necessary to TRAVERSE the list searching for the end.
Inserting
Linked-Lists are useful because INSERTING a node in the middle of
the list is more efficent than INSERTING a new cell in an array.
In an array, the program must SEARCH for the correct position,
and then it must MOVE each following cell ahead one position
before inserting the new item.
In a Linked-List, the program must search for the correct position,
but inserting is done by changing the pointers - it is not necessary
to PHYSICALLY move the subsequent items.
Of course, it only makes sense to INSERT a node in a specific
position if the list is SORTED. That might be alphabetical,
or by date, or size, or any other order.
(1) Change the INPUT method so that it inputs both the name and the age.
Then change all the output methods to print both name and age.
(2) Write a method called CheckAgeSorted that checks whether the
.age fields are in order, from smallest to largest.
It should return a boolean value - true means the list is sorted.
Since duplicate ages are likely, it is okay if two nodes
have the same age, but a following node cannot be smaller
than the previous node. You will need a command similar to:
if (temp.age > temp.next.age)
{ sorted = false; }
You also need some more commands, like a loop to TRAVERSE all
the nodes (using temp = temp.next;).
(3) Explain why the following code will NOT correctly INSERT a node
into the list directly following the name "FRED":
Node temp = head;
Node gNode = new Node();
gNode.name = "GRETA";
while (!temp.equals("FRED"))
{ temp = temp.next; }
temp.next = gNode;
gNode.next = temp.next;
(4) ASSUMING the list is sorted by .age, write a method that will
input a new node and then INSERT that node into the list in
the correct position.
(5) Explain why the following code will NOT correct DELETE the
node following "FRED":
Node temp = head;
while (!temp.equals("FRED"))
{ temp = temp.next; }
temp.next.name = "";
(6) Write a method to DELETE a node. This must input the .name,
search for that name in the list, and then remove the node by
executing a command similar to this:
temp.next = temp.next.next;
Of course that only works if TEMP is pointing to the node BEFORE
the one you wish to delete.
(7) The showList() method THROWS an EXCEPTION when the list is empty -
that is, if head is equal to null. Add an IF command to prevent
this error from occuring.
(8) All the methods are susceptible to errors at the ENDS of the list.
For example, you may need to INSERT a new node BEFORE the first node,
or after the last node. These "special cases" might not work the same
as the standard insert-in-the-middle case. You need to clean up
your code by HANDLING all the unusual cases, thus preventing errors.
A proper Linked-List ADT would ENCAPSULATE all these methods (and more)
into a separate class, so that it can be RE-USED to make lots of
linked-lists. For the HL dossier project, you need to create an ADT of
some sort. A linked-list is not the easiest, but is generally pretty
useful, and writing the code is the best way to learn DYNAMIC programming.
As you are thinking about your project, try to identify some DATA that
could be stored in a Linked-List, Stack, or Queue. This is still in the
future, but if you think of something now go ahead and write it down so
you don't forget.
*******************************************************/