Data Structures
Definition:

A data structure consists of

A base storage method (e.g. an array, a list, a tree, a …)

One or more algorithms that are used to access or modify that data

Data Abstraction

Data abstraction is a key concept for data structures.

Example - Dice

By Svjo (Own work) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

Here is a program demonstrating a dice data structure. Dice is a useful example because we all understand what a set of dice are and how they work. You can roll/spin them to produce a total value and you can get the face up values of the dice being rolled.

Simple procedural approach - the data in the program is simply stored as two variables in the program, which calculates values for these variables using a method that generates random numbers.
```
public static void main(String[] args) {
  int die1, die2, total;
  // randInt()user generated method to 
  // return a random number between 1 and 6
  die1 = randInt( );  
  die2 = randInt( );
  total = die1 + die2;
  System.out.println("first die: " + die1);
  System.out.println("second die: " + die2);
  System.out.println();
  System.out.println("total for spin is: " + total);
}
```
Object oriented approach - defines a class called Dice that encapsulates two individual dice, and that has methods to spin the dice and to return the values of the first die and the second die. The roll method encapsulates the calculation of the dice values, so that the calculation is the responsibility of the Dice object, not the responsibility of the program – the program doesn't need to know how that calculation is done or how the dice values are stored. The Dice class is an example of a data structure that abstracts, or hides the details of, the data and the way the data is manipulated.
```
public static void main(String[] args) {
  System.out.println("using class approach");
  int die1, die2, total;
  Dice dice = new Dice(); // instantiate the dice
  total = dice.roll( );   // roll the dice
  die1 = dice.die1();     // get die1 value
  die2 = dice.die2( );    // get die1 value
  System.out.println("first die: " + die1);
  System.out.println("second die: " + die2);
  System.out.println( );
  System.out.println("total is: "+ total);    
}
```
We haven't looked inside the Dice class to see how the code is written, and we don't need to here. All we need to know in order to use the Dice class in our program is what it does. Dice is a data structure that stores data and provides operations that acts on the data.

Data - two integers, each between 1 and 6

Operations - one operation to roll the dice and return the total value, and operations to return the value of each die

The Dice class could be written to provide further operations. For example it could return a text representation of the result.

More complex data

The Dice class is a very simple data structure. The data and the operation(s) are so simple that there is little, if any, advantage over the procedural approach – the procedural program is itself simple. What if the data were more complex?

Example - deck of cards

Data – 4 suites of 13 cards each

Operations – deal, cut, shuffle, and so on

Writing a program to implement a card game would become quite complicated, much simpler if these data and operations are encapsulated in a Deck data structure.

Example - air traffic control system

Very complex data and operations - need to develop a model, requires high level of software engineering expertise and expert knowledge of the problem domain
Abstract Data Type (ADT)

ADTs give us a tool to use to control complexity

An ADT is a collection of data and operations

Abstract – does not say anything about the details of how it actually works

ADT defines the data characteristics but DOES NOT include method of representation

ADT defines the operations that may be applied to the data but DOES NOT include how these operations are implemented

The idea of the ADT was proposed by Barbara Liskov at MIT in a paper published in 1974.

Definition of ADT

An Abstract Data Type (ADT) is :

a well-specified collection of data

known as the characteristics, or data state

and a set of operations that can be performed upon the data

known as behaviours or operations

The set of operations that can be performed is known as the interface

Implementation

In order to have a data structure that can actually be used you need to have an implementation of the ADT that actually stores the data and provides working operations. In Java, operations are implemented as methods. There may be many possible ways of implementing the same ADT. In the Dice example, the two die values could be stored as two integer fields in the Dice class, or perhaps as an array of integers as a field in the class. The details of the spin operation would be slightly different in each case. The program doesn't need to know anything about these details, though, in order to use the Dice.

This is a bit like driving a car - you don’t need a mechanic’s understanding of what’s under a car’s hood in order to drive it.

What’s the car’s interface?

What’s the implementation?

