JOSE RIZAL MEMORIAL STATE UNIVERSITY

The Premier University in Zamboanga del Norte

DATA STRUCTURES AND ALGORITHMS

Data Structures and Algorithms

Unit 1- Introduction to Data Structures and Algorithms

This unit introduce students to data structures and algorithms. This will
explain the importance of analyzing algorithms, pseudocodes and understand
the basic concept of data structures and algorithms.

Learning Outcomes

At the end of this unit, you will be able to:

● Demonstrate the process of problem solving through the use of algorithms.

● Describe data type, abstract data type and data structure.
● Differentiate algorithms and pseudocodes.

Pretest

Multiple Choice:
Direction: Encircle the letter of the correct answer

1. ____________ is a step-by-step procedure in solving a problem.

a. Software
b. Computer
c. Algorithm
d. Computer Procedure
2. ____________ refers to the data that a variable can hold in programming
language?
a. Structure
b. Data Structures
c. Data Types
d. Data
3. __________ is an artificial language used to describe computer program without
using the syntax of any particular programming language.
a. Algorithm
b. Programming Languages

1
Data Structures and Algorithms

c. Machine language
d. Pseudocode
4. ____________ are specialized format for storing and organizing data in a
computer’s memory or disk.
a. Data Structures
b. Data
c. Pseudocode
d. Algorithms
5. ____________ refers to a specification of a set of data and set of operations
performed in a data.
a. Information
b. Abstract Data Types
c. Data
d. Data Structures

Thank you for answering the pre-test.

Please see page 48 for the correct answer.
Keep on reading to learn more.

Content

Algorithms

Algorithm is a well-defined procedure in solving a problem. It takes some values

for input and process these values to produce an output. Algorithms are used to solve
computational problems. It describes a computational procedure for achieving that input/
output relationship (Cormen et al.,2009).

Every algorithm must satisfy the following criteria:

1. Input
2. Output
3. Definiteness
4. Finiteness
5. Effectiveness.

An algorithm should have an input and must produce an output. It should be

definite; definiteness means each instruction must be clear and unambiguous. Finiteness
means that an algorithm should terminate after a number of steps. Effectiveness means
every instruction must be sufficiently basic that it can, in principle, be carried by a person,
and operations must be feasible.

2
Data Structures and Algorithms

Example 1:
Create an algorithm that computes for the average score of the student based on
the three quizzes.

1. Get the scores of the student on the three quizzes.

2. Get the sum of the three scores.
3. To get the average, divide the sum of the three scores by 3.
4. Display the average.

Example 2:
Create an algorithm that will determine if the number entered by the user is an odd
or even number.

1. Get the number.

2. Divide the number by 2.
3. If the remainder is equal to 0, the number is even, else the number is odd.
4. Display the result.

Example 3:
Create an algorithm that find the smallest number between two integers.

1. Get 2 numbers and assigned them to x and y.

2. Test if x is less than y
If yes, x is the smallest number, else y is the smallest number.
3. Display the smallest number.

To learn more on algorithm,

please watch this video by clicking
the link below:
https://www.youtube.com/watch?v=kM9ASKAni_s
Keep on reading to learn more.

Pseudocode

Pseudocode is a methodology used by the programmer to represent the

implementation of algorithm. It is an algorithm in the form of annotations and informative
text written in plain English. Unlike programming language, it has no syntax and can’t be
complied and interpreted by a computer (GeeksforGeeks, 2018).

Pseudocode uses a short terms or simple English language syntax to write code
for a program, these codes are then converted to a specific programming language. The
purpose of using pseudocode is to identify the top-level flow errors and understand the
programming data flows. This will save the programmer’s time in the actual programming
because conceptual errors have been already corrected (The Economic Times, 2020).

3
Data Structures and Algorithms

GeeksForGeeks (2020) suggested to follow the following steps in creating

pseudocode:

1. Arrange the sequence of tasks and write the pseudocode accordingly.

