HL Mastery aspect:

ADT's

Compare the code for this Class with that of the StudenRecordNode.

This Class has only one data field - it could have more.

DoubleNode.java
source code

NameList.java
source code

The Applet does not do a lot. It allows you to add names to the list and then move a pointer to the currently selected.

This uses the setNext() and setPrevious() methods of the DoubleNode Class.

You could modify it easily to highlight the selected item in a different colour or with a coloured background.

It would be useful, for example, for presenting a set of search results then allowing the user to select one.

Here we will flag the display routine that next or previous was pressed and move to the appropriate node before displaying the list.

Strictly speaking it's not the best idea to get one method to do two tasks but, hey, everyone has lazy days :-)

next button was pressed, move current to next node (if it exists)

same deal for previous button.

as before

except for marking the current item

Here is where you could add some color/colour.

If you know where the tail is, the head is always given by tail.getNext(), providing there is at least 1 item in the list.

FileNode.java
source code

OrderedList.java
source code

Notice how we split of the adding parts into their own methods to make this part of the code simpler.

A better approach would be to create a Class with all of the required methods.

This would satisfy the mastery of ADT's requirement.

Now that you have seen this example you should be able to add nodes in order to the doubly-linked list.

This could be worth up to 4 mastery factors.

On this page: [ doubly-linked lists | NameList Applet | Circular List ]

Doubly -linked list

A simple modification of the Node Structure allows a reference field to point to the previous node as well as one pointing to the next:

In Java, the class might look like this:

/**
* DoubleNode.java
*
* @author Mr J
* @version 20050208
*/
class DoubleNode
{
   // data member
   private String name;

  // The fields that links nodes together.
   private DoubleNode next;
   private DoubleNode prev;

  public DoubleNode( )
   {
     // default constructor, sets fields to null
     name = null;
     next = null;
     prev = null;
   }
   public DoubleNode(String nm, DoubleNode nx, DoubleNode pv)
   {
     // Second Constructor for a student record, assigns fields
     setName(nm);
     setNext(nx);
     setPrev(pv);
   }
   // accessor methods
   public String getName() {return name;}
   public DoubleNode getNext(){ return next;}
   public DoubleNode getPrev(){ return prev;}
   // mutator methods
   public void setName( String nm ) {name = nm;}
   public void setNext( DoubleNode n){next = n;}
   public void setPrev( DoubleNode p){prev = p;}
}

Back to top

NameList Applet

Back to top

Applet Code

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
/**
* Demonstrates use of a doubly-linked list
*
* @author Mr J
* @version 20050208
*/
public class NameList extends Applet implements ActionListener
{
   // GUI objects
   private TextField name = new TextField("Type a name here!");
   private Button add = new Button("Add name");
   private Button next = new Button("Next");
   private Button prev = new Button("Previous");
   private TextArea display = new TextArea(20, 30);
   private Label messages = new Label("Messages will appear here");

  // data members
   DoubleNode head = null;
   DoubleNode current = null;

   /**
   * Add objects to the Applet
   */
   public void init()
   {
     add(name);
     add(add);
     add(next);
     add(prev);
     add(display);
     add(display);
     add(messages);
     // Causes button presses to be detected
     add.addActionListener(this);
     next.addActionListener(this);
     prev.addActionListener(this);
   }
   /**
   * When an event occurs on an object with an ActionListener attached, this
   * method is carried out.
   *
   * @param e carries details about the event that occurred
   */
   public void actionPerformed(ActionEvent e)
   {
     messages.setText("");
     // Check the button presses
     if (e.getSource() == add)
     {
       addName();
     }
     else if (e.getSource() == next)
     {
       displayList( 1 );
     }
     else
     {
       displayList( -1 );
     }
   }
   public void addName()
   {
     // get the name and create a new node at the head
     String theName = name.getText();
     DoubleNode newOne = new DoubleNode( theName, head, null);
     // if head is pointing to a node, set it's previous pointer
     if (head != null)
     {
       head.setPrev(newOne);
     }
     head = newOne;
     // if no currently selected name, point to head
     if (current == null)
     {
       current = head;
     }
     displayList( 0 );
   }
   public void displayList(int move)
   {
     display.setText("start\n-----\n");
     // Move the currently selected, if required
     if (move == 1)
     {
       if (current.getNext() != null)
       {
         current = current.getNext();
       }
       else
       {
         messages.setText("At last name");
       }
     }
     else if (move == -1)
     {
       if (current.getPrev() != null)
       {
         current = current.getPrev();
       }
       else
       {
         messages.setText("At first name");
       }
     }
     DoubleNode temp = head;
     // "walk" down the list, using the temp pointer
     while (temp != null)
     {
       if (temp == current)
       {
         display.append(temp.getName() + "<< current\n");
       }
       else
       {
         display.append(temp.getName() + "\n");
       }
       temp = temp.getNext();
     }
   }
}

Back to top

Exercises

Add a new nodes to the tail of the list instead of the head.

Add new nodes in their correct order (difficult). If you succeed, add a tail pointer too. Then you can traverse the ordered list easily in any direction.

Circular Linked List