When working with an ADT, the program that uses it need not know about the implementation of the ADT. It interacts with the ADT using only public methods. This is an example of reusable code – the same ADT implementation can be used in many different programs.

ADTs facilitate storage, organization, and processing of information

ADT Design Process:

Identify “kinds” or “types” of Information

Encapsulate information1.1 and provide a public Interface consisting of methods

Hide information and method code in the private implementation

Language-independent ADTs

Important to note that an ADT is a formal description, not code; independent of any programming language. Why is code independence a good idea? It promotes design by contract:

A contract in business typically specifies responsibilities of suppliers and clients explicitly, so they can be enforced by law, if necessary

A contract in software specifies the responsibility of the code that performs an operation and the code that calls it. What do you think enforces a software contract?

In either case, the contract doesn't specify the details of:

How the supplier will actually create the product or service, or

How the code implements the operation

This is not a Java programming course; however you will use Java to help you to learn about data structures, in a couple of ways:

Note that the Java Collections Framework provides data structures that implement many common ADTs, and you will learn to make use of these during this module.

You will be expected to use Java in the practical activities to implement your own version of ADTs
Interfaces
As you have learned, an ADT’s specification describes:

what data can be stored (the characteristics of the ADT),

and how it can be used (the operations),

but not how it is implemented or represented in the program. ADTs do not specify how the data structure will be implemented - there may be many ways. The data specification has been decoupled from the implementation.

This means that software development can be less complex (fewer details to consider). Also, software development is more flexible (the actual structure is not fixed) – easier to change!

Object-oriented programming (OOP) emphasizes data abstraction, and provides a basis for defining ADTs and creating data structures to implement them. Note that data structures are not dependent on OOP – you can also create them in non-OO languages.

A Java interface is a way to specify but not implement an ADT. An interface can specify the names, parameters and return types of the ADT methods without specifying how the methods carry out their operations and without specifying how the data is internally represented

Interface Definition

FORM:
```
public interface interfaceName {
    abstract method headings
    constant declarations
}
```
EXAMPLE:
```
public interface Payable {
    double calcSalary();
    boolean salaried();
    static final double DEDUCTIONS = 25.5;
}
```
This example specifies two methods, each of which takes no parameters and has the specified return type. Note that constants can also be defined in the interface, but not instance variables. In this example, the constant DEDUCTIONS is accessible in classes that implement the interface
Contracts and Interfaces
A java interface is a contract between the interface designer and the programmer of a class that implements the interface. The programmer MUST code the methods that carry out the operations identified in the interface. The screenshot below shows a class definition for a class SayHello that implements an interface IMustBeHere. There is a problem with this class, though, and the compiler is reporting an error. The interface specifies that a method mustBeHere must be present in an implementing class, but SayHello does not yet provide an implementation for this method, hence the error message. To fulfil the contract specified by the interface, SayHello must implement a method mustBeHere with a signature that matches that specified in the interface ( it must return a Boolean value and take no parameters).
```
public interface IMustBeHere {
   boolean mustBeHere();
}
```
There can be many different implementations of an interface:
```
public class SayBye implements IMustBeHere {
...
```
A class may implement more than one interface — their names are separated by commas:
```
public interface ICanSleepIfIWantTo {
    	Boolean canSleep();
}

public class SayHello implements IMustBeHere, ICanSleepIfIWantTo {
...
```
As long as the implementation satisfies the contract, the programmer may implement it as he or she chooses.

In addition to implementing all data fields and methods in the interface, the programmer may add:

data fields not in the implementation

methods not in the implementation

constructors (an interface cannot contain constructors because it cannot be instantiated)

Here is a complete SayHello class that implements the interfaces IMustBeHere and ICanSleepIfIWantTo:
```
public class SayHello implements IMustBeHere, ICanSleepIfIWantTo {

public Boolean mustBeHere() {
     return true;
}

public Boolean canSleep(){
     return false;
}
   	public void sayHello() {
     		if (mustBeHere() && !canSleep())
           		System.out.println(“Hello DSA Students!”);
     }
}
```
The Dice ADT
Now let’s look at how the Dice class referred to earlier can be implemented as an ADT. The Dice ADT represents two simple dice that can be rolled to get a random total that lies between 2 and 12. The value of each die can also be retrieved after rolling.