2. Start with the statement of pseudocode which establishes the main goal of the aim.
3. The way the if-else, for, while loops are indented in a program, indent the
statements likewise, as it helps to comprehend the decision control and execution
mechanism. They also improved the readability to a great extent.
4. Use appropriate naming conventions. The human tendency follows the approach
to follow what we see. If a programmer goes through a pseudocode, his approach
will be the same as per it, so the naming must be simple and distinct.
5. Use appropriate sentence casings, such as CamelCase for methods, upper case
for constants and lower case for variables.
6. Elaborate everything which is going to happen in the actual code. Don’t make the
pseudocode abstract.
7. Use standard programming structures such as ‘if-then’, ’for’, ’while’, ’cases’ the
way we use it in programming.
8. Check whether all the sections of a pseudocode is complete, finite and clear to
understand and comprehend.
9. Don’t write the pseudocode in a complete programmatic manner. It is necessary
to be simple to understand even for a layman or client, hence don’t incorporate too
many technical terms.

Example 1:

Create a pseudocode for determining if the number entered by the user is an even
or odd number.

This program will determine if the number entered by

the user is an even number or odd number.

get number
if number divide by 2 is equal 0
print “even number”
else
print “odd number”

Example 2:

Create a pseudocode that ask for a grade from the user and determine if the
entered grade has a remark of passed or failed.

This program will determine if the grade entered has a

remark of passed or failed.

get grade
if grade is greater than or equal to 75
print “Passed”
else
print “Failed” 4
Data Structures and Algorithms

To learn more on writing pseudocode

please click this link:
https://www.youtube.com/watch?v=D0qfR606tVo
Keep on reading to learn more.

Data Structures

Data is an individual facts, statistics, or items of information. It is a body of facts or

information (Dictionary.com, 2012). Data are values or a set of values that are in a
particular format. A data refers to a single set of values, most data are categorized and
are grouped. Most organization today collect data for decision making and Data
processing to increased productivity and profit. Figure 1 is an example of data.

Figure 1
Note: An example of Data. Adapted from “Data Structures Introduction” by w3schools,
2018. https://www.w3schools.in/data-structures-tutorial/intro/

Data types refers to a data that a variable can hold in programming language. Data
types are used by the programmers for referencing to ensure that the program comes up
with the proper result and is error-free (Computer Hope, 2020)

Abstract Data Type is a special kind of datatype, whose behavior is defined by a

set of values and set of operations. We can perform different operations of an Abstract
Data Type. Abstract Data Type is made of with primitive datatypes, but operation logic is
hidden (tutorialspoint, 2020). Programmers combine data structures with operations and
call it Abstract Data Type to simplify the process of problem solving.

Abstract Data Type is composed of two parts, the declaration of data and the
declaration of operations. Commonly used Abstract Data Types are Linked List, Queues,

5
Data Structures and Algorithms

Priority Queues, Binary Trees, Dictionaries, Hash tables and many others (Karumanchi,
2017). This topic will be discussed in the following unit.

Data Structure is a way to store and organize data in a computer’s memory so that
these data can be used later on. We can arrange data in many different ways, such as
logical. We have two categories of Data Structure; these are linear data structures and
non-linear data structures. In linear data structures, elements are accessed in a sequential
order. In non-linear data structures, elements are stored/accessed in a non-linear order.
Example of linear data structures are Linked list, Stacks and Queues, while in non-linear
data structures are trees and graphs (Karumanchi, 2017).

Analysis of Algorithms

There are many ways to solve a problem, but we always choose the one that will
fit the situation. Analyzing the algorithm is determining the amount of resources necessary
to execute it, such as time and storage. There are three types of analysis:

1. Worst case – defines the input for which the algorithm takes a long time.
2. Best case – defines the input for which the algorithm takes the least time.
3. Average case – provides a prediction about the running time of the algorithm.

6
Data Structures and Algorithms

Learning Activities

Activity 1: Compare / Contrast Diagram

