Republic of the Philippines

City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Data Structures and Algorithms

Title: Linked Lists Lesson No: 6

I. INTRODUCTION
“Linking up the things you were with the things you become is what growing up is. “
James L. Brooks

A linked list is a linear collection of data elements whose order is not given by their physical
placement in memory. Instead, each element points to the next. It is a data structure consisting of a
collection of nodes which together represent a sequence. These nodes hold both the data and a
reference to the next node in the list. Linked lists are often used because of their efficient insertion
and deletion. They can be used to implement stacks, queues, and other abstract data types.
Compared to using Arrays to store data, arrays are static structures and therefore cannot be
easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions
and deletions. This will lead us to better understand the implementation of Linked Lists in data
structure.
However, unlike arrays which allow random access to the elements contained within them,
a link list only allows sequential access to its elements. Linked lists also use more storage space in a
computer's memory as each node in the list contains both a data item and a reference to the next
node.
There are various types of Linked List (LL): Simple or Singly LL, Doubly LL and Circular LL.
Concept of iterator and having a list of lists will also be introduced in this lesson. Arithmetic
sequences, Fibonacci and Catalan series, Pascal’s, Fractal and Sierpinski’s Triangles, Koch curve and
Snowflake are algorithms that will be examined as part of this lesson.

II. LEARNING OBJECTIVES

After studying this module, you should be able to:

• Understand how Linked List works and how to implement it in programming.
• Identify the types of Linked List and differentiate when to use one over the other in data
structure.
• Use and implement Linked List ADTs in programming.
• Perform operations using Linked List data structure to build CRUD structure of developing
programs/applications.

Author: Mr. Ronnie D. Luy, MIT Page | 1

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

III. TOPICS AND KEY CONCEPTS

A. Linked List Characteristics
Lists are linearly ordered collections. Some things we refer to in everyday life as lists, such as
shopping lists or laundry lists, are really sets because their order doesn’t matter. Order matters in
lists. A to-do list is really a list if the tasks to be done are in the order in which they are supposed to
be completed.
A linked list is a sequence of data structures, which are connected together via
links.

Linked List is a sequence of links which contains items. Each link contains a connection to another
link. Linked list is the second most-used data structure after array. Following are the important terms
to understand the concept of Linked List.
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
LinkedList − A Linked List contains the connection link to the first link called
First.

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.
• Linked List contains a link element called first.
• Each link carries a data field(s) and a link field called next.
• Each link is linked with its next link using its next link.
• Last link carries a link as null to mark the end of the list.

Each element (we will call it a node) of a list is comprising of two items - the data and a
reference to the next node. The last node has a reference to null. The entry point into a linked
list is called the head of the list. It should be noted that head is not a separate node, but the
reference to the first node. If the list is empty then the head is a null reference.

Author: Mr. Ronnie D. Luy, MIT Page | 2

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can
grow and shrink on demand. Any application which has to deal with an unknown number of
objects will need to use a linked list.

Advantages over arrays

1) Dynamic size
2) Ease of insertion/deletion

Drawbacks
1) Random access is not allowed. We have to access elements sequentially
starting from the first node. So, we cannot do binary search with linked lists
efficiently with its default implementation.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache friendly. Since array elements are contiguous locations, there is
locality of reference which is not there in case of linked lists.

Java program showing Linked List structure

class LinkedList {
Node head; // head of the list

/* Linked list Node*/

class Node {
int data;
Node next;

// Constructor to create a new node

// Next is by default initialized as null

Node(int d) { data = d; }
}
}

Simple linked list with 3 nodes

// A simple Java program to introduce a linked list
class LinkedList {
Node head; // head of list

/* Linked list Node. This inner class is made static so that

main() can access it */
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
} // Constructor
}

/* method to create a simple linked list with 3 nodes*/

public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();

Author: Mr. Ronnie D. Luy, MIT Page | 3

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

llist.head = new Node(1);

Node second = new Node(2);
Node third = new Node(3);

/* Three nodes have been allocated dynamically. We have references to these three
blocks as head, second and third */
llist.head.next = second; // Link first node with the second node

second.next = third; // Link second node with the third node

}
}

Linked List Traversal

/* This function prints contents of linked list starting from head */
public void printList()
{
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}

B. Types of Linked Lists

Following are the various types of linked list.

