HL Mastery aspects:

Linked lists

ADT's

output each node's contents into the TextArea, one at a time.

The earth symbol is sometimes used to indicate a null pointer.

In Node represenations, often a diagonal bar is put through the reference field:

Applet source code

StudentRecordNode source code

On this page: [ example list | Applet ]

The Linked List Using Object References

Using the object reference together with a record type Class allows the formation of lists linked by their reference fields:

A typical Class for defining such a linked list could be:

/**
* StudentRecordNode.java
*
* @author Mr J
* @version 20050205
*/
class StudentRecordNode
{
   // data members of the class, just a couple for illustration
   // more members using more types can easily be added
   private String name;
   private String tutor;
   // The field that links nodes together.
   private StudentRecordNode next;

   public StudentRecordNode( )
   {
     // default constructor, sets fields to null
     name = null;
     tutor = null;
     next = null;
   }
   public StudentRecordNode(String nm, String tr, StudentRecordNode nx )
   {
     // Second Constructor for a student record, assigns fields
     setName(nm);
     setTutor(tr);
     setNext(nx);
   }
   // accessor methods
   public String getName() {return name;}
   public StudentRecordNode getNext(){ return next;}
   public String getTutor(){return tutor;}
   // mutator methods
   public void setName( String nm ) {name = nm;}
   public void setNext( StudentRecordNode n){next = n;}
   public void setTutor( String tr ){tutor = tr;}
}

Back to top

A linked list of Student Nodes

The use of this linked record structure to construct a list of linked student object instances is illustrated in the following Applet:

public class StudentList extends Applet implements ActionListener
{
   // Using a defined StudentRecordNode class
  private StudentRecordNode root; // first item in list;
  TextArea textWindow =
             new TextArea("This is where the outputs will appear\n", 20, 30);
   // fields and labels for data entry
   Label nameLabel = new Label("Student name: ");
   Label tutorLabel = new Label("Tutor group: ");
   TextField nameField = new TextField(30);
   TextField tutorField = new TextField( 3);
   // action buttons
   Button addButton = new Button("Add");
   Button lstButton = new Button("List");
   /**
   * This method sets up the GUI objects
   */
   public void init()
   {
     addButton.addActionListener(this);
     lstButton.addActionListener(this);
     // text objects
     add(nameLabel);
     add(nameField);
     add(tutorLabel);
     add(tutorField);

    add(addButton);
     add(lstButton);

    add(textWindow);
   }
   /**
   * This method detects button events
   *
   * @param ActionEvent - the action that triggered the call to this method
   */
   public void actionPerformed(ActionEvent e)
   {
     // React to the button presses
     if (e.getSource() == addButton)
     {
       addNode();
     }
     else
     {
       displayList();
     }
   }
   /**
   * Adds a node to the head of the linked list
   */
   public void addNode()
   {
     // create a new node using the constructor of Class StudentRecordNode
     // this node has its reference field pointed to root
     StudentRecordNode theNode = new StudentRecordNode( nameField.getText(),
                                                        tutorField.getText(),
                                                        root );
     // now we point the root pointer to this node
     root = theNode;
     // clear the fields of text for convenience
     nameField.setText("");
     tutorField.setText("");
     // put the cursor in the name field
     nameField.requestFocus();
   }
   /**
   * A method to display the linked list of nodes in the text area window
   */
   public void displayList()
   {
     // a temporary pointer to hold the reference of each node
     // of the list in turn
     StudentRecordNode temp;
     int numInList=1;
     // start at the root
     temp = root;
     textWindow.append( "\n head of list \n ------------\n" );
     // "walk" down the list, using the temp pointer
     while (temp != null)
     {
       textWindow.append( "Number: " + numInList++ + "\n" );
       textWindow.append( "Name: " + temp.getName() + "\n" );
       textWindow.append( "Tutor: " + temp.getTutor() + "\n" );
       textWindow.append( "\n--------------------\n" );
       temp = temp.getNext();
     }
   }
}

Back to top

The Applet:

At the start of the program, root points to null:

Suppose "Fred" and "Xyz" are in the text boxes (nameField and tutorField), we now have a new StudentRecordNode object created in memory:

      StudentRecordNode theNode = new StudentRecordNode( nameField.getText(),                                                        tutorField.getText(),   
                                                       root );

Later on in the program, root will be pointing to an existing list of nodes, so effectively we have now added this node to the head. However, it remains to point root back to this node as it is now the first in the list, so we use the line:

  // now we point the root pointer to this node
     root = theNode;

To prove that it really does work, the linked list is displayed in a TextArea. Notice the way that this methods "walks" down the list starting at root. It uses a temp reference to point to each object in turn. One has to take care with methods that access linked lists, always use a while loop so that you don't generate an error when accessing an empty list (the root pointer is still null).

The program as it stands is incomplete, in particular, nodes can only be added and not removed. Also nodes can only be added at the head (front, root) of the list. The following exercises will (hopefully) help your understanding of these useful structures:

Back to top

Exercises

Add a new button and method to remove a node from the head of the list. Be careful to check that the list is not empty first!

Try adding/removing nodes at the tail of the list instead of the head. You can use a method similar to displayList to get to the end node.

 Back to top

Related: [ Java home | data structures home | Next: more lists ]

This structure is called a node .

A list of linked nodes.

A Flash movie illustrating adding to the head of a linked list.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.