A Brief Intro to Abstract Data Types

I wanted to talk about a topic in computer science which is used extremely often and one that is fundamental to the way we code. Computer science is all about solving problems and one of the ways we do so is to look for solutions in terms of models and to determine whether there is an existing program to solve it. We aim to find a solution represented through an algorithm.

An algorithm is a sequence of instructions performed in a period time with a finite amount of effort. You want to choose an algorithm that is easy to implement and one that is efficient. Efficiency becomes increasingly important as the amount of data increases. In addition, we need ways to organize data so that you can operate on it easily in a format that the algorithm requires.

This brings us to the topic of abstract data types (ADTs) which are a collection of data and set of operations that define that data type. After data and operations are defined, the ADT is implemented through the use of data structures. These data structures are created from the most primitive data types of the programming language using the available data structuring methods.

Capture

Some benefits of using ADTs include the ability for easily reusing code and the fact that the user doesn’t need to know about an ADT implementation because they interact with the public methods. Examples of data structures include arrays, records and linked lists. As pictured above, there is also something called an interface which describes the ADT to the user by specifying actions they perform, arguments needed, and results returned by the ADT. Classes can then implement the interface which feeds code to the ADT and a result can be returned if all of the interface requirements are met.

Let us examine the ATM interface to try to simplify the idea of how an interface works. An ATM allows the user to do several things:

  • Enter PIN
  • Choose between checking or savings account
  • Withdraw money
  • Show acct balance

If we were to code this, it could look something like the code below. The keyword interface in the header tells us that the interface is being declared. Each of the actions above are represented in the interface definition below where headings are only shown for its methods. This is because they are abstract methods which must additionally be defined in a class which implements the interface.

public interface ATM {
   boolean verifyPIN(String pin);
   String selectAccount();
   boolean withdraw(String account, double amount);
   void showBalance(String account);
}

The interface definition can also define any constants to be used so in the example above, if there was an ATM fee, it would be included in the definition as:

double fee = 2.50;

Now that we have the ATM interface, different bank companies may want to implement the interface with their own custom methods, this can be performed by defining the new class as

public class WellsFargo implements ATM

You cannot instantiate an interface but you can declare a variable with type interface and has a lot to do with polymorphism which I will talk about in the next blog post on object oriented programming.

ATM anATM = new ATM(); // invalid statement
ATM ATM1 = new WellsFargo(); //Declared var of interface type
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s