5.3.1
Dynamic data structures

Properties like Button color, Button text.

Methods like Button.setColor(Color), Button.setText(String)

The diagonal bar is used to denote a null pointer.

You might want to look back at the Button example at the top of the page again.

Sometimes we will speak of "pointing to" when meaning the same thing as referencing.

We could as easily show this node with the diagonal bar signifying null.

Objects and references

Apart from primitives , all Java objects are actually references. A primitive, such as an int , boolean or double , is stored directly into a memory location:

When you instantiate an object such as a button:

b is not actually a Button object , strictly speaking it's a reference to a button Object (it specifies where in memory the Button and it's associated methods and properties are to be found).

Assume we create a second button object:

Somewhere in physical computer memory these details are stored:

 If we make an assignment such as:

 We overwrite the reference ( January 3, 2006 ference the address that b references ("Press me"). The memory occupied by "Press me not" is no longer referenced and becomes inaccessible storage.

Any methods available to c, such as setColor(blue), will now affect button b ("Press me"), that is:

b.setColor(Color.BLUE);
 c.setColor(Color.BLUE);

will now affect the same object.

Back to top

The Linked List

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 a Node for such a linked list could be:

/**
* ListNode.java
*
* @author Mr J
* @version 20060103
*/
class ListNode
{
   private int value;
   private ListNode next;

  public ListNode( )
   {
     // default constructor, sets fields to null
     value = 0;
     next = null;
   }
   public ListNode(int v, ListNode n)
   {
     // Second Constructor for List, assigns fields
     setValue(v);
     setNext(n);
   }
   // accessor methods
   public int getValue() {return value;}
   public ListNode getNext(){ return next;}
   // mutator methods
   public void setValue( int v ) {value = v;}
   public void setNext( ListNode n){next = n;}
}

Adding to the head of the list:

/**
* SimpleList.java
*
* @author richard
* @version 20060103
*/
public class SimpleList
{
   ListNode head = null; // pointer to the first node
   public static void main(String[] args)
   {
     new SimpleList();
   }
   public SimpleList()
   {
     int x;
     do
     {
       x = inputInt("Please input a whole number (-1 to end): ");
       add(x);
     } while (x >=0);
     displayList(head);
   }
   public void add(int x)
   {
     // create a new ListNode
     ListNode temp = new ListNode(x, null);
     // point this new node to the current head node:
     temp.setNext(head);
     // Now point the current head to the new node:
     head = temp;
   }
   public void displayList(ListNode head)
   {
     while (head != null)
     {
       output("" + head.getValue());
       head = head.getNext();
     }
   }

//============================================================
 // Below are the IBIO simple input and output methods

How does this work? Let's start by adding the first item to the list - assume it is the number 4.

     public void add(int x)       // x gets the value 4

The method then creates a new ListNode object:

    ListNode temp = new ListNode(x, null);

A really important point to note here is the difference between this new ListNode that has been created (and which is referenced by temp) and the ListNode head identifier - head is NOT a node, it cam contain a reference to a node, just as temp can, but it is not itself a ListNode object/instance.

  ListNode head = null; // pointer to the first node

Notice that this declaration has no new keyword to call the ListNode constructor to reserve memory for a ListNode instance. Therefore an attempt, say, to call head.setNext() will fail as a null pointer exception.

The next line, sets the next field of the temp node to reference the same thing that head is referencing.

    temp.setNext(head);

At this point head is still null, so the next field of the temp node gets this null value to. Finally, head itself is assigned the same value as temp so it now points to the new node containing the value 4:

    head = temp;

Imagine now, that the add method is called again, this time with the value 7. What happens. First a new node is created again:

    ListNode temp = new ListNode(x, null);

This time, the line:

     temp.setNext(head);

Sets the nexct pointer to reference the same as head, but head is already referencing the list with the node 4 in it. So we get this situation:

Now, when head is re-assigned:

    head = temp;

We get the following list (ignoring temp):

Exercise

To demonstrate your understanding of these concepts, write a method that adds a ListNode to the tail of the list.

The last node in the list ought to be the only one which has a next field set to null.

Write a method that removes an item from the head of the list, if it exists.

Write a method to remove an item from the tail of the list, if it exists.

Other types of list - doubly-linked and circular lists are covered on this page . You can adapt the SimpleList program to implement these in JETS/IBIO form easily enough.

Stacks , queues and trees as dynamic data structures are covered on this page and related pages.

A stack can be created using the add to head method for push and the new remove from head method.

A queue can be created using the add to head (rear) and remove from tail (front) methods you created in the exercise - although it would be sensible to rename the reference identifiers and method names.

For a binary tree , you can adapt the methods given on this page to work at the console.

Back to top

related: [ ADT home | previous: static data structures | next: objects ]

Here we are revisiting the dynamic data structures (see also the Java pages on this).

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.