Data Structures in Java

Real Life

The real world is complex. There are all kinds of things out there - cars, buildings, people, electricity, books, the Internet, football games, money, etc.

Sometimes all these things are a mess, like in a teenager's bedroom or the desk shown here. The real world needs organization to keep the mess under control.

Inside a computer program, we use data-structures for organization.

Data Structures

Data refers to single items - a number, a word, a character, etc. A data-structure is an "object" that can store more than one piece of data. We can store a list of numbers in an array, so an array is an example of a data structure. We can store lots of words in a text-file, so a text-file is another example of data-structure.

Arrays store simple linear lists of homogeneous data - that means all the data items are the same type. An array either contains numbers or strings, but not both. In the picture above, there are lots of pieces of paper. We could make stacks of paper to organize things. If we put all the A4 sheets in one stack, and smaller sheets (pictures, memos) in another, then we would be making homogenous stacks of paper.

Composite Objects

What if you want to stick various types of things together? You could staple a picture onto a piece of paper to make a composite object - one that contains both a sheet of paper and a photograph. Other real-world objects consist of many different parts - for example, a bicycle. A bicycle has 2 wheels, a handle-bar, a frame, a chain, some gears and pedals. These are "stuck together" by welding or screwing the parts together.

Composite Data Structures

In Java, we can also build composite objects containing various types of data. Consider this ticket for a parking garage. The ticket contains 3 pieces of data: a date, a time, and an ID number.

You Park

12/25/08 14:55

243098625

It is possible to store all three data items as Strings, so we could use a String[] array. But there is another possibility that is simpler for the programmer. We create a data record type. In Java, we make a new class that contains a variable (property) for each data item. Like this:

class ParkTicket
{
   String date = "";
   String time = "";
   int ID = 0;
}

If you go shopping and park in a parking garage, the ticket records the time you entered. When you leave, a machine will read the ticket, compare the starting time to the current time, calculate the number of hours you parked, and then charge you accordingly. Modern parking garages use a central computer that saves the data centrally, so the time and date printed on the ticket aren't actually used - only the id number to look up the time and date.

Sample Program

This program shows how to use a data class in a larger program. The program simulates the machine in a parking garage.

import java.util.Date;

public class Garage extends EasyApp
{
    public static void main(String[] args)
    {
        new Garage();
    }

ParkTicket ticket = new ParkTicket();

    public Garage()
    {
        output("Click [OK] to enter the garage");

        Date enter = new Date();
        ticket.date = enter.toString().substring(4,10);
        ticket.time = enter.toString().substring(11,16);
        ticket.ID = 187762539;

output("Click [OK] to exit the garage");

Date leave = new Date();
ticket.leave = leave.toString().substring(11,16);

output("You entered at " + ticket.time + " on " + ticket.date);

output("You left at " + ticket.leave);
}
}

class ParkTicket
{
    String date = "";
    String time = "";
    String leave = "";
    int ID = 0;
}

Of course, this should be changed to a GUI interface, with buttons for entering and leaving. ACTUALLY, it should all run from a machine that prints tickets and takes money, but we will stick to a simple simulation.

The command to put the date INTO the ticket object is :

ticket.date = enter.toString().substring(4,10);

The command to put the ID number into the ticket object is:

ticket.ID = 187762539;

The command to read the date later is :

ticket.date

Similarly for reading or writing the .leave field.

Objects are Better than Simple Variables

Using fields in an object is better than using simple variables because you can make as many COPIES of ParkTicket objects as you want. You could make a whole array of ParkTickets, just like a machine dispensing tickets. Then you could store all the tickets for the day. When a customer leaves, the program could SEARCH for the ticket ID, retrieve the time of entry, and calculate the parking fee. The command to make lots of ParkTicket objects is:

ParkTicket[] tickets = new ParkTicket[1000];

It's all a bit more complex than that, but that's the basic idea.

Computer Dating Project

We can use these techniques to make a computer dating program. This program tries to match a boy and a girl of similar interests and similar age.

Data Structure

The first question is: what pieces of data should we store for each student? Here is a suggestion:

       class Person
       {
           String name = "???";
           char gender = '?';
           int age = 0;
           String music = "???";
           String hobby = "???";
           String other = "???";
       }

You can add more data if you wish, but this will be enough for a prototype of the program.

Algorithms

The second question is: what should the program do? Here is a suggestion:

Input - accept new people and input their data fields
List - store all the peoples' records in an array
Save - write all the information (all records and all fields) into a text file
Load - get all the information back from the file the next time the program runs
Match - search for a good match for a specific person

First Try

Here is a first try at the program. It inputs people until the user types QUIT. It stores all the people in an array. Then it prints the names of all the females. After that, it stores all the data in a text file.

Some of the commands have been erased. You need to fill in the missing pieces and get the program running.

import java.io.*;

public class Dating extends EasyApp
{
public static void main(String[] args)
{
   new Dating();
}

Person[] people = new Person[1000];
int count = 0;

public Dating()
{
   inputPeople();
   showFemales();
   saveData();
}

public void inputPeople()
{
   String more = "yes";
   while (!more.equals("QUIT"))
   {
     Person p = new Person();
     p.name = input("Name");
     p.gender = inputChar("Gender (M/F)");
     p.age = inputInt("Age");
     people[count] = p;
     count = count + 1;
     more = input("More input (yes or QUIT)?");
   }
}

public void showFemales()
{
   for (int c = 0; c < count; c = c + 1)
   {
      if (people[c].gender == 'F')
      { output(people[c].name + " " + people[c].age); }
   }
}

public void saveData()
{
   try
   {
      PrintWriter file = new PrintWriter(
            new FileWriter("d:\\mine\\people.txt"));
            for (int c = 0; c < count; c = c + 1)
            {
              file.println(people[c].name);
              file.println(people[c].gender);
              file.println(people[c].age);
              file.println(people[c].music);
              file.println(people[c].hobby);
              file.println(people[c].other);
            }
      file.close();
   }
   catch(IOException ex)
   { output(ex.toString()); }
}

}

class Person
{
    String name = "???";
    char gender = '?';
    int age = 0;
    String music = "???";
    String hobby = "???";
    String other = "???";
}

Make It Better

You need to improve the Dating program. It is missing a few pieces. It is also subject to some errors. Do as many of the following as you can:

Change the program so that it also inputs a HOBBY for each person.
Add a method that LOADS all the data from the text-file when the program runs. It needs to put new people in the array, very similar to the inputPeople, but it needs to read the data from the text file.
Make a file containing 10 friends, including a hobby for each.
VALIDATE the age input to force it to be between 1 and 99.
VALIDATE the name input to ensure that it is not blank.
VALIDATE the Gender input so they MUST type either 'M' or 'F' .
Now comes the important part. Add a method that can search for possible dates. It should ask whether you want a Male or Female, what the MINIMUM age is, and what HOBBY you like. Then the program prints out the people matching your wishes.
Make the MATCHING method a bit more flexible, by making the following changes:
- it must only match 2 of the 3 criteria : age, gender, hobby
- use .indexOf.. to find out whether the hobby you requested is somewhere in the hobby field. Then the user can ask for "ski" and they match all the following: "skier", "skiing", "alpine skiing", "downhill skiing".