Data Structures

Object Oriented Programming -

1
CoSc2051
Chapter Outlines
 The Set
 Set Implementation Classes
 The List
 List Implementation Classes
 The Queue
 Queue Implementation Classes
 Map/ dictionary

Object Oriented Programming - CoSc2051 2

 Introduction to Data structure
 What are Data Structures?
 We understand that computers do store, retrieve, and
process a large amount of data.
 If the data is stored in well organized, it can be accessed
quickly for processing.
 A data structure should be seen as a logical concept that
must address two fundamental concerns.
 First, how the data will be stored, and
 Second, what operations will be performed on it?
 The functional definition of a data structure is known as ADT
(Abstract Data Type) which is independent of
implementation.
Object Oriented Programming - CoSc2051 3
 Introduction to Data structure
 What are Data Structures?
 Made up of 2 words
 “DATA” + “STRUCTURES”
 It is a way to arrange data in computers
 Example: You might want to store data in
 Linear fashion – Array/ Linked List
 One on the other – Stacks
 Hierarchical Fashion – Trees
 Connect Nodes – Graph

Object Oriented Programming - CoSc2051 4

 Introduction to Data structure
 List of Data Structures using Java
 Array
Java Collection Framework
 Linked List  It is a set of classes and interfaces that
 implement commonly reusable
Stack
collection data structures algorithms.
 Queue  predefined architecture capable of
 storing a group of elements and
Binary Tree
behaving like a single unit such as an
 Binary Search object or a group
 There is no direct implementation of
Tree
this interface.
 Heap  However, it is implemented
 through its sub-interfaces like
Hashing
List, Set, and Queue.
Methods add(), size(), remove(), iterator(),
 Graph of addAll(), removeAll(), clear()
 Set
Collectio Object Oriented Programming - CoSc2051 5
 Map n
 Introduction to Collection - Data
structure

Methods
. of Collection
Method Descriptions
add(String e) inserts the specified element to the collection
size() Returns the size of the collection
remove(element) Removes a specified value from the collection
iterator() returns an iterator to access elements of the
collection
addAll(collection) Adds all the elements of a collection to the
specified collection
contains(element) Checks if the specified element is present in a
collection
removeAll(collectio Removes the elements of a collection from the
n) collection
clear() Clears
Object all Programming
Oriented the values of a collection
- CoSc2051 (does not6
clear the collection)
 Introduction to Data structure
 Methods of Collection