Characteristics (data state):

Represents a pair of 6-sided dice, each of which can have a value between 1 & 6.

Operations:

roll( )

Precondition: none.

Postcondition: A random value between 1 and 6 is stored for each of the 2 dies.

Returns: The sum of the two die values, lying between 2 and 12.

die1( )

Precondition: Dice must exist and has been rolled at least once

Postcondition: Die #1 will have value in range 1 & 6

Returns: The value of die number 1 lying between 1 & 6

die2( )

Precondition: Dice must exist and has been rolled at least once

Postcondition: Die #2 will have value in range 1 & 6

Returns: The value of die number 2 lying between 1 & 6

ADT interface - IDice
```
public interface IDice {    
    
	int roll(); 

	int die1();

	int die2();    
    
}
```
ADT Class version 1 – Dice implements IDice
```
public class DiceV1 implements IDice {
    
    public int roll() {
       return die1() + die2(); 
    }
    
    public int die1() {
       return randInt();        
    }    
    
    public int die2() {
       return randInt();        
    }

  // private implementation of randInt() ...

} // end of Class
```
ADT Class V2 – Dice implements IDice

It is often possible to implement an ADT in more than one way, as long as it provides the required operations to implement the interface. Here is a variation on the implementation of the Dice ADT:
```
public class DiceV2 implements IDice {
    
    public int roll() {
     die1Value = randInt();   // roll die #1
     die2Value = randInt();   // roll die #2
     return die1Value + die2Value; 
    }   
 
    public int die1() {    
     return die1Value;
    }        

    public int die2() {   
     return die2Value;
    }
        
    // private section
    private int die1Value;
    private int die2Value;

  // private implementation of randInt() ...

} // end of Class
```
Declaring a Variable of an Interface Type

While you cannot instantiate an interface, you can declare a variable that has an interface type
```
/* interface type */
IDice dice1 = new DiceV1();
IDice dice2 = new DiceV2();
```
This is useful when dealing with polymorphic code, so that the code that uses a Dice object does not have to specify which implementation of the ADT will be used at runtime, but simply relies on the fact that the ADT will fulfil the contract specified by the ADT interface.
Abstract Classes
Abstract Class

An interface can declare methods but does not provide an implementation of the methods. In an interface, all the methods are abstract – i.e. they do not include any code that implements any action. An interface also cannot have any data fields or constructors.

An abstract class, on the other hand, can have:

abstract methods

data-fields

concrete implementations of methods

constructors that initialize data-fields

However, like an interface, it still cannot itself be instantiated

Useful for situations where you want to provide implementations of some behaviour that will be common to a set of classes that will otherwise implement their own behaviour.

Here is an example of a simple Abstract Class that includes a data field, a concrete method and an abstract method. The data field could be initialised by a constructor, although that is not illustrated in this example.
```
public abstract class Animal {
	
String name;

	void eat(String food) 
{
	System.out.println("Ate some " + food);
}

abstract void talk(); 
}
```
This can be extended by concrete classes that inherit the eat method and implement the talk method:
```
class Dog extends Animal {
	
void talk( ) {
   System.out.println("Woof"); 
}
}

class Cat extends Animal {

void talk( ) {
   System.out.println("Miaow"); 
}
}
```
Like interfaces, abstract classes enable polymorphism. This example creates a collection of animals. The type of the collection objects is declared as Animal, but the actual object types are Dog and Cat.
```
public class AbstractDemo {

    public static void main(String[] args) {
        ArrayList<Animal> animals = new ArrayList<Animal>();
        animals.add(new Dog());
        animals.add(new Cat());
        
        for(Animal a: animals) {
            a.eat("nice food");
            a.talk();
        }           
    }
}
```