Compare or contrast the two items in the box below. Write the comparison below
the “HOW ALIKE?” box and write its differentiation below the “HOW DIFFERENT?” box.

ALGORITHM PSEUDOCODE

HOW ALIKE?

HOW DIFFERENT?

7
Data Structures and Algorithms

Assessment

Activity 1. Problem Solving.

1. Create an algorithm and pseudocode to find the largest value of any three
numbers.

Algorithm:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

Pseudocode:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

8
Data Structures and Algorithms

2. Create an algorithm and pseudocode in converting temperature from Fahrenheit

to Celsius. Temperature in Fahrenheit is the input and temperature in Celsius is
the output. Use this formula: ˚C = (˚F – 32 ) x 5 / 9

Algorithm:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

Pseudocode:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

9
Data Structures and Algorithms

Activity 2.
ESSAY: Answer the following questions:
1. Explain and differentiate Data and Data Types.

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
2. What is Abstract Data Type?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
3. Define data Structure and state its use.

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

10
Data Structures and Algorithms

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Activity 3. Programming
In creating programs in this course, we can utilize compiler application that can be
downloaded and installed on smart phone. If you have laptops or personal computers at
home you can also download any compiler to write and run your code.
For those who have smart phone you can install this application for you to write
and run a code.
Application name: AIDE – IDE for Android Java C++

11
Data Structures and Algorithms

Install and open the application. This will be the default view of the app:

You can edit the code by just typing in the white space.

12
Data Structures and Algorithms

You can run the code by pressing the button.

1. Now create a program that will convert temperature from Fahrenheit to Celsius.
Temperature in Fahrenheit is the input and temperature in Celsius is the output.
Use this formula: ˚C = (˚F – 32 ) x 5 / 9. Screenshot your code and the output and
submit it in our google classroom. Using this classroom code: e6u3rbj.

Congratulations! If you have questions regarding the

activities on this unit, feel free to message me in our
Google Classroom or send me a personal message
on the contacts provided on your course guide.

13
Data Structures and Algorithms

Write your thoughts about the unit here:

____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________

14
Data Structures and Algorithms

References:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009).
Introduction to Algorithms.
GeeksforGeeks. A computer science portal for geeks (2018.
https://www.geeksforgeeks.org/how-to-write-a-pseudo-code/
The Economic Times (2020). Software-Development, Definition of 'Pseudocode'.
https://economictimes.indiatimes.com/definition/pseudocode
W3schools (2018). Data Structures Introduction. https://www.w3schools.in/data-
structures-tutorial/intro/
DICTIONARY.COM (2012). Data. https://www.dictionary.com/browse/data
Computer Hope (2020). Data Type. https://www.computerhoe.com/jargon/d/datatype.htm
Tutorialspoint (2020). Abstract Data Type in Data Structures.
https://www.tutorialspoint.com/abstract-data-type-in-data-structures
Narasimha Karumanchi (2017). Data Structures and Algorithms Made easy in Java. Data
Structure and Algorithmic Puzzles.
Joyce Farell. (2015). Programming Logic and Design Comprehensive.

Rubric in Essay:

Criteria Points
Answers use specific details from the 5
lessons in a very clear and reasonable way.
Answers use some details from the lesson 4
in a very clear and reasonable way.
Answers use specific but unrelated details. 2-3
Answers have no details from the lesson. 1

Rubric in Algorithm and Pseudocode

Criteria Points
The solution was properly organized. 5
The solution was organized. 4
Some parts of the solution are organized. 2-3
The solution is not organized. 1

15
Data Structures and Algorithms

Unit 2 – Basic Data Structures and Algorithms

This unit will discuss the basic data structures and algorithms. This will
present the discuss the basic data structures and algorithms such as Array,
Linked List, Stack, Queues and Hash Tables.

Learning Outcomes

At the end of this unit, you will be able to:

● Define and describe Array, Linked List, Stacks, Queues and Hash Table.
● Write, test, debug programs and implement Array, Linked List, Stacks, Queues and
Hash Tables.

Pretest

Matching Type: Direction: Match column A to column B. Write the answer on the space
provided.

Column A

_________ 1. It is a linear structure that that follows the First In First Out (FIFO) order in
performing operation.
_________ 2. An ordered collection of data items of the same type referred to collectively
by a single name.
_________ 3. A data structure which is designed to use a special function called the hash
function.
_________ 4. It is a data structure that has a linear structure which follows the Last In
First Out (LIFO) or First In Last Out (FILO) order in performing an operation.
_________ 5. It is a sequential data structure.

Column B
a. Trees d. Array
b. Stack e. List
c. Queue f. Hashing

16
Data Structures and Algorithms

Thank you for answering the pre-test.

Please see page 48 for the correct answer.
Keep on reading to learn more.

Content

Array

Array is an ordered sequence of related values and objects. It is used to store

multiple values in a single variable. Array is the commonly used data structure storage,
built into most programming languages. An array group the same variables to easily
manage it instead of declaring it one by one (Goodrich et al., 2014)

Array Name

elements
Scores:

78 98 95 87 88 82 75 73 82 81
0 1 2 3 4 5 6 7 8 9

Indices

Figure 2

Figure 2 shows the illustration of an array. The name of the array is Scores and it
has 10 elements inside it. Notice that all the elements has the same data type which is
integer, an array can only hold elements with the same data type. Values stored in an
array is called elements. As shown in figure 2 the elements of the Scores array are 78,
98, 95, 87, 88, 82, 75, 73, 82 and 81. The length of the array refers to the capacity of the
array, in the above example, the length of the Score array is 10. Each variable in the array

17
Data Structures and Algorithms

has an index, an index uniquely refers to the value stored in a cell. The cells of an array
are numbered 0, 1, 2, 3 and so on. In the example shown in figure 2 index 4 has an
element of 88.

Example 1: Now let’s have a sample code for array. Supposed we want to write a code
for storing scores in an array and display these scores.

Figure 3

The figure above shows the code for getting 5 scores from the user and displaying
it. Let’s understand it line by line.

Line 1: import java.util.Scanner is a class in the Java API that can be used to input
alphanumeric characters from an output source.
Line 2: Declares Scores as the class name.
Line 4: The main class.
Line 5: Initialize Scanner to create a new scanner instance which point to the input
stream as passed argument.
Line 6: Declare array Score with 5 as its length.
Line 7: Display the line “Enter 5 scores:”.
Line 8: for loop for accessing the indices in the array.
Line 10: Assign the scored entered by the user to the indices of the array.
Line 12: Display the line “You have entered the following scores: “.
Line 13: for loop for accessing the indices in the array.
Line 15: Displays the 5 scores entered the user separated by a single space (“ “).

18
Data Structures and Algorithms

Program output:

Figure 4

It will allow the user to enter 5 scores, suppose we enter 76,87,90, 95 and 81.

Figure 5

The program will then display the 5 scores we have entered earlier.

Figure 6

You can also run this program using smart phones compiler application. Sample
application are shown in unit 1. Figure 7 shows how to run it using a smart phone
application.

19
Data Structures and Algorithms

Figure 7

20
Data Structures and Algorithms

Example 2: Let’s try another data type, suppose you want to write a program that accepts
3 names and display it.

Figure 8

21
Data Structures and Algorithms

Example 3: Create a program that will let the user save an integer value in any index
he/she wants to choose.

Figure 9

22
Data Structures and Algorithms

To learn more on array, visit this site for java

array practice programming question and solution:
https://www.5balloons.info/java-array-practice-
programming-questions-and-solutions/
Keep on reading to learn more.

Linked List

Linked list is a linear data structure, where elements are connected together via
links. It provides an alternative to an array-based structure. It is a collection of nodes in a
form of a linear sequence. A linked list has the following properties (Karumanchi, 2017):

• Successive elements are connected by pointer

• The last element points to NULL.
• Can grow or shrink in size during execution of a program
• Can be made just as long as required (until systems memory exhaust)
• Does not waste memory space (but takes some extra memory for pointers). It
allocates memory as list grows.

There are two types of linked list:

• Singly-linked list
• Doubly-linked list

Each node in a singly-linked list stores a reference to an object that is an element of

the sequence, as well as a reference to the next node of the list. Item navigation in a
singly-linked list is forward only (Goodrich et al., 2014).

Figure 10
Note: A representation of singly-linked list from “Linked List” by Carnegie Mellon
University School of Computer Science (2009).
https://www.cs.cmu.edu/~adamchik/15-
121/lectures/Linked%20Lists/linked%20lists.html

As represents above in figure 10, a singly-linked list has a node. A node comprises
of two items namely; the data and the reference to the next node. The first node is the
head and the last node has a reference to null. A linked list is a dynamic structure, this
means that the number of nodes is not fix, it can grow or shrink. In a singly-linked list the

23
Data Structures and Algorithms

elements are in a certain order, this order is determined by a chain of next links going from
each node to its successor in the list.

Here is an algorithm in creating singly-linked list from javaTpoint (2011):

1. Create a class Node which has two titles: data and next. Next is a pointer to the
next node.
2. Create another class which has two attributes: head and tail.
3. addNode() will add a new node to the list:
a. create a new node.
b. It first checks, whether the head is equal to null which means the list is
empty.
c. If the list is empty, both head and tail will point to the newly added node.
d. If the list is not empty, the new node will be added to end of the list such
that tail’s next point to the newly added node. This new node will become
the new tail of the list.
The display() will display the nodes present in the list.

24
Data Structures and Algorithms

Figure 11

25
Data Structures and Algorithms

Figure 12

Figure 11 is the sample code of adding a node to the singly-linked list. The program
created a list with 4 nodes; 1,2,3 and 4. The program will display these nodes and ask the
user if he/she wants to add another node (1-yes and 0-no). If the user chooses 1, he/she
will then be asked to enter a number, this number will then be the new node added to the
tail of the list. If the user chooses no, then the program exits. Please try running the code
to fully understand its process. Figure 12 is the output of the program.

Figure 13
Note: A representation of Doubly-linked list from “Linked List” by Carnegie Mellon
University School of Computer Science (2009).
https://www.cs.cmu.edu/~adamchik/15-
121/lectures/Linked%20Lists/linked%20lists.html

A doubly-linked list is a list with two references, one to the next node and the other
to the previous node. Figure 13 shows the representation of doubly-linked list.
(Adamchik, 2009)

Algorithm in creating a doubly-linked list from javaTpoint (2011):

1. Define a Node class which represents a node in the list. It will have three
properties: data, previous which will point to the previous node and next which will
point to the next node.
2. Define another class for creating a doubly-linked list, and it has two nodes: head
and tail. Initially, head and tail will point to null.
3. addNode() will add node to the list.

26
Data Structures and Algorithms

a. It first checks whether the head is null, if yes, then it will insert the node as
the head.
b. Both head and tail will point to a newly added node.
c. Head’s previous pointer will point to null and tail’s next pointer will point to
null.
d. If the head is not null, the new node will be inserted at the end of the list
such that new node’s previous pointer will point to tail.
e. The new node will become the new tail. Tail’s next pointer will point to null.

Display() will show all the nodes present in the list.

• Define new node ‘current’ that will point to the head.
• Print current.data till current points to null.
• Current will point to the next node in the list in each iteration.

27
Data Structures and Algorithms

Figure 14

28
Data Structures and Algorithms

Figure 15

Figure 14 is the sample code of adding a node to the doubly-linked list. The
program created a list with 4 nodes; 1,2,3 and 4. The program will display these nodes
and ask the user if he/she wants to add another node (1-yes and 0-no). if the user chooses
1, he/she will then be asked to enter a number, this number will then be the new node
added to the tail of the list. If the user chooses no, then the program exits. Please try
running the code to fully understand its process. Figure 15 is the output of the program.

There are a lot of operations that we can performed in a linked list, one of it is the
example above that adds node to the list. Here are the operations in linked list (Adamchik,
2009).:
• Adding at the beginning of the list – create a node and prepends it at the beginning
of the list.
• traversing – starts with the head and access each node until you reach null.
• Adding at the end of the list – create a node and appends the node to the end of
the list. this requires traversing.
• Inserting “after” – find a node containing a key and insert a new node after it.
• Inserting “before”- find a node containing a key and insert a new node before that
node.
• Deletion – find a node containing a key and delete it.

Stacks

Stack is a collection of objects that are inserted and removed accordingly to the
last in first-out (LIFO) principle. Stack was derived from the metaphor of stack of plates in
a spring-loaded, cafeteria plate dispenser (Goodrich & Tamassia, 2004). When you add
plate on the stack, you add it at the top of the stack and when you remove a plate from
the stack you also get it from the top of the stack.

29
Data Structures and Algorithms

There are 2 operation perform in stack:

• Push – adding or pushing an element on the stack.
• Pop – removing an element from the stack.

To check the status of the stack we will use the following functionality:
• peek – get the top data element of the stack, without removing the element.
• Is full – check if the stack is full.
• Is empty – check if the stack is emty.

Figure 16
Note: A representation of stack and its operations from “Data Structure and Algorithms”
by Tutorialspoint (2020).
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

Figure 16 shows the representation of stacks including its operation. As you can
see, operations are performed at the top of the stack.

Figure 17

30
Data Structures and Algorithms

Figure 17 shows the sample operation of stack. First it pushed 6 in the stack, then
pushed 5, and then pushed 1 in the stack. Now the stack contains 1, 5 and 6. A pop
operation was then called. Take note that the operation on stack follows the Last in First-
Out procedure, the last pushed element was 1, so when the pop operation was performed
the last pushed element was removed. The remaining element now is 5 and 6.

The algorithm to perform push operation in a stack is as follows:

1. Check if the stack is full.
2. If it is full, produce a message telling the user that it is full.
3. If stack is not full, increment the top to point to the next empty space.
4. Add the new data element to the stack location, where the top is pointing.
5. Return success.

Pop operation algorithm:

1. Check if the stack is empty.
2. If the stack is empty, produce a message telling the user that it is empty.
3. If the stack is not empty, access the data element at which top is pointing.
4. Decrease the value of the top by 1.
5. Return success.

31
Data Structures and Algorithms

Figure 18

32
Data Structures and Algorithms

Figure 19

Figure 18 is a sample stack program with its operation and functionalities. Figure
19 is the output of the program. To illustrate the output, please refer to Figure 20. First the
user entered 7 to be pushed in the stack, then pushed other elements which are 4, 5, and
9. Then it perform a pop operation, which pops 9 because it was the last element that the
user pushed, and perform pop operation again to remove other element which is 5. Now,
the remaining element is 4 and 7 and the peek is 4.

Figure 20

Queues

Queue is a collection of objects that are inserted and remove accordingly to the
First-In First-Out (FIFO) principle. Unlike stack, a queue is open at both its ends. One end
is always used for insertion and the other one is for removing element. Elements are
inserted into the queue at the rear end and removed from the queue at the front. In the
FIFO methodology, the data item stored first will be accessed first. Figure 21 shows the
illustration of queue data structure.

33
Data Structures and Algorithms

Figure 21

Queue Basic Operation:

• Enqueue – insert/add item to the queue.
• Dequeue – remove/delete item from the queue.
Queue Functions
• Peek – get the element at the front of the queue without removing it.
• Is full – checks if the queue is full.
• Is empty – checks if the queue is empty.

Figure 22

Figure 22 shows the operation on queue. First it performs an enqueue operation

inserting 7, then it inserts elements 4, 5, and 9. Then it performs the dequeue operation.
In removing element in queue we follow the First-In First-Out principle, which says the first
elements that has been added in the queue should also be the first one to be remove in
the queue. In the figure above when the dequeue operation was first called, it removes
the element 7 since it is the first element inserted in the queue. Then it again performs
dequeue operation which deleted 4. Now the queue has only 9 and 5 as its elements.

34
Data Structures and Algorithms

Figure 23

35
Data Structures and Algorithms

Figure 24

Figure 23 shows the sample program of queue and its operations and functions.
Figure 24 is the output of the program. The program let the user choose 1 for
enqueue/add, 2 for dequeue/remove, 3 to view the front and rear element and 4 for exit.
The figure below shows the illustration of the program above. The user enqueue the
numbers 1,2,3,4, and 5. Then it performs a dequeue operation which removes the element
1. And another dequeue operation, which removes the element 2. Leaving the elements
5,4, and 3 in the queue. 5 is the rear and 3 is the front.

Figure 25

36
Data Structures and Algorithms

Hash Table

Hashing a technique used to identify a specific object from a group of similar

objects. One best example of hashing are the library books which are assigned to a
unique number that can be used to determine information about the book, such as its
exact position in the library. Books are hashed to a unique number. The steps in hashing
are as follows (HackerEarth, 2020):

1. An element is converted into an integer by using a hash function. This element can
be used as an index to store the original element, which falls into the hash table.
2. The element stored in the hash table where it can be quickly retrieved using
hashed key.

A hash function determines the index of our key-value pair. Hash function can be used
to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash
table. The following are the basic requirements for a good hashing mechanism:
1. Easy to compute. It should be easy to compute and must not become an algorithm
in itself.
2. Uniform distribution: it should provide a uniform distribution across the hash table
and should not result in clustering.
3. Less collisions: Collisions occur when pairs of elements are mapped to the same
hash value. These should be avoided.

Hash table is a data structure that store data in an array format, where each data value
has its own unique index value. Supposed you want to create a table for these data:

Name ID Address
Anna 12345 Makati City
Kyle 12346 Malabon City
Peter 12347 Marikina City

But obviously we can’t apply linked list on these because we have rows and columns. The
perfect data structure to use in this is hash tables. The hash functions turn the elements
to integer and use that integer to compute for the index in the array. Let’s say we will
compute for the index using the letters in the alphabet in which a =1, b=2, c=3 and so on.

A=1 K = 11 P = 16
N = 14 Y = 25 E=5
N = 14 L = 12 T = 20
A = 11 E=5 E=5
R = 18
1+14+14+11 = 40 11+25+112+5 = 53
16+5+20+5+18 = 64

37
Data Structures and Algorithms

Figure 26

Figure 26 shows how we save our data using the computation we have above.
Anna is store in index 40, Kyle is store in index 53, and Peter is store in index 64.

Basic operations on hash table (tutorialspoint, 2020):

• Search - searches an element in a hash table.
• Insert - inserts an element in a hash table.
• Delete – deletes an element from a hash table.

38
Data Structures and Algorithms

Figure 26

39
Data Structures and Algorithms

Figure 27

Figure 26 shows the sample code of hashing, in the example above we used the
embedded classes of hash table in java. In using a class, we can just call it directly
and it will automatically perform the operation. Note that most of the data structures
above can be readily used by accessing its java packages. It’s a built-in and user-
defined packages into the java source file so that the class you use can refer to a class
that is in another package by directly using its name. Figure 27 shows the output of
the program.

To learn more on writing hash table

please click this link:
https://www.geeksforgeeks.org/hashtable-in-java/
Keep on reading to learn more.

40
Data Structures and Algorithms

Learning Activities

Activity 1: Retrieval Chart

Fill in the tables based on its heading.

Topic Description My Knowledge and

Understanding

Array

Linked List

Stack

41
Data Structures and Algorithms

Queue

Hash Table

Assessment

Activity 2. Problem Solving.

3. Create an algorithm in inserting element in an array with 10 as its size.

Algorithm:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

42
Data Structures and Algorithms

4. Create an algorithm in inserting 4 elements in a doubly-linked list.

Algorithm:
______________________________________________________________________
Activit
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

5. Create an algorithm in searching element in a hash table.

Algorithm:
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
_________________________________________________________

43
Data Structures and Algorithms

Activity 3: Illustration.
1. Illustrate the following operation on stack:
• Push 4
• Push 6
• Push 7
• Push 8
• Push 1
• Pop
• Pop
• Peek:

44
Data Structures and Algorithms

2. Illustrate the following operation on Queue:

• Enqueue 4
• Enqueue 6
• Enqueue 1
• Enqueue 10
• Dequeue
• Dequeue
• Front:
• Rear:

45
Data Structures and Algorithms

Activity 4. Programming. Create a program based on the following conditions and

screen shot the source code and the output and submit it in our google classroom.
1. Create a program that can insert, delete and search an element in an array.
2. Create a program that can delete an element in a singly-linked list based on the
entered element of the user.
3. Create a program that will enqueue the following elements: 2, 4, 5, 6 and 8. And
display the rear and front element.
4. Create a program that will check if the stack is empty or not.
5. Create a program that will search an element in a hash table.

Congratulations! If you have questions regarding the

activities on this unit, feel free to message me in our
Google Classroom or send me a personal message
on the contacts provided on your course guide.

Write your thoughts about the unit here:

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
__________________________________

46
Data Structures and Algorithms

References:
Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. (2014) Data Structures
and Algorithms in Java.
Narasimha Karumanchi, (2017). Data Structures and Algorithms Made Easy in Java
Data Structures and Algorithmic Puzzles.
Victor S. Adamchik.(2009). Linked List https://www.cs.cmu.edu/~adamchik/15-
121/lectures/Linked%20Lists/linked%20lists.html
javaTpoint. (2018). Java Program to create and display a singly linked list.
https://www.javatpoint.com/java-program-to-create-and-display-a-singly-linked-list
javaTpoint. (2018). Java Program to create and display a doubly linked list.
https://www.javatpoint.com/java-program-to-create-and-display-a-doubly-linked-
list#:~:text=Define%20another%20class%20for%20creating,the%20node%20as%20the
%20head
tutorialspoint. (2020). Data Structure and Algorithms.
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
GeeksforGeeks. (2018). Stack Data Structure (introduction and Program).
https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
Software Testing Help. (2020). Java Queue - Queue Methods, Queue Implementation
With Examples. https://www.softwaretestinghelp.com/java-queue-
interface/#:~:text=Answer%3A%20Queue%20in%20Java%20is,that%20inherits%20the
%20Collection%20interface.
tutorialspoint. (2020). Data Structure and Algorithms - Hash Table.
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm#:~:t
ext=Advertisements,index%20of%20the%20desired%20data
Study Tonight. (2020). Java Package. https://www.studytonight.com/java/package-in-
java.php#:~:text=To%20import%20java%20package%20into,by%20directly%20using%2
0its%20name

Rubric in Essay:

Criteria Points
Answers use specific details from the 5
lessons in a very clear and reasonable way.
Answers use some details from the lesson 4
in a very clear and reasonable way.
Answers use specific but unrelated details. 2-3
Answers have no details from the lesson. 1

47
Data Structures and Algorithms

Rubric in Algorithm and Pseudocode

Criteria Points
The solution was properly organized. 5
The solution was organized. 4
Some parts of the solution are organized. 2-3
The solution is not organized. 1

Answer Key: Unit 1

Multiple choice.
1. C
2. C
3. D
4. A
5. B

Answer Key: Unit 2

Matching Type.
1. B
2. D
3. F
4. C
5. E

48