DATA STRUCTURES
AND ALGORITHM
Prepared by: Maxil S. Urocay MSCS ongoing
Prepared by: Maxil S. Urocay MSCS ongoing
ARRAYS
AND
LINKEDLIST
Prepared by: Maxil S. Urocay MSCS ongoing
ARRAY
Prepared by: Maxil S. Urocay MSCS ongoing
Array
- is a data structure that holds a fixed-size
sequence of elements of the same type.
- is a type of linear data structure that is defined as
a collection of elements with same or different data
types and stores them in contiguous and adjacent
memory locations.
- each item in an array is indexed starting with 0
and each element in an array is accessed through its
index.
Prepared by: Maxil S. Urocay MSCS ongoing
Array
MEMORY 125 126 127 128 129 130 131
ADDRESS
ARRAY 0 1 2 3 4 5 6
INDEX
ELEMENT / 24 56 12 63 46 21 5
ARRAY
VALUES
Memory address – the starting address of free memory
available.
Array index – key value to label the elements in the
array.
Element / Array values – the items stored in an array.
Prepared by: Maxil S. Urocay MSCS ongoing
Types of Array
*One-dimensional arrays - which is a one dimensional
array as a row, where elements are stored in a single row
or stored one after another.
*Multidimensional arrays - which stores a multiple rows
of elements and do have two types which includes two-
dimensional array and three-dimensional array.
*Two-dimensional arrays – can be considered as an
array of arrays or as a matrix consisting of rows and
columns.
*Three-dimensional arrays – contains three
dimensions.
Prepared by: Maxil S. Urocay MSCS ongoing
How to Initialize an array?
int[] num={1, 2, 3, 4, 5};
String [] names = {“Ace”, ”Boy”,
”Charlie”};
Datatype [] arrayname = element;
Prepared by: Maxil S. Urocay MSCS ongoing
ARRAY OPERATIONS
Prepared by: Maxil S. Urocay MSCS ongoing
TRAVERSAL
- print all the array elements one by one.
int[] num = {1, 2, 3, 4, 5};
for (int i= 0; i < [Link]; i++){
[Link](num[i]);
Prepared by: Maxil S. Urocay MSCS ongoing
INSERTION
- Adds an element at the given index
We are adding one or more elements to
the array. It can be done at the
beginning, at the end or at any given
index of an array.
Prepared by: Maxil S. Urocay MSCS ongoing
DELETION
- deletes an element at the given index.
*You can also do deletion in different
ways at the beginning, at the end, and at
any index.
Prepared by: Maxil S. Urocay MSCS ongoing
SEARCHING
- searches an element using the given index.
*There are two ways we can search in an
array (Linear search & Binary Search).
Linear search – sequential search algorithm
that start at one end and goes through each
element of a list until the desired element is
found.
Binary search – is a searching algorithm used
in a sorted array by repeatedly dividing the
Prepared by: Maxil S. Urocay MSCS ongoing
SORTING
- the process which arrange elements in
a user-defined order.
- it could be in ascending order or
descending order.
Prepared by: Maxil S. Urocay MSCS ongoing
UPDATE
- updates an element at the given
index.
Prepared by: Maxil S. Urocay MSCS ongoing
LINKEDLIST
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST
- is a linear data structure which is non-
contiguous that forms a series of
connected nodes, where each node
stores the data and the address of the
next node and connected by pointers.
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST
HEAD NEXT POINTER
NULL
DATA
Data – the value or information stored in node.
Reference / Next pointer – a pointer or reference
to the next node in the sequence. It stores the
memory address (reference) of the next node in
the sequence. Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST
Head – linked list is accessed through the
head node which points to the first node
in the list.
Null – the last node in the list points to
null indicating the end of the list and also
known as the tail node.
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST
HEAD
A B C NULL
*Each node has a reference to the next
node.
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST TYPES
HEAD
A B C NULL
Singly Linked List – the nodes only point
to the address of the next node in the
list.
- each node has data and address that
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST TYPES
HEAD
A B C NULL
NULL
Doubly Linked List – the nodes point to the
address of both previous and next nodes.
- contain a three buckets in one node, one bucket
holds the data and the other buckets holds the
addresses of the previous and next nodes in the
Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST TYPES
HEAD
A B C NULL
NULL
Doubly Linked List – the navigation is possible in both ways,
either forward and backward.
LINK – each link of a linked list can store a data called element.
NEXT – each link of a linked list contains a link to the next link
called next.
PREV – each link of a linked list contains a link to the previous
link called Prev. Prepared by: Maxil S. Urocay MSCS ongoing
LINKED LIST TYPES
HEAD
A B C
Circular Linked List – the last node in the list will
point to the first node in the list.
*Since the last node and the first node of the
circular linked list are connected, the traversal in
this linked list will go on forever until it is broken.
Prepared by: Maxil S. Urocay MSCS ongoing
LINKEDLIST
OPERATIONS
Prepared by: Maxil S. Urocay MSCS ongoing
TRAVERSAL
HEAD
1 20 30 NULL
0
To traverse / display all nodes one by
one.
Prepared by: Maxil S. Urocay MSCS ongoing
INSERTION
HEAD
1 20 30 NULL
0
To insert new nodes at specific positions
(beginning, end or any position within the
list)
Prepared by: Maxil S. Urocay MSCS ongoing
INSERTION
1 START
2 Create a node to store the data
3 Check if the list is empty
4 If the list is empty, add the data to the node and
assign the head pointer to it.
5 If the list is not empty, add the data to a node
and link to the current head. Assign the head to
the newly added node.
6 END
Prepared by: Maxil S. Urocay MSCS ongoing
DELETION
HEAD
1 20 30 NULL
0
To delete nodes from a specific positions.
(beginning, end or from a specific position).
Prepared by: Maxil S. Urocay MSCS ongoing
DELETION
1 START
2 Assign the head pointer to the
next node in the list
3 END
Prepared by: Maxil S. Urocay MSCS ongoing
SEARCHING
HEAD
1 20 30 NULL
0
To search for an element from the linked list.
*comparing every element in the list
with the key element.
*Searching for an element in the list is
using a key element.
Prepared by: Maxil S. Urocay MSCS ongoing
SEARCHING
1 START
2 If the list is not empty, iteratively check if
the list contains the key element.
3 If the key element is not present in the list,
unsuccessful search.
4 END
Prepared by: Maxil S. Urocay MSCS ongoing
REVERSE
HEAD
1 20 30 NULL
0
We need to make the last node to be pointed by
the head node and reverse the whole linked list.
Prepared by: Maxil S. Urocay MSCS ongoing
REVERSE
1 START
2 We use three pointers to perform the reversing:
Prev, Next, Head.
3 Point the current node to head and assign its
next value to the prev node.
4 Iteratively repeat the step 3 for all the nodes in
the list.
4 Assign head to the prev node
5 END
Prepared by: Maxil S. Urocay MSCS ongoing
[Link];
-to specifically import the
LinkedList class from the [Link]
package.
Prepared by: Maxil S. Urocay MSCS ongoing
INITIALIZING LINKEDLIST
LinkedList<String> list = new
LinkedList<>();
-creating an empty linked list that holds
String elements.
Prepared by: Maxil S. Urocay MSCS ongoing
BASIC STRUCTURE OF THE
NODE
class Node {
int data;
Node next;
Node(int data) {
[Link] = data;
[Link] = null;
}
}
Prepared by: Maxil S. Urocay MSCS ongoing
BASIC STRUCTURE OF THE
NODE
class Node {
int data;
//class that represents the node
// declares the instance variable “data” with int datatype
Node next; //declares the instance variable ”next” which is the
reference to the next node in the list
Node(int data) { //constructor for the node class
[Link] = data; //initializing the instance variable data with
the value ”data” which signifies the current
[Link] = null; //initializes the next instance to null
}
}
Prepared by: Maxil S. Urocay MSCS ongoing
TRAVERSAL
[Link]();
[Link](list);
- to simply print the list.
Prepared by: Maxil S. Urocay MSCS ongoing
ADDING/INSERTING ELEMENTS
[Link](”Apple”);
[Link](10);
- to add elements to the
beginning of the list.
Prepared by: Maxil S. Urocay MSCS ongoing
ADDING/INSERTING ELEMENTS
[Link](”Apple”);
[Link](”Apple”);
[Link](30);
- to add elements at the end of
the list.
Prepared by: Maxil S. Urocay MSCS ongoing
ADDING/INSERTING ELEMENTS
[Link](2, 3);
[Link](0, 25);
[Link](0, 25);
- to add elements at the specific
position.
Prepared by: Maxil S. Urocay MSCS ongoing
DELETING ELEMENTS
[Link](4);
[Link](”Max”);
- to simply delete specific value
in the list.
Prepared by: Maxil S. Urocay MSCS ongoing
DELETING ELEMENTS
[Link]();
[Link]();
[Link]();
- to simply delete the head node.
Prepared by: Maxil S. Urocay MSCS ongoing
DELETING ELEMENTS
[Link]();
[Link]();
[Link]();
- to simply delete the last node.
Prepared by: Maxil S. Urocay MSCS ongoing
SEARCHING ELEMENTS
[Link](2);
-to simply search the list with the
value 2.
Prepared by: Maxil S. Urocay MSCS ongoing
REVERSE ELEMENTS
[Link]();
-to simply reverse the value of
the list.
Prepared by: Maxil S. Urocay MSCS ongoing
THANK YOU
PRODUCT
OFFERS
Prepared by: Maxil S. Urocay MSCS ongoing