• Simple Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − Last item contains link of the first element as next and the first
element has a link to the last element as previous.

Single Linked Lists

The simplest list you can have is a single none ordered linked list. It is characterized by the list
consisting of elements (also called nodes) that contains a data object and a reference to the
next element/node.

Class Node
{
data
DataType data;
Node next;

A list is merely a reference to the element that is the first node in the list corresponding to the
figures above.

Author: Mr. Ronnie D. Luy, MIT Page | 4

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Doubly Linked List

A list that has two references, one to the next node and another to previous node.

The single linked list has its uses and is characterized by that it has a simple implementation, but
often you choose to implement a double linked list, where each node not only keeps track of the
successor, but also the predecessor. By giving the individual nodes a reference to the
predecessor, you will also be able to search backward, for example, to start at the end of the list
and traverse the list in the opposite direction. It is advantageous for many tasks, and some
methods can actually be implemented more easily, but the price is that the individual nodes
must contain an additional reference.

Class Node
{
data
DataType data;
Node previous;
Node next;

Advantages
• As each node has pointers pointing to the previous and next nodes, the doubly linked
list can be traversed easily in forward as well as backward direction
• You can quickly add the new node just by changing the pointers.
• Similarly, for delete operation since we have previous as well as next pointers, the
deletion is easier and we need not traverse the whole list to find the previous node as
in case of the singly linked list.

Disadvantages
• Since there is an extra pointer in the doubly linked list i.e. the previous pointer,
additional memory space is required to store this pointer along with the next pointer
and data item.
• All the operations like addition, deletion, etc. require that both previous and next
pointers are manipulated thus imposing operational overhead.

Author: Mr. Ronnie D. Luy, MIT Page | 5

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Circular Linked List

Another important type of a linked list is called a circular linked list where last node of the list
points back to the first node (or the head) of the list.

A double linked list can be implemented in several ways, and one of the options is like a
circular list, where the last node points to the first, while the first points back to the last one:

There is no longer any first and last element, and you refer to the list’s elements using an
internal reference, which refers to a current node. A class that implements such a data
structure must therefore have methods that can move this internal reference and insertion
in the list occurs before or after the node where current points. Similarly, deletion means
that the node where current currently should be removed.

Advantages of a Circular Double Linked List:

• The circular doubly linked list can be traversed from head to tail or tail to head.
• Going from head to tail or tail to head is efficient and takes only constant time O (1).
• It can be used for implementing advanced data structures including Fibonacci heap.

Disadvantages:

• As each node needs to make space for the previous pointer, extra memory is required.
• We need to deal with lots of pointers while performing operations on a circular doubly
linked list. If pointers are not handled properly, then the implementation may break.

Author: Mr. Ronnie D. Luy, MIT Page | 6

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

C. Linked List Operations and Representations

Singly Linked List

Following are the basic operations supported by a list or a single linked list.
1. Insertion − Adds an element at the beginning of the list.
2. Deletion − Deletes an element at the beginning of the list.
3. Display − Displays the complete list.
4. Search − Searches an element using the given key.
5. Delete − Deletes an element using the given key.

addFirst

The method creates a node and prepends it at the beginning of the list.

public void addFirst(AnyType item)

{
head = new Node<AnyType>(item, head);
}

Traversing

Start with the head and access each node until you reach null. Do not change the head
reference.

Node tmp = head;

while(tmp != null) tmp = tmp.next;

Author: Mr. Ronnie D. Luy, MIT Page | 7

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

addLast

The method appends the node to the end of the list. This requires traversing, but make sure
you stop at the last node

public void addLast(AnyType item)

{
if(head == null) addFirst(item);
else
{
Node<AnyType> tmp = head;
while(tmp.next != null) tmp = tmp.next;

tmp.next = new Node<AnyType>(item, null);

}
}

Inserting "after"

Find a node containing "key" and insert a new node after it. In the picture below, we insert a
new node after "e":

public void insertAfter(AnyType key, AnyType toInsert)

{
Node<AnyType> tmp = head;
while(tmp != null && !tmp.data.equals(key)) tmp = tmp.next;

if(tmp != null)
tmp.next = new Node<AnyType>(toInsert, tmp.next);
}

Author: Mr. Ronnie D. Luy, MIT Page | 8

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Inserting "before"

Find a node containing "key" and insert a new node before that node. In the picture below, we
insert a new node before "a":

For the sake of convenience, we maintain two references prev and cur. When we move along
the list we shift these two references, keeping prev one step before cur. We continue until cur
reaches the node before which we need to make an insertion. If cur reaches null, we don't insert,
otherwise we insert a new node between prev and cur.

public void insertBefore(AnyType key, AnyType toInsert)

{
if(head == null) return null;
if(head.data.equals(key))
{
addFirst(toInsert);
return;
}

Node<AnyType> prev = null;

Node<AnyType> cur = head;

while(cur != null && !cur.data.equals(key))

{
prev = cur;
cur = cur.next;
}
//insert between cur and prev
if(cur != null) prev.next = new Node<AnyType>(toInsert, cur);
}

Author: Mr. Ronnie D. Luy, MIT Page | 9

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Deletion

Find a node containing "key" and delete it. In the picture below we delete a node containing
"A"

The algorithm is similar to insert "before" algorithm. It is convenient to use two references prev
and cur. When we move along the list we shift these two references, keeping prev one step
before cur. We continue until cur reaches the node which we need to delete. There are three
exceptional cases, we need to take care of:
1. list is empty
2. delete the head node
3. node is not in the list

public void remove(AnyType key)

{
if(head == null) throw new RuntimeException("cannot delete");

if( head.data.equals(key) )
{
head = head.next;
return;
}

Node<AnyType> cur = head;

Node<AnyType> prev = null;

while(cur != null && !cur.data.equals(key) )

{
prev = cur;
cur = cur.next;
}

if(cur == null) throw new RuntimeException("cannot delete");

//delete cur node

prev.next = cur.next;
}

Author: Mr. Ronnie D. Luy, MIT Page | 10

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Doubly Linked List

Following are the basic operations supported by a doubly linked list.

1. Insertion − Adds an element at the beginning of the list.

2. Deletion − Deletes an element at the beginning of the list.
3. Insert Last − Adds an element at the end of the list.
4. Delete Last − Deletes an element from the end of the list.
5. Insert After − Adds an element after an item of the list.
6. Delete − Deletes an element from the list using the key.
7. Display forward − Displays the complete list in a forward manner.
8. Display backward − Displays the complete list in a backward manner.

addLast

The addition of new nodes is usually done at the end of the list. The below diagram shows
the addition of the new node at the end of the doubly linked list. To add a new node at the end of
the list, the next pointer of the last node now points to the new node instead of null. The previous
pointer of the new node points to the last node. Also, the next pointer of the new node points to
null, thereby making it a new last node.

//The program below shows Java implementation of a doubly-linked list with the addition of new nodes at the end of the
list.

class DoublyLinkedList {
//A node class for doubly linked list
class Node{
int item;
Node previous;
Node next;

public Node(int item) {

this.item = item;
}
}
//Initially, heade and tail is set to null

Author: Mr. Ronnie D. Luy, MIT Page | 11

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Node head, tail = null;

//add a node to the list

public void addNode(int item) {
//Create a new node
Node newNode = new Node(item);

//if list is empty, head and tail points to newNode

if(head == null) {
head = tail = newNode;
//head's previous will be null
head.previous = null;
//tail's next will be null
tail.next = null;
}
else {
//add newNode to the end of list. tail->next set to newNode
tail.next = newNode;
//newNode->previous set to tail
newNode.previous = tail;

//newNode becomes new tail

tail = newNode;
//tail's next point to null
tail.next = null;
}
}

//print all the nodes of doubly linked list

public void printNodes() {
//Node current will point to head
Node current = head;
if(head == null) {
System.out.println("Doubly linked list is empty");
return;
}
System.out.println("Nodes of doubly linked list: ");
while(current != null) {
//Print each node and then go to next.
System.out.print(current.item + " ");
current = current.next;
}
}
}
class Main{
public static void main(String[] args) {
//create a DoublyLinkedList object
DoublyLinkedList dl_List = new DoublyLinkedList();
//Add nodes to the list
dl_List.addNode(10);
dl_List.addNode(20);
dl_List.addNode(30);
dl_List.addNode(40);
dl_List.addNode(50);

//print the nodes of DoublyLinkedList

dl_List.printNodes();
}
}

Author: Mr. Ronnie D. Luy, MIT Page | 12

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Apart from adding a new node at the end of the

list, you can also add a new node at the
beginning of the list or in between the list. We
leave this implementation to the reader so that
the readers can understand the operations in a
better way.

Circular Linked List

Following are the important operations supported by a circular list.

• insert − Inserts an element at the start of the list.

• delete − Deletes an element from the start of the list.
• display − Displays the list.

In circular linked list, the next pointer of the last node points to the first node and the previous
pointer of the first node points to the last node making the circular in both directions.

Circular Linked List is a variation of Linked list in which the first element points to the last element
and the last element points to the first element. Both Singly Linked List and Doubly Linked List can
be made into a circular linked list.

Singly Linked List as Circular

In singly linked list, the next pointer of the last node points to the first node.

Author: Mr. Ronnie D. Luy, MIT Page | 13

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Doubly Linked List as Circular

In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of
the first node points to the last node making the circular in both directions.

As per the above illustration, following are the important points to be considered.
• The last link's next points to the first link of the list in both cases of singly as well as doubly linked
list.
• The first link's previous points to the last of the list in case of doubly linked list.

Advantages of Circular Linked Lists:

1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just
need to stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two
pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted
node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple
applications are running on a PC, it is common for the operating system to put the running applications
on a list and then to cycle through them, giving each of them a slice of time to execute, and then making
them wait while the CPU is given to another application. It is convenient for the operating system to
use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci
Heap.
Application of Circular Linked List
• The real-life application where the circular linked list is used is our Personal Computers, where
multiple applications are running. All the running applications are kept in a circular linked list
and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating
over the linked list until all the applications are completed.
• Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and
the pointer keeps on moving forward as a player's chance ends.
• Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two
pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one
pointer is required.

Author: Mr. Ronnie D. Luy, MIT Page | 14

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Insertion Operation

Following code demonstrates the insertion operation in a circular linked list based on single linked list.
insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
head := node
next of node = head
else
temp := head
while next of temp is not head, do
temp := next of temp
done
next of node := head
next of temp := node
head := node
end if
End

Deletion Operation

Following code demonstrates the deletion operation in a circular linked list based on single linked list.
deleteFirst():
Begin
if head is null, then
it is Underflow and return
else if next of head = head, then
head := null
deallocate head
else
ptr := head
while next of ptr is not head, do
ptr := next of ptr
next of ptr = next of head
deallocate head
head := next of ptr
end if
End

Author: Mr. Ronnie D. Luy, MIT Page | 15

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Display List Operation

Following code demonstrates the display list operation in a circular linked list.
display():
Begin
if head is null, then
Nothing to print and return
else
ptr := head
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End

D. ADT Lists and Interface

We all have an intuitive understanding of what we mean by a "list". We want to turn this intuitive
understanding into a concrete data structure with implementations for its operations. The most important
concept related to lists is that of position. In other words, we perceive that there is a first element in the
list, a second element, and so on. So, define a list to be a finite, ordered sequence of data items known
as elements. This is close to the mathematical concept of a sequence.

"Ordered" in this definition means that each element has a position in the list. So the term "ordered"
in this context does not mean that the list elements are sorted by value. (Of course, we can always choose
to sort the elements on the list if we want; it's just that keeping the elements sorted is not an inherent
property of being a list.)

Each list element must have some data type. In the simple list implementations discussed in this
chapter, all elements of the list are usually assumed to have the same data type, although there is no
conceptual objection to lists whose elements have differing data types if the application requires it. The
operations defined as part of the list ADT do not depend on the elemental data type. For example, the list
ADT can be used for lists of integers, lists of characters, lists of payroll records, even lists of lists.

A list is said to be empty when it contains no elements. The number of elements currently stored is
called the length of the list. The beginning of the list is called the head, the end of the list is called the tail.

We need some notation to show the contents of a list, so we will use the same angle bracket notation
that is normally used to represent sequences. To be consistent with standard array indexing, the first
position on the list is denoted as 0. Thus, if there are n elements in the list, they are given positions 0
through n−1 as ⟨ a0, a 1, ..., an−1 ⟩. The subscript indicates an element's position within the list. Using this
notation, the empty list would appear as ⟨ ⟩.

Author: Mr. Ronnie D. Luy, MIT Page | 16

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

The code below presents our list ADT. Any implementation for a container class such as a list should
be able to support different data types for the elements. One way to do this in Java is to store data values of
type Object. Languages that support generics (Java) or templates (C++) give more control over the element
types.

The comments given with each member function describe what it is intended to do. However, an
explanation of the basic design should help make this clearer. Given that we wish to support the concept of
a sequence, with access to any position in the list, the need for many of the member functions such
as insert and moveToPos is clear. The key design decision embodied in this ADT is support for the concept
of a current position. For example, member moveToStart sets the current position to be the first
element on the list, while methods next and prev move the current position to the next and previous
elements, respectively. The intention is that any implementation for this ADT support the concept of a
current position. The current position is where any action such as insertion or deletion will take place. An
alternative design is to factor out position as a separate position object, sometimes referred to as
an iterator.

// List class ADT. Generalize the element type using Java Generics.

public interface List<E> { // List class ADT

// Remove all contents from the list, so it is once again empty

public void clear();

// Insert "it" at the current location

// The client must ensure that the list's capacity is not exceeded

public boolean insert(E it);

// Append "it" at the end of the list

// The client must ensure that the list's capacity is not exceeded

public boolean append(E it);

// Remove and return the current element

public E remove() throws NoSuchElementException;

// Set the current position to the start of the list

public void moveToStart();

// Set the current position to the end of the list

public void moveToEnd();

// Move the current position one step left, no change if already at beginning

public void prev();

Author: Mr. Ronnie D. Luy, MIT Page | 17

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

// Move the current position one step right, no change if already at end

public void next();

// Return the number of elements in the list

public int length();

// Return the position of the current element

public int currPos();

// Set the current position to "pos"

public boolean moveToPos(int pos);

// Return true if current position is at end of the list

public boolean isAtEnd();

// Return the current element

public E getValue() throws NoSuchElementException;

// Tell if the list is empty or not

public boolean isEmpty();

A list can be iterated through as follows:

for (L.moveToStart(); !L.isAtEnd(); L.next()) {

it = L.getValue();

doSomething(it);

In this example, each element of the list in turn is stored in it, and passed to
the doSomething function. The loop terminates when the current position reaches the end of the list.

The list class declaration presented here is just one of many possible interpretations for lists. Our list
interface provides most of the operations that one naturally expects to perform on lists and serves to
illustrate the issues relevant to implementing the list data structure. As an example of using the list ADT, here
is a function to return true if there is an occurrence of a given integer in the list, and false otherwise.
The find method needs no knowledge about the specific list implementation, just the list ADT.

Author: Mr. Ronnie D. Luy, MIT Page | 18

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

// Return true if k is in list L, false otherwise

static boolean find(List L, Object k) {

for (L.moveToStart(); !L.isAtEnd(); L.next())

if (k == L.getValue()) return true; // Found k

return false; // k not found

IV. TEACHING AND LEARNING MATERIALS RESOURCES

• PC Computer || Laptop || Android Phone
• Installed C/Java programming language
o For downloads
▪ C/C++ → https://developerinsider.co/download-turbo-c-for-windows-7-8-8-1-
and-windows-10-32-64-bit-full-screen/
▪ Java → https://www.filehorse.com/download-java-runtime-64/download/
o For online compiler
▪ C/C++/Java → https://www.onlinegdb.com/online_c_compiler
▪ Java → https://www.jdoodle.com/online-java-compiler/
o For mobile user, download in the App store
▪ Java Editor
▪ AIDE-IDE for Android Java C++

V. LEARNING TASKS

A. ENGAGE
Activity: Pascal’s Triangle vs Sierpinski’s Triangle

Pascal's triangle is a triangular array constructed

by summing adjacent elements in preceding
rows.

The Sierpiński triangle, also called the Sierpiński

gasket or Sierpiński sieve, is a fractal attractive
fixed set with the overall shape of an equilateral
triangle, subdivided recursively into smaller
equilateral triangles.

Author: Mr. Ronnie D. Luy, MIT Page | 19

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

1. Create a design by coloring the Pascal’s and Sierpinski’s Triangles on the next page.
2. Try to observe both triangles. What is the relationship of Pascal’s Triangle and Sierpinski’s
Triangle?
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________

3. Build a 3D Sierpinski’s Triangle.

Author: Mr. Ronnie D. Luy, MIT Page | 20

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

Author: Mr. Ronnie D. Luy, MIT Page | 21

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

B. EXPLORE & EXPLAIN

1. Explain Fractal Triangles.

__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
2. Draw Koch Curve and Snowflakes given the initial figures and by repeating the process
several times.

Koch Curve Koch Snowflake

3. What is an iterator? How is it being used in creating fractal triangles? How can you apply it
in programming?
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
4. What is Catalan Numbers? What are the applications of Catalan Numbers? Give at least 3
example applications of Catalan Numbers. How can you use Pascal’s Triangle in
determining Catalan Numbers?
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________

Author: Mr. Ronnie D. Luy, MIT Page | 22

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

5. Complete the table of Catalan Numbers using the given formula.

n 0 1 2 3 4 5 6 7 8
Cn 1 1 2

When n = 0,
C0 = ___2n!___ = ___0!___ = __1__ = 1
(n+1)!n! (0+1)! 0! (1)(1)

When n = 1,
C1 = ___2n!___ = ___2!___ = __2__ = 1
(n+1)!n! (1+1)! 1! (2)(1)

When n = 2,
C2 = ___2n!___ = ___4!___ = __24__ = 2
(n+1)!n! (2+1)! 2! (6)(2)

6. What is Fibonacci Series? What are the applications of Fibonacci Series? Give at least 3
example applications of Fibonacci Series. How can you use Pascal’s Triangle in determining
Fibonacci Series?
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
7. Complete the table of Fibonacci Series given the following rule.

Xn = Xn−1 + Xn−2
n 0 1 2 3 4 5 6 7 8
Xn 0 1 1

When n = 2: X2 = X2−1 + X2−2 → X2 = X1 + X0 → X2 = 1 + 0 → X2 = 1

Author: Mr. Ronnie D. Luy, MIT Page | 23

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

C. ELABORATE & EVALUATION

1. Parts of the Arithmetic Sequence Formula

Where:
an = the term that you want to find
a1 = first term in the list of ordered numbers
n = the term position (ex: for 5th term, n = 5 )
d = common difference of any pair of consecutive or adjacent numbers
Using Java programming, solve the following problems:
a. Find the 35 term in the arithmetic sequence 3, 9, 15, 21, …
b. Find the 125 term in the arithmetic sequence 4, −1, −6, −11, …
c. Given two terms in the arithmetic sequence, a5 = −8 and a25 = 72. Find the 100th term
(a100).
d. Write the formula of a sequence with two given terms, a5 = −32 and a18 = 85. Find the 36th
term (a36).

2. Design a Java program that will implement Linked List structure on the following
procedures:
a. Initial car lists are: Lexus → Porsche → Lincoln → Toyota → Mercedes-Benz
b. Add Kia at the end of the list
c. Add BMW at the beginning of the list
d. Add Honda between Porsche and Lincoln
e. Delete Lincoln and replace it with Hyundai
f. Replace the last car with Subaru
g. Find the middle of the list and insert Audi
h. Count the number of cars in the list and display them in order

3. Re-structure your car lists and make it a doubly linked list. Answer the following questions
using your Java program.
a. What is the order of the list when you print them from head to tail?
b. What will be the order of the list when you print them from tail to head?
c. Is it possible to display the list from Hyundai to the tail of the list?
d. Can you arrange the list in alphabetical order?

Author: Mr. Ronnie D. Luy, MIT Page | 24

 Republic of the Philippines
City of Olongapo
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City
www.gordoncollege.edu.ph

VI. REFERENCES
• Fox, C. (2018). Java Data Structures and Algorithms 1 st Ed.
• Miller B. & Ranum D. (2013). Problem Solving with Algorithms and Data Structures Release
3.0
• Goodrich, M. & Tamassia, R. Data Structures and Algorithms in Java 4th Ed.
• Paul Klausen (2018). Java 18: Algorithms and Data Structures: Software Development 1st
Ed.
• Paul Klausen (2018). Java 19: More Algorithms and Data Structures: Software Development
1st Ed.
• Wikipedia
• https://www.geeksforgeeks.org/
• https://www.tutorialspoint.com/
• https://www.chilimath.com/
• https://www.autolist.com/guides/most-reliable-car-brands
• https://codegym.cc/
• https://mathworld.wolfram.com/

Author: Mr. Ronnie D. Luy, MIT Page | 25