Method Descriptions
add(String e) inserts the specified element to the
collection
size() Returns the size of the collection
remove(element) Removes a specified value from the
collection
iterator() returns an iterator to access elements of
the collection
addAll(collectio Adds all the elements of a collection to
n) the specified collection
contains(element Checks if the specified element is
) present in a collection
removeAll(collec Removes the elements of a collection
tion) from the collection
clear() Clears all the values of a collection (does
Object Oriented Programming - CoSc2051 7
 List Implementation - ArrayList
• vimport java.util.ArrayList;
public class List {
public static void main(String[] args) {
//1. create an ArrayList
ArrayList<String> students = new ArrayList<>();
}
}

//2. Add Elements to the ArrayList

students.add("Bedasa");
students.add("Chala");
students.add("Bontu");

System.out.println(students); // [Bedasa, Chala, Bontu]

/*3. Access Elements in the ArrayList

use of the get() method */

System.out.println(students.get(1)); // Chala
OOP - CoSc2051 8
 List Implementation - ArrayList
• v4. Update Elements in the ArrayList
/*
make use of the set() method */
students.set(2,"Keraj");

System.out.println(students); // [Bedasa, Chala, Keraj]

/* 5. Remove Elements in the ArrayList
* make use of the remove() method */
students.remove(2);

System.out.println(students); // [Bedasa, Chala]

/* 6. the clear() method to remove all the elements

* in the collection: */
students.clear();

System.out.println(students); // []

OOP - CoSc2051 9
 Introduction to Data structure
 Collection Implementations
 Classes that implement the collection interfaces typically
have names in the form of <Implementation-
style><Interface>.
 The general purpose implementations are summarized in
the following
Interfac Hash : Resizable Balanc Linked Hash Table +
e Table Array ed Tree List Linked List
Set HashSe TreeSe LinkedHashS
t t et
List ArrayList LinkedLi
st
Deque ArrayDeq LinkedLi
ue st
Map HashMa TreeMa LinkedHash
p p Map

Object Oriented Programming - CoSc2051 10

 Introduction to Data structure
 Arrays
 Linear Data Structure
 Elements are stored in contiguous memory locations
 Can access elements randomly using index
 Stores homogeneous elements i.e, similar elements
 Syntax:
 Array declaration
 datatype varname []=new datatype[size];
 datatype[] varname=new datatype[size];
 Can also do declaration and initialization at once
 Datatype varname [] = {ele1, ele2, ele3,
ele4};
Object Oriented Programming - CoSc2051 11
 Introduction to Data structure
 Arrays - Advantages
 Random access
 Easy sorting and iteration
 Replacement of multiple variables
 Arrays - Disadvantages
 Size is fixed
 Difficult to insert and delete
 If capacity is more and occupancy less, most of the array
gets wasted
 Needs contiguous memory to get allocated

Object Oriented Programming - CoSc2051 12

 Example
package Array;

public class Array {

public static void main(String[] args) {

int[] numbers = { 2, -9, 0, 5, 12 };

int sum = 0;
Double average;

// access all elements using for each loop

// add each element in sum
for (int i = 0; i <= numbers.length; i++) {
sum += i;
}
System.out.println("SUm: " + sum);
}
}

OOP - CoSc2051 13
 Introduction to Data structure
 The Set
 Set in Java is an interface declared in java.util package.
 It extends the collection interface that allows creating
an unordered collection or list, where duplicate values are
not allowed.
 A Set is a Collection that contains unique elements (i.e.,
no duplicate elements).
 The collections framework contains several Set
implementations, including HashSet and TreeSet.
 HashSet stores its elements in a hash table, and TreeSet
stores its elements in a tree.

Object Oriented Programming - CoSc2051 14

 Introduction to Data structure
 Set Implementations
 As the name implies, a set in Java is used to create a
mathematical set.
 You cannot directly use the set to create its object as it is an
interface.
 Hence, you have to use the four classes, namely
 HashSet,
 EnumSet,
 LinkedHashSet, and
 TreeSet, that implement the set interface to work with it.
 Here, you will look at an example to create a set in Java using

the HashSet class.

Object Oriented Programming - CoSc2051 15
 Introduction to Data structure
 The Set implementation Example
import java.util.HashSet;
import java.util.Set;
 As the name implies, a set in Java is used to create a
public class SetExample {
mathematical
public static voidset.
main(String[] args) {
 You cannot directly
//create use the
set using set to
HashSet create its object as
generic
Set<String> setName = new HashSet<>();
it is an interface.
setName.add("Data Structure");
 setName.add("Java Set");
Hence, you have to use the four classes, namely
setName.add("OOP");
EnumSet, HashSet, LinkedHashSet, and TreeSet,
System.out.println(setName);
that
} implement the set interface to work with it.
}

 Here, you will look at an example to create a set in

Java using the HashSet class.
Object Oriented Programming - CoSc2051 16
 Introduction to Data structure
 Java Set Methods
Method Descriptions
add(String e) Adds a new value to the set
addAll(collection) Adds all the elements of a collection to the
specified set
contains(element) Checks if the specified element is present in a
set
isEmpty() Checks if the set is empty
removeAll(collectio Removes the elements of a collection from the
n) set
clear() Clears all the values of a set (does not clear
the set itself)
remove(element) Removes a specified value from the set
size() Returns the size of the set
toArray() Creates an array with the elements of a set
Object Oriented Programming - CoSc2051 17
 Introduction to Data structure
 Java Lists
 The List is an interface in Java, which is a child interface
of Collection.
 A List is an ordered Collection that can contain duplicate
elements.
 It can also accommodate null elements inside it.
 It is index-based, meaning you can insert and access
elements using a 0-based index.
public interface List<E> extends
 The list interface can be declared using the following
Collection<E>
syntax -

Object Oriented Programming - CoSc2051 18

 Introduction to Data structure
 List Implementations
 Being a Collection subtype all methods in the Collection
interface are also available in the List interface.
 Since List is an interface you need to instantiate a concrete
implementation of the interface in order to use it.
 You can choose between the following List implementations in
the Java Collections API:
 java.util.ArrayList
 java.util.LinkedList
 java.util.Vector
 java.util.Stack.
Of these implementations, the ArrayList is the most
Object Oriented Programming - CoSc2051 19
commonly used.
 Introduction to Data structure
 List Implementations Example
import java.util.ArrayList;
import java.util.List;

public class ListExample {

public static void main(String[] args) {

// Implement ArrayList class using the myList.

List<String> myList = new ArrayList<String>();

// Add String objects to the list

myList.add("Welcome ");
myList.add("to ");
myList.add("Java List");
System.out.println(myList);
}
}

Object Oriented Programming - CoSc2051 20

 Introduction to Data structure
 ArrayList in Java
 Unlike arrays in Java, ArrayList is a dynamic array that
has no size limit.
 It’s ordered, which means we can perform index-based
operations and store duplicates in it.
 It’s much more flexible and helpful than the traditional
array in Java.
 The ArrayList class in Java implements the List interface
and inherits the AbstractList class.
 Please note that you can’t use primitive data types such
as char, int, etc. with it.
 Instead, you can use wrapper classes for each of them.
Object Oriented Programming - CoSc2051 21
 Introduction to Data structure
 ArrayList in Java

import java.util.ArrayList;
import java.util.List;

public class ListExample {

public static void main(String[] args) {

// Implement ArrayList class using the myList.

ArrayList<Integer> ls = new ArrayList<Integer>();
ls.add(1);
ls.add(2);
ls.add(3);
System.out.println(ls);
}
}

Object Oriented Programming - CoSc2051 22

 Introduction to Data structure
 Iterating the List in Java

// Implement ArrayList class using the myList.

List<String> myList = new ArrayList<String>();

// Add String objects to the list

myList.add("Welcome ");
myList.add("to ");
myList.add("Java List");
//System.out.println(myList);

//Basic for loop

for(int i=0; i<myList.size(); i++){
System.out.println(myList.get(i) + " ");
}

Object Oriented Programming - CoSc2051 23

 Introduction to Data structure
 List Vs ArrayList in Java

List
. ArrayList
It’s categorized as an interface. It’s a class that implements
the list interface.
The list interface extends the It extends the AbstractList
collection framework. class.
It allows faster object It’s slower than a list.
manipulation compared to
ArrayList.
You can’t instantiate them. It can be instantiated.
They are not dynamic. We can expand them
dynamically.

Object Oriented Programming - CoSc2051 24

 Introduction to Data structure
 List Methods in Java

.
Method Descriptions
size() It is used to return the total number of
elements in the List
add(int index, It is used to insert the element or object
Object obj) at the specified index.
add(Object obj) This method is used to append the
element at the end of the list.
isEmpty() It is used to check whether or not the list
is empty.
remove(Object Removes the elements of a collection
obj) from the List
listIterator() It returns an iterator that points towards
the start of the list.

Object Oriented Programming - CoSc2051 25

 Introduction to Data structure
 Queue in Java
 A queue is similar to a checkout line in a supermarket
– the first person in line is serviced first, and other
customers enter the line only at the end and wait to be
serviced.
 Queue nodes are removed only from the head of the queue
and are inserted only at the tail.
 For this reason, a queue is referred to as a first-in, first-out
(FIFO) data structure.
 The insert and remove operations for a queue are known as
enqueue and dequeue.
 Java.Util.Queue contains multiple elements before the
Object Oriented Programming - CoSc2051 26
process.
 Introduction to Data structure
 Implementation of Queue in Java

 The queue is an interface that is required to manifest a

concrete implementation of the interface to use.
 Implementation of Java is below:
 Java.util.LinkedList
 Java.util.PriorityQueue
 Linked List:
 A linked list is a data structure similar to arrays.
 It interconnects each node to the next node through a
memory address link.
 A linked list has three elements:

Object Oriented Programming - CoSc2051 27

 Introduction to Data structure
 Implementation of Queue using Linked List:

 A linked list has three elements:

 Head
 Nodes
 Tail

Object Oriented Programming - CoSc2051 28

 Introduction to Data structure
 Implementation of Queue using Linked List:

import java.util.LinkedList;
import java.util.Queue;
 A linked list has three elements:
public class QueueExample {
 Head
public static void main(String[] args) {
/* Queue is a interface it has two methods to add
 Nodes
elements */
Queue<Integer> queueOne = new LinkedList<>();
 Tail
queueOne.add(6); //add method to use insert element
queueOne.add(1);
queueOne.add(8);
queueOne.add(4);

System.out.println("Example with Add method The queue is:

" + queueOne);
}
}
Object Oriented Programming - CoSc2051 29
 Introduction to Data structure
 Implementation of Queue using Linked List:
 import
.g java.util.LinkedList;
import java.util.Queue;
 A linked list has three elements:
public class QueueExample {
public
 Headstatic void main(String[] args) {
/* Queue is a interface it has two methods to add
elements
 Nodes */
Queue<String> queueTwo = new LinkedList<>();
queueTwo.offer("One");
 Tail //offer method to use insert
element
queueTwo.offer("Two");
queueTwo.offer("Three");
queueTwo.offer("Four");

System.out.println("Example with Offer method The queue

is: " + queueTwo);
}
}
Object Oriented Programming - CoSc2051 30
 Introduction to Data structure
 Queue Methods Interface

Method
.g Description
Inserts the specified element into the
add()
queue.
It is used to insert the specified element
offer(object)
into this queue.
element() - Returns the head of the queue.
element()
Throws an exception if the queue is empty.
Returns the head of the queue. Returns
peek()
null if the queue is empty.
Object It is used to retrieves and removes the
remove() head of this queue.
It is used to retrieves and removes the
Object poll() head of this queue, or returns null if this
queue is empty.
Object Oriented Programming - CoSc2051 31
 Introduction to Data structure
 Map/ dictionary

 Maps map keys to values and cannot contain duplicate keys.

 Maps differ from Sets in that Maps contain both keys and
values, whereas Sets contain only values.
 HashMaps store elements in a hashtable, and TreeMaps store
elements in a tree.
 Hashtables and HashMaps store elements in hash tables, and
TreeMaps store elements in trees.
 HashMap is a generic class that takes two type arguments.
 The first type argument specifies the type of key, and
 The second the type of value.

Object Oriented Programming - CoSc2051 32

 Introduction to Data structure
 Map/ dictionary

 We can access and modify values using the keys associated

with them.
 Note: The Map interface maintains 3 different sets:
 the set of keys
 the set of values
 the set of key/value associations (mapping).
 Hence we can access keys, values, and associations
individually.

Object Oriented Programming - CoSc2051 33

 Introduction to Data structure
 Map Implementation

 Since Map is an interface, we cannot create objects from it.

 In order to use functionalities of the Map interface, we can
use these classes:
 HashMap
 EnumMap
 LinkedHashMap
 WeakHashMap
 TreeMap
 These classes are defined in the collections framework and
implement the Map interface.

Object Oriented Programming - CoSc2051 34

 Introduction to Data structure
 Map Implementation Example

 Since Map is an interface, we cannot create

import java.util.HashMap;
import java.util.Map;
objects from it.
public
 class MapExample {
In order to use functionalities of the Map interface,
public static void main(String[] args) {
we can use these classes:
// Creating a map using the HashMap
 Map<String, Integer> numbers = new HashMap<>();
HashMap
// Insert elements
 EnumMap to the map
numbers.put("One", 1);
 numbers.put("Two", 2);
LinkedHashMap
System.out.println("Map: " + numbers);
 WeakHashMap
 TreeMap
 These classes are
Object Oriented Programming - CoSc2051
defined in the collections
35
 Introduction to Data structure
 Map Implementation Example

// Access keys of the map

System.out.println("Keys: " + numbers.keySet());
// Access values of the map
System.out.println("Values: " + numbers.values());

// Access entries of the map

System.out.println("Entries: " +
numbers.entrySet());

// Remove Elements from the map

int value = numbers.remove("Two");
System.out.println("Removed Value: " + value);
}
}

Object Oriented Programming - CoSc2051 36

 Introduction to Data structure
 Map Methods in Java

Method Descriptions
put(K, V) Inserts the association of a key K and a value V into the
map. If the key is already present, the new value replaces
the old value.
putAll() Inserts all the entries from the specified map to this map.
get(K) Returns the value associated with the specified key K. If
the key is not found, it returns null.
replace(K, Replace the value of the key K with the new specified
V) value V.
remove(K) Removes the entry from the map represented by the key
K.
values() Returns a set of all the values present in a map.
remove(K, Removes the entry from the map that has key K
V) associated with value V.
keySet() Returns a set ofOriented
Object all the keys present
Programming in a map.
- CoSc2051 37
 Bye

Take a look :
https://docs.oracle.com/en/java/

Object Oriented Programming - CoSc2051 38