In this type of linear data structure , the last node is pointed back to the head of the list instead of being a null reference. Depending on the use of the list, it is quite often more convenient to keep a tail pointer rather than a head pointer.

If there is only one node it is pointed at itself.

The node structure is the same as for a "normal"inked list:

/**
* FileNode.java
*
* @author Mr J
* @version 20050210
*/
class FileNode
{
   // This could be used to hold a key and an address in a Random Access File
   // For SL, if using text files, it could contain a line in the text file
   // If the list is kept in order, it could be used to locate a block in a
   // partially-indexed file, for example.
   private String name;
   private long filePos;
   private FileNode next;

  public FileNode()
   {
     // default constructor, sets fields to null
     name = null;
     filePos = -1;
     next = null;
   }
   public FileNode(String nm, long fp, FileNode nx )
   {
     // Second Constructor for a student record, assigns fields
     setName(nm);
     setFilePos(fp);
     setNext(nx);
   }
   // accessor methods
   public String getName() {return name;}
   public FileNode getNext(){ return next;}
   public long getFilePos(){return filePos;}

  // modifier methods
   public void setName( String nm ) {name = nm;}
   public void setNext( FileNode n){next = n;}
   public void setFilePos( long fp ){filePos = fp;}
}

Example Applet:

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
/**
* Demonstrates use of a circular linked list, maintained in order
*
* @author Mr J
* @version 20050211
*/
public class OrderedList extends Applet implements ActionListener
{
   // GUI objects
   private TextField name = new TextField("Type a name here!");
   private Button add = new Button("Add name");
   private TextArea display = new TextArea(20, 30);
   private Label messages = new Label("Messages will appear here");

  // data members
   FileNode tail = null;
   long pos = 0;
   /**
   * Add objects to the Applet
   */
   public void init()
   {
     add(name);
     add(add);
     add(display);
     add(messages);
     // Causes button presses to be detected
     add.addActionListener(this);
   }
  /**
   * When an event occurs on an object with an ActionListener attached, this
   * method is carried out.
   *
   * @param e carries details about the event that occurred
   */
public void actionPerformed(ActionEvent e)
   {
     messages.setText("");
     addName();
   }
   /**
   * Add name in correct position in the list
   */
   public void addName()
   {
     // get the name and create a new node at the head
     // We'll just increment pos - could hold the pos of this record
     // or block of records in a partially indexed file
     String theName = name.getText();
     pos = pos + 1;
     FileNode newOne = new FileNode( theName, pos, null);
     // Need to link this node into the existing list
     // First check if the list is empty
     if (tail == null)
     {
       tail = newOne;
       newOne.setNext(newOne); // if only one node, it points to itself
     }
     else
     {
       FileNode temp = tail.getNext(); // head node
       int result = theName.compareTo(temp.getName()); // name at head
       if (result < 0)
       {
         // Name belongs at the head
         addAtHead(newOne);
       }
       else
       {
         // traverse to entry point
         FileNode prev = temp;  // we'll need a reference to the previous node
         boolean found = false; // insertion point found flag
         boolean atTail = false;// insert at tail flag

         while ( (!found) && (!atTail) )
         {
           prev = temp;
           temp = temp.getNext();
           atTail = (temp == tail);
           found = (theName.compareTo(temp.getName()) < 0);
         }
         if (found)
         {
           addInMiddle(newOne, prev, temp);
         }
         else if (atTail)
         {
           addAtTail(newOne);
         }
       }
     }
     displayList();
   }
   /**
   * Display the list of names
   */
   public void displayList()
   {
     if (tail == null)
     {
       display.setText("empty list");
     }
     else
     {
       display.setText("start\n-----\n");
       FileNode temp = tail;
       boolean completed = false;
       // "walk" round the list, using the temp pointer
       while (!completed)
       {
         temp = temp.getNext(); // first time this will be the head
         display.append(temp.getName() + " temp " + temp.getFilePos() + "\n");
         completed = (temp == tail); // check have we been all the way round
       }
     }
   }
   /**
   * Adds a node to the tail end of the list
   *
   * @param n the node to be added
   */
   private void addAtTail( FileNode n )
   {
     n.setNext(tail.getNext());
     tail.setNext(n);
     tail = n;
   }
   /**
   * Adds a node to the head of the list
   *
   * @param n the node to be added
   */
   private void addAtHead( FileNode n )
   {
     n.setNext(tail.getNext());
     tail.setNext(n);
   }
   /**
   * Add a node in the middle of the list
   *
   * @param n the node to be added
   * @param p the node before the insertion point
   * @param t the node after the insertion point
   */
   private void addInMiddle( FileNode n, FileNode p, FileNode t )
   {
     n.setNext(t);
     p.setNext(n);
   }
}

Back to top

Exercises

Change the code so it adds nodes in reverse order.

Add a button and a method to remove a node from the list.

Add code to eliminate any duplicate nodes.

A mini-project might be to create a Class that combines some of the above techniques to implement all the methods necessary to maintain a list in order. Page 66 of the Subject Guide suggests the methods that a list ADT should implement.

Related: [ Java home | Previous: simple lists | Next: stacks ]

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.