The Dice ADT Using An Abstract Class

You can base the Dice implementation on an abstract class instead of an interface. Here is the abstract class. It represents the same data characteristics and operations that we defined previously for the Dice ADT. Note that it has data fields representing the values of each die, and it implements the die1 and die2 operations as getter methods for these fields. It does not, however, implement the roll method, so in order to create and use a dice you need to have a concrete class that extends this abstract class and provides an implementation of roll.
public abstract class ADice { public int die1Value; public int die2Value; public int die1(){ return die1Value; } public int die2(){ return die2Value; } public abstract int roll(); }
Here is another version of the Dice ADT, this time as a class that extends the ADice abstract class. Note that because it does so, it only needs to provide a concrete implementation of roll, which as in the previous versions, makes use of a private method to calculate a random integer, and this private method is used in the roll method.
public class DiceV3 extends ADice { public int roll() { die1Value = randInt(); // roll die #1 die2Value = randInt(); // roll die #2 return die1Value + die2Value; } // private implementation of randInt() ... } // end of Class
The following code creates and tests instances of each of the three versions of the Dice ADT. Note that they are all used in exactly the same way.
public class DiceDemo1 { public static void main(String[] args) { System.out.println("Using DiceV1"); int total1; IDice dice1 = new DiceV1(); total1 = dice1.roll(); System.out.println("first die: " + dice1.die1()); System.out.println("second die: " + dice1.die2()); System.out.println("total is: " + total1); System.out.println("Using DiceV2"); int total2; IDice dice2 = new DiceV2(); total1 = dice2.roll(); System.out.println("first die: " + dice2.die1()); System.out.println("second die: " + dice2.die2()); System.out.println("total is: " + total1); System.out.println("Using DiceV3"); int total3; ADice dice3 = new DiceV3(); total3 = dice3.roll(); System.out.println("first die: " + dice3.die1()); System.out.println("second die: " + dice3.die2()); System.out.println("total is: " + total3); } }

Interface and Abstract Class
Note that the ADice abstract class actually fulfils the contract specified by the IDice interface. It provides all the operations (die1, die2, roll) in the interface. This means that we can make ADice implement IDice. This works, even though the implementation of roll in ADice is abstract.
```
public abstract class ADice implements IDice {
```
This combination of an interface and an abstract class is quite commonly used when designing implementations of ADTs. In this approach:

The interface specifies what operations the ADT must provide – it is the contract

The abstract class provides some operations that will be common to some or all implementations of the ADT, so that these do not need to be written in every class that implements it.

With this modification, the test class can be simplified, using polymorphism, as all the versions of the Dice ADT now implement the same interface.
```
public class DiceDemo2 {

    public static void main(String[] args) {
        ArrayList<IDice> allDice = new ArrayList<IDice>();
        allDice.add(new DiceV1());
        allDice.add(new DiceV2());
        allDice.add(new DiceV3());

        for (IDice dice : allDice) {
            int total;
            total = dice.roll();
            System.out.println("first die: " + dice.die1());
            System.out.println("second die: " + dice.die2());
            System.out.println("total is: " + total + "\n");
        }
    }
}
```

Summary of Features of Classes, Abstract Classes, and Interfaces

Property	Class	Abstract Class	Interface
Instances of this can be created	Yes	No	No
This can define instance variables and methods	Yes	Yes	No
This can define constants	Yes	Yes	Yes
The number of these a class can extend	0 or 1	0 or 1	0
The number of these a class can implement	0	0	Any number
This can extend another class	Yes	Yes	No
This can declare abstract methods	No	Yes	Yes
Values of this type can be declared	Yes	Yes	Yes

Data Structures

Abstract Data Type (ADT)

Interfaces

Contracts and Interfaces

The Dice ADT

Abstract Classes

The Dice ADT Using An Abstract Class

Interface and Abstract Class

Summary of Features of Classes, Abstract Classes, and Interfaces