Chapter 1

Introduction to Data Structure

 Introduction to Data Type
In Java programming, all variables are required to have a data
type.

Java Data Types can be divided into:

a) Fundamental /Primitive /Base Type

b) Abstract Data Type
 Fundamental /Primitive /Base Type
 A variable of the fundamental type simply store a value of that
type (one value at a time).

 8 fundamental types
 int : 32-bit signed two’s complement integer
 float :32-bit floating-point number
 double : 64-bit floating-point number
 long :64-bit signed two’s complement integer
 short :16-bit signed two’s complement integer
 char :16-bit unicode character
 boolean:boolean value – true or false
 byte :8-bit signed two’s complement integer
 Abstract Data Type (ADT)

Definition:

A set of data values and associated operations that are precisely

specified independent of any particular implementation.

Paul E. Black (2004)

 Abstract Data Type (ADT)
Abstract Data Type (ADT)

 A data type that specifies the logical properties without the

implementation details

 ADT is used to describe the characteristics of a data structure

 The data representation and actual algorithms for the operations

are unspecified

 An ADT has
◦ A set of values (data)
◦ A set of operations (methods)

 An ADT is presented as a class type and treated as a single entity

that encapsulates its data together with its method
 Abstract Data Type (ADT)
 Classes are used to represent objects in Object Oriented
Programming (OOP) approach.

 OOP uses classes to encapsulate data (attributes) and methods

(behaviors).

 Encapsulation enables objects to hide their implementation from

other objects.

 An ADT provide information hiding

◦ ADT kept the implementation details of the operations and the

data from the users of ADT

◦ The user of ADT can use the operations on an ADT without

knowing how the operation is implemented
 Abstract Data Type (ADT)
ADT is also referred to as an object.

ADT contains more than one fundamental data types.

ADT also contains the methods as an interface to manipulate the data.

Each ADT is an encapsulation of data and methods.

In Java, ADT or object is defined using Class. Eg:

class Computer {
private int code;
private String brand;
private double price;

public Computer () { }
public Computer (int c, String b, double p) {…}
public int getCode () { return code; }
public String getBr () { return brand; }
public double getPr() { return price; };
 Data Structure
 is a particular way of storing and organizing data in a computer so it
can be used efficiently.

 is a systematic way of organizing a collection of data.

 is a representation of data and the operations allowed on the data.

 is known as a collection of related data items.

 Every data structure needs a variety of algorithms for processing

the data in it (insertion, deletion, retrieval, etc)

 Algorithms are used to manipulate the data contained in these data

structures as in searching and sorting.

 Different kinds of data structures are suited to different kinds of

applications.
 Data Structure
 Example of Data Structure
◦ Arrays
◦ Lists
◦ Queues
◦ Stacks
◦ Trees
◦ Indexes

 The choice on which data structure to be used for a system will affect
the system design and contribute to the effectiveness of that system.

 The correct choice of data structure allows major improvement in

program efficiency

 2 types:
◦ Static – fix size (array, record)
◦ Dynamic – grow and shrink at runtime (list, queue, stack, binary
tree)
 Data Structure
Static VS Dynamic Data Structure

 Besides time and space efficiency another important criterion

for choosing a data structure is whether the number of data
items it is able to store can adjust to our needs or is bounded.

 This distinction leads to the notions of dynamic data structures

vs. static data structures.

 Dynamic data structures grow or shrink during run-time to fit

current requirements
e.g., a structure used in modeling traffic flow.

 Static data structures are fixed at the time of creation.

e.g., a structure used to store a postcode or credit card number
(which have a fixed format).
 Data Structure
Advantages of Static Data Structure

ease of specification

Programming languages usually provide an easy way to

create static data structures of almost arbitrary size

no memory allocation overhead

Since static data structures are fixed in size, there are no

operations that can be used to extend static structures; such
operations would need to allocate additional memory for the
structure (which takes time)
 Data Structure
Disadvantages of Static Data Structure
must make sure there is enough capacity

the number of data items we can store in a static data structure

is fixed, once it is created, we have to make sure that this
number is large enough for all our needs

more elements? (errors), fewer elements? (waste)

However, when our program tries to store more data items in a

static data structure than it allows, this will result in an error
(e.g. ArrayIndexOutOfBoundsException)

On the other hand, if fewer data items are stored, then parts of
the static data structure remain empty, but the memory has
been allocated and cannot be used to store other data.
 Data Structure
Advantages of Dynamic Data Structure

There is no requirement to know the exact number of data

items

Since dynamic data structures can shrink and grow to fit

exactly the right number of data items, there is no need to know
how many data items we will need to store

Efficient use of memory space if we only extend a dynamic data

structure in size whenever we need to add data items

have exactly the right size and no memory space is wasted

 Data Structure
Disadvantages of Dynamic Data Structure

Memory allocation/de-allocation overhead

Whenever a dynamic data structure grows or shrinks, then

memory space allocated to the data structure has to be added
or removed (which requires time)
 Data Structure
A good approach to determine which data structure that best suit
your application is to study the strengths and weaknesses of
each of the data structure available.
 Data Structure Application
 Array

A data structure that holds a collection of data in sequential

order

Is the simplest data structure and easy to use

Can be one- dimensional and multi-dimensional

2 limitations:
 Once an array is created its size cannot be altered
 An array does not provide adequate support for insertion
and deletion operation
 Data Structure Application
 List
A dynamic data structure where size can be changed
A list is a collection of data stored sequentially
It supports insertion and deletion anywhere in the list

Two types of list :

 Sequential list (array list) – arrays that store data in a
contiguous memory (elements next to each other)
 Linked list – a linked structure that store data where one
element refers to another, anywhere in memory
 Data Structure Application
 Stack

A stack can be perceived as a special type of list where

insertions and deletions take place only one end, refererred to
as top of the stack

Known as LIFO (Last in First Out)

Example: Stack of plates

 Data Structure Application
 Queue

A queue represent a waiting list, where insertions take place

at the back of the queue

Adding at the back and deleting in front

Known as FIFO (First In First Out)

Example: queuing for the bus, taxi, etc

 Data Structure Application
 Binary tree

A binary tree is a data structure that supports searching,

sorting, inserting and deleting data efficiently

Data in a hierarchical relationship

 ADT & Data Structure
 ADT consist of a collection of values, together with collection of
operations on those values.

 Using Java, a user of a class can:

◦ Create an instance of that class (value)
◦ Invoke the public methods of the class

 However, classes have additional properties (inheritance and

polymorphism) not normally associated with ADTs
 ADT & Data Structure
 A Data Structure is the implementation of an abstract data type.

 In OO languages, a developer implements an interface with class.

 In another word is as following association :

General term Object Oriented Term

Abstract Data Type interface

Data Structure class

 ADT & Data Structure
ADT is the logical picture of the data and the operations to
manipulate the component elements of the data

Data structure is the actual representation of the data during the

implementation and the algorithms to manipulate the data elements

ADT is the logical level and data structure is in the implementation

level

Conclusion:
Data structure is how we implement the data in an abstract data
type.