Abdelmalek Essaadi University

Java Data Structure

GCyB - I

Pr. Youssef SBAYTRI 2024-2025

I- Introduction

2
 1. Why studying data structure ?

• The study of data structures helps us to understand the basic concepts involved in organizing and
storing data as well as the relationship among the data sets.

• Data structure provides a way to store and organize data in a manner that allows for efficient retrieval
and modification.

• Choosing the right data structure can significantly impact the performance of an application or
algorithm. This enable faster processing and reduced memory consumption (more details in Chapter
IV).

• Data structures are supported by the majority of programming languages, including C, C++, Java,
Python, and others.

• Java provides a rich set of built-in data structures through its libraries (Chapter II). 3
 2. Goals of data structure

• Data structure implements two complementary goals.

Correctness Efficiency

Data structure is designed It should process the data at high

such that it operates speed without utilizing much of
correctly for all kinds of the computer resources such as
input memory space.

4
 3. Classification of data structure

Depending on the organization of the elements, data structures are classified into two categories :
• Primitive data structure: Primitive data structures consist of the numbers and the characters which
are built in programs. These can be manipulated or operated directly by the machine level instructions.
Basic data types such as integer, real, character, and Boolean come under primitive data structures.

• Non-primitive data structure: Non-primitive data structures are those that are derived from primitive
data structures. These data structures cannot be operated or manipulated directly by the machine level
instructions. In java, non-primitive data structure further divided into:
• Linear data structures: Data elements are accessed in a sequential order but it is not compulsory
to store all elements sequentially (Ex: Array, Linked Lists, Stacks and Queues).

• Non-linear data structures: Data elements are not arranged in a sequential order. There is a
hierarchical relationship between individual data items (Ex: Trees and Graphs).
5
3. Classification of data structure

6
 4. Abstract Data Type ?

• Abstract Data Types (ADT) is the combination of data structure with their operations.

• An ADT consists of two parts: Declaration of data and declaration of operations.

 For the primitive data structure (int, float, double), the system provides the implementation of
basic operation such as addition and substruction.
 For non-primitive data structure, operations should be defined. The implementation for these
operations can be done when we want to actually use them. That means, in general, user defined
data structure along with their operations.

7
 2. Abstract Data Type

Properties off ADTs

• The operations of an ADTs are separated from their implementation (The same operation or
functionality can result from different implementations).

• ADTs are language-independent representations of data types (Can be used to specify a new data type
that can then be implemented in various ways using different programming languages).

• In Object-oriented language, classes are language-specific structures that allow implementation of

ADTs.
 A given ADTs can be implemented in different ways using different classes (Ex: Stack, Queue,
LinkedList can be implemented in different ways).
 A given class can in fact be used to represent more than one ADTs (a Java class ArrayList can
be used to represent a Stack, Queue and other ADTs). 8
II- Java Collection Framework

9
 1. Arrays
• Array is a type of data structure that stores data elements of same data types in adjacent locations.

• The array’s length is set when the array is created, and it cannot be changed.

• Array index values must be integers in the range 0...length –1.

public class ArrayMethod1 { public class ArrayMethod2 {

public static void main(String[] args) { public static void main(String[]
int[] arr = new int[6]; args) {
arr[0] = 7; int[] arr ={7,15,103,45,23,31};
arr[1] = 15; }
arr[2] = 103; }
arr[3] = 45;
arr[4] = 23;
arr[5] = 31; Index 0 1 2 3 4 5
}
} Arr 7 15 103 45 23 31
10
 1. Arrays
Arrays can be classified according to their dimension into:

 One-dimensional Array: It has only one row of elements. It is stored in ascending storage location.

 Two-dimensional Array: It consists of multiple rows and columns of data elements. It is also called
as a matrix.

 Multidimensional Array: Multidimensional arrays can be defined as array of arrays.

Multidimensional arrays are not bounded to two indices or two dimensions. They can include as
many indices as required.

11
 1. Arrays
• Example of a 2D array (3x3) of integers

int[][] Array2D = {
{7, 12, 31},
{14, 62, 49},
{10, 55, 75}
};

// Accessing elements of the 2D array

System.out.println("Element at row 1, column 2: " +
Array2D[0][1]);
System.out.println("Element at row 2, column 3: " +
Array2D[1][2]);

12
 1. Arrays
• Example of a 3D array (2x3x4) of integers

int[][][] Array3D = {
{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12} },
{
{13, 14, 15, 16},
{17, 18, 19, 20},
{21, 22, 23, 24}
}
};

// Accessing elements of the 3D array

System.out.println("Element at layer 1, row 2, column 3: " +
Array3D[0][1][2]); System.out.println("Element at layer 2, row 3,
column 4: " + Array3D[1][2][3]); 13
 1. Arrays
• JAVA standard arrays are of fixed length. Sometime we do not know how much memory we need so
we create a bigger size array. There by wasting space.

• If an array is already full and we want to add more values to it than we need to create a new array,
which have sufficient space and then copy the old array to the new array.

• To avoid this manual reallocation and copy we can use ArrayList or Linked Lists to store data.

14
 2. Linked List
• A linked list is a dynamic data structure in which memory is allocated at run time.
• A linked list is considered as a chain of records called nodes. Each node in the list contains two
items: the data and a reference to the next node
• A linked list has the following properties.
 The number of nodes in a list is not fixed and can grow and shrink on demand.
 The last node has a reference to null.
 The entry point into a linked list is called the head (the reference to the first node) of the list.
 If the linked list is empty then the head is a null reference.

15
 2. Linked List
• Types of Linked List:
 Singly Linked List: In a singly linked, each node has some data and a pointer to the next node in the list.

 Doubly Linked List: In a doubly linked list each node contains two pointer: one points to the previous node and the
other points to next node. This allows easy traversal in both forward and backward direction.

 Circular Linked List: In a circular linked list, the last node points to the first node. This implies that the list can be
traversed infinitely in a loop. Circular linked lists can be implemented using either singly linked nodes or doubly linked
nodes.

16
 2. Linked List
import java.util.LinkedList;
LinkedList<Integer> LL = new LinkedList<>(); //Creating a linkedlist
LL.add(10); // Adding elements to the LinkedList
LL.add(20);
System.out.println("LinkedList elements: " + LL); // Displaying the elements of the
LinkedList
System.out.println("the first element: "+LL.getFirst()); //get the first element
System.out.println("the second element: "+LL.get(1)); //get the second element
LL.addFirst(5); // Inserting at the beginning
System.out.println("the first element: "+LL.getFirst());
LL.addLast(50); // Inserting at the end
System.out.println("After insertion: " + LL);
LL.removeFirst(); // Removing the first element
LL.removeLast(); // Removing the last element
System.out.println("After deletion: " + LL);
boolean contains30 = LL.contains(30); // Searching
System.out.println("Does the list contain '30'? " + contains30);
System.out.println("Elements of the LinkedList:"); // Traversal
for (int number : LL) {
System.out.println(number); 17
}
 2. Linked List

Applications:

 Implementing stacks, queues, binary trees and graphs of predefined size.

 Implement dynamic memory management functions of operating system. They can be used to
maintain a list of free memory blocks, allowing the operating system to efficiently allocate memory to
processes as needed.

 Linked lists can represent polynomials efficiently. Each node of the linked list can store a term of the
polynomial (e.g., coefficient and exponent), allowing for operations such as addition, subtraction,
multiplication, and division of polynomials.

18
 2. Linked List
Advantages of Linked List:

 Dynamic Data Structure: Linked List being a dynamic data structure can shrink and grow at the runtime by deallocating or
allocating memory, so there is no need for an initial size in linked list.

 No Memory Wastage: As the size of a linked list can grow or shrink at runtime, so there is no memory wastage. Only the
required memory is allocated.

 Implementation: data structures like queues and stacks can be easily implemented using a Linked List.

 Insertion and Deletion Operation: In a Linked List, insertion and deletion operations are quite easy, as there is no need to
shift every element after insertion or deletion. Only the address present in the pointers needs to be updated.

19
 2. Linked List
Disadvantages of Linked List:

 Slower Access Time: Accessing elements in a linked list requires traversing the list from the beginning (or end) to the
desired position, which can result in slower access times.

 Extra Space for Pointers: Linked lists require additional space for storing pointers/references to the next node, which
increases the overall space complexity of the data structure. This overhead can become significant, especially for large lists
or in scenarios where memory usage is critical.

 Difficulty in Reversal and Traversal: Singly linked lists can be traversed in only one direction, doubly linked lists support
traversal in both directions but require more memory for storing additional pointers.

 Potential for Fragmentation: Linked lists can suffer from memory fragmentation over time, especially in dynamic memory
allocation scenarios. As nodes are dynamically allocated and deallocated, memory fragmentation may occur, leading to
inefficient memory utilization and increased memory management overhead.
20
 3. Stacks
• A stack is a linear data structure in which insertion and deletion of elements are done at only one
end, which is known as the top of the stack.
• Stack is called a last-in, first-out (LIFO) structure because the last element which is added to the
stack is the first element which is deleted from the stack.

21
 3. Stacks
 When an element is inserted in a stack, the concept is called push.

 when an element is removed from the stack, the concept is called pop.

 Trying to pop out an empty stack is called underflow.

 Trying to push an element in a full stack is called overflow.

22
 2. Stacks
import java.util.Stack;
public class StacksDemo
{
public static
void main(String[] args) {
Stack<Integer> ST = new Stack<Integer>();
// Pushing elements onto the stack
ST.push(1);
ST.push(2);
ST.push(3);
System.out.println("Stack: "+ST); ); // Displaying the elements of the Stacks
System.out.println("Stack size : "+ST.size()); //Returns the number of elements stored in
the stack
System.out.println("Stack top : "+ST.peek()); // Peeking the top element of the stack
System.out.println("Stack pop : "+ST.pop());//Remove the top element of the stack
System.out.println("Stack top : "+ST.peek());
System.out.println("Stack isEmpty : "+ST.isEmpty()); //Verify if the stack is emptyt
} 23
}
 3. Stacks
Applications:
 Depth-first search of trees and graphs traversal.

 Managing function calls and recursion in programming.

 Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of the problem-solving
process. The current state is pushed onto the stack, and when the algorithm backtracks, the previous state is popped
from the stack.

 UNDO and REDO operation: Undo/Redo operations: Each time an action is performed, it is pushed onto the stack.
To undo the action, the top element of the stack is popped.

 Browser history: manage the history of visited pages in web browsers. Each time you visit a new page, the URL is
pushed onto the stack, and when you hit the back button, the previous URL is popped from the stack.

24
 3. Stacks
Advantages of stacks:

 Easy implementation: Stack data structure is easy to implement using arrays or linked lists, and its operations are simple to
understand and implement.

 Efficient memory utilization: Stack uses a contiguous block of memory, making it more efficient in memory utilization as
compared to other data structures.

 Fast access time: Stack data structure provides fast access time for adding and removing elements as the elements are
added and removed from the top of the stack.

25
 3. Stacks
Disadvantages of stacks:

 Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed number of elements. If the stack
becomes full, adding new elements may result in stack overflow, leading to the loss of data.

 No random access: Stack data structure does not allow for random access to its elements, and it only allows for adding and
removing elements from the top of the stack. To access an element in the middle of the stack, all the elements above it must
be removed.

 Memory management: Stack data structure uses a contiguous block of memory, which can result in memory fragmentation
if elements are added and removed frequently.

 Not suitable for certain applications: Stack data structure is not suitable for applications that require accessing elements
in the middle of the stack, like searching or sorting algorithms.

 Stack overflow and underflow: Stack data structure can result in stack overflow if too many elements are pushed onto the
26
stack, and it can result in stack underflow if too many elements are popped from the stack.
 4. Queue
• A queue is an ordered list in which the elements in a queue are added at one end called the “rear”
and removed from the other end called the “front”.
• The first element to be inserted is the first one to be deleted. Hence, it is called First in First out
(FIFO).

27
 4. Queue

import java.util.ArrayDeque;
public class QueueDemo
{
public static
void main(String[] args) {
ArrayDeque<Integer> que = new ArrayDeque<Integer>();
que.add(1);
que.add(2);
que.add(3);
System.out.println("Queue "+que);
System.out.println("Queue size : "+que.size());
System.out.println("Queue peek : "+que.peek());
System.out.println("Queue remove : "+que.remove());
System.out.println("Queue isEmpty : "+que.isEmpty());
}
}
28
 4. Queue
Applications:
 Operating System Scheduling: In an operating system, queues are used to schedule processes and
allocate resources.
 Computer Networks: Queues are also used in computer networks to manage network traffic.
 Simulation and Modeling: Queues are commonly used in simulation and modeling to simulate real-
life scenarios. For example, a queue can be used to simulate the waiting time at a supermarket
checkout counter.
 Traffic Management Systems: Queues are used in traffic management systems to manage traffic
flow and avoid congestion.

29
 4. Queue

Advantages of queue:

 Queues are easy to implement and understand.

 They are efficient for storing and accessing elements in a specific order.

 Queues are suitable for applications that require processing elements in a FIFO manner.

Disadvantages of queue:

 Queues have a fixed size, which means they can’t accommodate more elements than their size.

 Adding and removing elements from the middle of the queue is not efficient and requires shifting all the
elements.

30
 5. Tree
• Tree is a hierarchical data structure. The top node of a
tree is called the root of the tree.
• A tree can contain no nodes or root node with zero or
more subtrees.
• Except the root node, every node in a tree has a parent
node, and zero or more child nodes.
• Every edge of the tree is directly or indirectly originated
from the root.
• Every child has only one parent, but one parent can
have many children.
• A leaf node is a node that has no children. It's at the end
of the tree branch.

31
 5. Tree

• The depth of a node is the length of the path from the root to
the node (The depth of B is 2, P-Q-B).

• The height of a node is the length of the path from that node
to the deepest node (The height of R is 3, R-C-M-I).

• The height of a tree is the length of the path from the root to
the deepest node in the tree (The height of this tree is 4).

• The size of a node is the number of descendants it has

including itself (The size of subtree L is 4).

32
 5-1. Binary Tree
A binary tree is a type of tree in which each node has at most two children (0, 1 or 2) which are referred as left child and
right child, binary tree also can divide into three category:
 Strict Binary Tree: A binary tree is called strict binary tree if each node has exactly two children or no children.
 Complete binary tree : A binary tree is called complete binary tree if all leaf nodes are at height h or h-1 (h is
height of the binary tree) and also without any missing number in the sequence.
 Perfect Binary Tree: A binary tree is called perfect binary tree if each node has exactly two children and all
leaf nodes are at the same level.

33
 5-1. Binary Tree

A binary search tree (BST) is a special type of binary tree in which the left child of a node contains a value smaller than
the node's value, and the right child contains a value greater than the node's value. This property enables efficient
searching, insertion, and deletion operations.

34
 5. Tree
• Tree implementation in JAVA Collection
 TreeSet: Implements the NavigableSet interface and import java.util.TreeSet;
public class TreeDemo {
is also based on a red-black tree. It represents a set public static
where elements are sorted in their natural order or void main(String[] args) {
// Create a tree set.
according to a specified comparator. TreeSet<String> ts = new TreeSet<String>();
// Add elements to the tree set.
ts.add("A");
 TreeMap: Implements the NavigableMap interface ts.add("B");
and is based on a red-black tree. It provides a sorted ts.add("C");
System.out.println(ts);
key-value mapping, where keys are sorted in their }
natural order or according to a specified comparator. }

35
 5. Tree
import java.util.TreeMap;
public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<String, Integer> tm = new TreeMap<String, Integer>(); // create a
tree map.
// Put elements into the map
tm.put("Adam", 55);
tm.put("Sara", 77);
tm.put("Ali",89);
tm.put("rim", 75);
System.out.println("Students count: " + tm.size());
for(String key : tm.keySet()){
System.out.println(key + " score marks:" + tm.get(key));
}
System.out.println("Adam score: " + tm.containsKey("Adam"));
tm.remove("sara");
System.out.println(tm.toString());
}
} 36
 5 Tree

Application
The tree is the most useful data structure when we have hierarchical information to store/maintain:
• Implementing the hierarchical structures in computer systems like directory and file system.
• Implementing the navigation structure of a website.
• Decision making in gaming applications.
• Implementation of priority queues for priority-based OS scheduling functions
• Storing data keys for DBMS for indexing
• Spanning trees for routing decisions in computer and communications networks
• Path-finding algorithm to implement in AI, robotics and video games applications

37
 5 Tree

Application
The tree is the most useful data structure when we have hierarchical information to store/maintain:
• Implementing the hierarchical structures in computer systems like directory and file system.
• Implementing the navigation structure of a website.
• Decision making in gaming applications.
• Implementation of priority queues for priority-based OS scheduling functions
• Storing data keys for DBMS for indexing
• Spanning trees for routing decisions in computer and communications networks
• Path-finding algorithm to implement in AI, robotics and video games applications

38
 5 Tree

Advantages
• Hierarchical Structure: Trees represent hierarchical relationships among elements, making them suitable for
organizing and representing hierarchical data, such as file systems, organizational charts, and XML/HTML
documents.
• Efficient Search: Balanced trees (e.g., binary search trees, AVL trees, red-black trees) provide efficient search
operations with time complexity O(log n), where n is the number of elements in the tree. This makes them suitable for
applications requiring fast search operations.
• Ordered Data: Some trees, like binary search trees and B-trees, maintain elements in sorted order. This makes it
easy to retrieve elements in sorted order, which is useful in various applications like searching for nearest neighbors
or iterating through elements in sorted order.
• Dynamic Size: Trees can dynamically grow and shrink in size, allowing for efficient insertion and deletion operations
without requiring a fixed-size structure. 39
 5 Tree

Disadvantages
• Complexity: Some types of trees, especially balanced trees, can be complex to implement and understand.
Managing balance conditions, rotations, and other operations can be challenging.
• Memory Overhead: Trees often have a higher memory overhead compared to simpler data structures like arrays or
linked lists. Each node in a tree typically requires additional memory for storing references to child nodes, leading to
increased memory consumption.
• Traversal Complexity: Traversing trees can sometimes be complex, especially in the case of unbalanced trees. In
worst-case scenarios, traversal operations can degrade to linear time complexity, making them less efficient than in
balanced trees.
• Insertion and Deletion Overhead: While balanced trees offer efficient insertion and deletion operations on average,
in some cases, these operations can involve complex restructuring of the tree, leading to increased overhead.

40
 6. HashMap
• HashMap is a data structure that implements the Map interface provided by the Java Collections
Framework. It stores key-value pairs and allows rapid retrieval of values based on their associated keys.

• The HashMap class provides methods to add, remove, and retrieve elements from the map.
 The put() method is used to add a key-value pair to the map,
 The remove() method is used to remove a key-value pair,
 The get() method is used to retrieve the value associated with a key.

• Hashing is used to provide fast access to the elements in the map. When a key-value pair is added to the
map, the key is hashed to generate an index into an array of buckets. Each bucket contains a linked list
of elements with the same hash code. When a key is used to retrieve a value, its hash code is used to
locate the appropriate bucket, and the linked list is searched for the key.
41
 6. HashMap
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args) {
// Create a new HashMap to store country-domain mappings
HashMap<String, String> countryTLD = new HashMap<>();
// Add country-domain mappings to the HashMap
countryTLD.put("Morocco", ".ma");
countryTLD.put("France", ".fr");
countryTLD.put("United Kingdom", ".co.uk");
// Print the TLD results
System.out.println(countryTLD.toString());
System.out.println(countryTLD.hashCode());
countryTLD.replace("Morocco",".ma",".ac.ma");
System.out.println(countryTLD.toString());
System.out.println(countryTLD.hashCode());
countryTLD.remove("France"); // Remove a country tld mapping
System.out.println("After removing France, size of country TLD: " +
countryTLD.size());
} 42
}
 6. HashMap

Advantages
• Fast Retrieval: HashMap provides constant time O(1) performance for retrieving elements. This means that
regardless of the size of the map, the time to retrieve an element remains the same.
• Efficient Storage: HashMap uses a hash table data structure to store key-value pairs. This provides efficient storage
and retrieval of elements, as the hash function can map the key to the index of the array directly.
• Flexibility: HashMap can store any type of object as a key or value. This allows for a wide range of data to be stored
in the map.
• Dynamic Sizing: HashMap is dynamically sized, which means that the size of the map can be changed as elements
are added or removed. This allows the map to be optimized for memory usage and performance

43
 6. HashMap

Disadvantages
• Unordered: The items in a HashMap are not stored in any particular order. This means that if you need to retrieve the
items in a specific order, you will need to sort the items yourself.
• Performance: In certain situations, the performance of a HashMap may not be optimal. This is because the hash
code function used to generate the keys must distribute the keys evenly to avoid collisions, which can lead to longer
lookup times.
• Thread safety: HashMaps are not thread-safe by default. This means that if multiple threads access the same
HashMap object concurrently, it can lead to data corruption or inconsistency. You can use synchronized or concurrent
HashMaps to overcome this issue, but this comes at the cost of performance.
• Memory usage: HashMaps can use a lot of memory, especially if the hash table needs to be resized. When the load
factor is exceeded, the HashMap needs to allocate a new, larger array and rehash all the elements. This can be a
costly operation in terms of time and memory usage. 44
II- Implementation of main data structures

45
 1. Singly Linked List Implementation

• A Singly-linked list is a collection of nodes linked together in a sequential way where each node of the
singly linked list contains a data field and an address field that contains the reference of the next node.
• The structure of the node in the Singly Linked List is: public class LinkedList{
private Node head;
class Node { private int length;
int data; class Node {
Node next; int data;
Node(int data) { Node next;
this.data = data; Node(int data) {
} this.data = data;
} }
}
public LinkedList(int val){
Node newNode = new
Node(val);
head= newNode;
length=1;
46
}
}
 1. Singly Linked List Implementation

• To create a singly linked list of one node:

public static void main(String[] args) {

LinkedList myLL = new
LinkedList(1);
}

• To display the data of linked list we must verify if the linked list is empty.
public void DisplayLinkedList() {
Node current = head;
System.out.print("head ==> ");
while (current != null) {
System.out.print(current.data + " =>
");
current = current.next;
}
System.out.println("Null"); 47
}
 1. Singly Linked List Implementation

• The various basic operations that we performing on linked lists are:

 Insert element into a linked list.
 Remove element from linked list.
 Search element by index/value.
 Update element in a linked list.

48
 1-1. Insert element in Singly Linked List

• An element can be inserted into a linked list in various orders:

 Insertion of an element at the start of linked list
 Insertion of an element at the end of linked list
 Insertion of an element at the Nth position of linked list (this operation requires get function at
position N).

49
 1-1-1. Insertion at the start of Singly Linked List

• Analysis:
 We need to create a new node with the value passed to the function as argument.
 The next pointer of the new node will point to the head of the linked list or null in case when list is
empty.
 The newly created node will become head of the linked list.
 Time Complexity: O(1).

50
1-1-1. Insertion at the start of Singly Linked List

public void addFirst(int val) {

Node newNode = new Node(val);

newNode.next = head;

head = newNode;
51
}
 1-1-2. Insertion at the end of Singly Linked List
public void addEnd(int val) {
• Analysis:
 New node is created and the value is stored inside it
Node newNode = new Node(val);
and store null value to its next pointer.

 If the list is empty then this new node will become

if (head == null) {
head = newNode;
head of linked list. }

Node current = head;

 If list is not empty then we have to traverse to the while (current.next != null) {
current = current.next;
end of the list and the new node. }
current.next = newNode;

 Time Complexity: O(n). 52

}
 1-1-2. Insertion at the end of Singly Linked List
public void addEnd(int val) {
• Analysis:
 New node is created and the value is stored inside it
Node newNode = new Node(val);
and store null value to its next pointer.

 If the list is empty then this new node will become

if (head == null) {
head = newNode;
head of linked list. }

Node current = head;

 If list is not empty then we have to traverse to the while (current.next != null) {
current = current.next;
end of the list and the new node. }
current.next = newNode;

53
}
 1-1-2. Insertion at the end of Singly Linked List

• What is the inconvenience of the previous method?

 The previous method is un-efficient as each time we want to insert an element we have to
traverse to the end of the linked list which means a time Complexity of O(n).

• What do you propose as solution ?

 So to make it efficient we have to keep track of the last element by adding a tail pointer.
Therefore, if it is required to insert element at the end of linked list, then we will keep track of the
tail reference also. And the time complexity become O(1).

54
 1-1-2. Insertion at the end of Singly Linked List
public void addEnd(int val) { public void addEnd(int val) {

Node newNode = new Node(val); Node newNode = new Node(val);

if (head == null) { if (head == null) {

head = newNode; head = newNode;
} tail = newNode;
}

Node current = head;

while (current.next != null) { else{
current = current.next; tail.next=newNode;
} tail=newNode;
current.next = newNode; }

} 55
}
 1-1-3. Insertion at a position N

• Let first implement Get element by index function

public Node Get(int index){

if(index<0 || index>=length){
return null;
}else{
Node temp = head;
for(int i=0;i<index;i++){
temp=temp.next;
}
return temp;
}
}

56
 1-1-3. Insertion at a position N public boolean insert(int index, int value){
if(index<0 || index>length) return false;

Insert element at position N if(index==0){

addFirst(value);
• If N<0 or N>length Return Null return true;
• If N=0 call addFirst (value) }

• If N=length call addEnd(value) if(index==length){

addEnd(value);
return true;
}

• Otherwise: Node newNode=new Node(value);

 Create a new Node newNode Node temp = get(index-1);
 Get the Node temp of index ’N -1’ newNode.next=temp.next;
temp.next=newNode;
 Point newNode to Node of index N (temp.next) length++;
 Point Node temp to newNode return true;
}
57
 1-2. Remove element from a Singly Linked List

• An element can be removed from linked list in various orders:

 Remove first element
 Remove last element
 Remove an element from Nth position of linked list (this operation require get an element at
position N).

58
1-2-1. Remove first element in a Singly Linked List

public Node removeFirst(){

if(head==null) return null;

Node temp = head;

head = head.next;

temp.next=null;

length--;
return temp;
} 59
1-2-2. Remove last element in a Singly Linked List
public Node removeLast(){
if(head==null) return null;

Node temp = head;

Node pre = head;

while(temp.next!=null){
pre=temp;
temp=temp.next;
}

tail=pre;
tail.next=null;
length--;
return temp;
}

60
 3. Doubly Linked List Implementation
public class DoublyLinkedList {
private class Node { private Node head;
int data; private Node tail;
Node next; private int length;
Node preview; public DoublyLinkedList(int val){
Node(int data) { Node newNode = new Node(val);
this.data = data; head= newNode;
} tail= newNode;
} length=1;
}

61
 3. Doubly Linked List Implementation

public void addFirst(int val) { public void addEnd(int val){

Node newNode = new Node newNode = new Node(val);
Node(val); if(head==null) {
if(length==0) { head=newNode;
head=newNode; tail=newNode;
tail=newNode; }else{
}else{ tail.next=newNode;
newNode.next=head; newNode.preview=tail;
head.preview = newNode; tail=newNode;
head=newNode; }
} length++;
length++; }
}

62
 3. Doubly Linked List Implementation

public Node removeFirst(){ public Node removeLast(){

if(head==null) return null; if(head==null) return null;
Node temp = head; Node temp = tail;
head = head.next; tail=tail.preview;
temp.next=null; tail.next=null;
head.preview=null; temp.preview=null;
length--; length--;
if(length==0) tail=null; if(length==0) {head=null;tail=null;}
return temp; return temp;
} }

63
 3. Doubly Linked List Implementation
public Node get(int index){ public boolean set(int index, int value){
if(index<0 || index>=length){
return null; Node temp = get(index);
}else{ if(temp!=null){
int m=length/2; temp.data=value;
if(index>m) { return true;
Node temp=tail;
for (int i = length-1; i > index; i--) { }
temp = temp.preview; return false;
} }
return temp;
}else {
Node temp=head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}

}
64
}
 3. Doubly Linked List Implementation
public boolean insert(int index,int value){
if(index<0 || index>length) return false; public boolean remove(int index){
if(index==0){
if(index<0 || index>length) return false;
addFirst(value);
return true;
if(index==0){
} removeFirst();
if(index==length){ return true;
addEnd(value); }
return true; if(index==length-1){
} removeLast();
Node newNode=new Node(value); return true;
Node temp = get(index); }
newNode.next=temp; Node temp = get(index);
temp.preview.next=newNode; temp.preview.next=temp.next;
temp.preview=newNode;
temp.next.preview=temp.preview;
newNode.preview=temp.preview;
length++;
length--;
return true; if(length==0) {head=null;tail=null;}
} return true;
}
65
 4. Binary Search Tree Implementation

• In a binary search tree (BST) the left child of a node contains a value smaller than the node's value, and
the right child contains a value greater than the node's value.
• The structure of a node in a BST can be implemented as:

public class BinarySearchTree {

private class Node {
Node root;
int data;
root private int height;
Node left;
}
Node right;
// Constructor for BST =>initial empty tree
Node(int data) {
null this.data = data; public BinarySearchTree(){
} root=null;
} }

66
 4. Binary Search Tree Implementation

• To create a BST of one top node (root is the top node of the tree. ):

public static void main(String[] args) { root

BinarySearchTree myBST = new BinarySearchTree();
}
null

• Once the tree is created, we can start by inserting nodes to it.

67
 4-1. Insert method

• What are the different scenarios?

 Insert a node to an empty tree.
root root
val

null val

Node newNode = new

Node(val);
if (root==null) {
root = newNode;
return true;
} 68
 4-1. Insert method
Insert a node to a tree that contains at least one node.
• what are the main scenarios in this case ?
root
 Insert the node at left.
val
 Insert the node at right.
 Don’t insert the node 40

val<40 val>40

val=40

69
 4-1. Insert method Node temp=root;

while(true ){

 Don’t insert the node if (newNode.data==temp.data) return false;

if(newNode.data<temp.data){
//insert at left
if(temp.left==null){
temp.left=newNode;

 Insert the node at left. }

return true;

temp = temp.left;
}

else{
//insert at right
if(temp.right==null){
temp.right=newNode;
 Insert the node at right. return true;
}
temp = temp.right;

}
70
}
 4-1. Insert method

• Let’s create the following BST

root

40

30 50

25 35 45 60

71
 4-1. Insert method
public static void main(String[] args) {
• Let’s create the following BST
BinarySearchTree myBST = new BinarySearchTree();

myBST.insert(40);

myBST.insert(30);
myBST.insert(50);
myBST.insert(25);
myBST.insert(35);
myBST.insert(45);
myBST.insert(60);

72
 4-1. Insert method

• Ho to reach to a specific node’s data

public static void main(String[] args) {

BinarySearchTree myBST = new BinarySearchTree();

……
……

System.out.println(myBST.root.left.right.data);

System.out.println(myBST.root.right.right.data);

73
 4-2. Search method
• How to verify if a node’s data/value exist in a BST. public boolean contains(int val){
 There are many methodologies for this task, let’s start with Node temp = root;
while (temp!=null){
the iterative approach: if(val<temp.data){
 Create a function contains(int value) temp=temp.left;

 Loop through the BST starting from the root } else if (val>temp.data) {
 If the search value is less then the current node’s temp=temp.right;
}else {
data, then move to the next node on the left. return true;
 Otherwise, move to the next node on the right.
}
}

return false;
}

74
 4-2. Search method
• How to verify if a node’s data/value exist in a BST.

public static void main(String[] args) {

BinarySearchTree myBST = new
BinarySearchTree();
myBST.insert(40);
myBST.insert(30);
myBST.insert(50);
myBST.insert(25);
myBST.insert(35);
myBST.insert(45);
myBST.insert(60);

System.out.println(myBST.contains(40));
System.out.println(myBST.contains(100));
}

75
 5 . Heap Implementation

What is Heap?

• A heap is a complete binary tree, in which the node can have at most two children.

• There are two types of the heap:

 Min Heap: The value of the parent node should be less than or equal to either of its children.
 In a min heap, the node with the smallest value will always be at the root node.

76
 5 . Heap Implementation

What is Heap?
 Max heap: The value of the parent node is greater than or equal to its children.
 In a max heap, the node with maximum value will always be at the root node.

77
 5-1 . Heap Implementation

• A Heap can be implemented using an array. Since the heap is a complete binary tree, there is no wastage of space.
• Let’s start the process of implementing a max heap

78
 5-1 . Heap Implementation

• Use ArrayList to store the data.

• Start storing from index 0.
• For any given node at position i:
 Its Left Child is at [2*i+1] if available.
 Its right child is at [2*i+2] if available.
 Its Parent Node is at [(i-1)/2] if available.

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

public class Heap {

5-1 . Heap Implementation private List<Integer> heap;
public Heap(){
this.heap = new ArrayList<>();
}
public List<Integer> getHeap(){
• Use ArrayList to store the data.
}
return new ArrayList<>(heap);


private int leftChild(int index){
Left Child is at [2*i+1] if available. return 2*index+1;
}

 Right child is at [2*i+2] if available.

private int rightChild(int index){
return 2*index+2;
}


private int parent(int index){
Parent Node is at [(i-1)/2] if available. return (index-1)/2;
}
}

80
 5-1-1 . Insert method

To implement insertion in a heap using an ArrayList in Java, we can

90
follow these steps:

 Add the Element: Add the new element to the end of the
70 60
ArrayList.

 Ensure that the heap property is maintained after insertion.

50 99
 Do a Bubble Up: Comparing the newly inserted
element with its parent and swapping them if necessary
until the heap property is satisfied.

81
 5-1-1 . Insert method

90 90 99
?

70 60 99 60 90 60
?

50 99 50 70 50 70

82
 5-1-1 . Insert method
public void insert(int value){
heap.add(value);
 Add the Element: Add the new element to the
end of the ArrayList. int current = heap.size()-1;
 Ensure that the heap property is
while(current>0 &&
heap.get(current)>heap.get(parent(current))){
maintained after insertion. swap(current,parent(current));
 Do a Bubble Up: Comparing the newly
}
current = parent(current);

inserted element with its parent and

}
swapping them if necessary until the
heap property is satisfied.
private void swap(int index1,int index2){

int temp = heap.get(index1);

heap.set(index1,heap.get(index2));
heap.set(index2,temp);
} 83
5-1-1 . Insert method

public class Heap {

public static void main(String[] args) {
Heap myHeap = new Heap();
myHeap.insert(90);
myHeap.insert(70);
myHeap.insert(60);
myHeap.insert(50);
System.out.println(myHeap.getHeap());
myHeap.insert(99);
System.out.println(myHeap.getHeap());
}
}

84
 5-1-2 . Remove method

To implement remove method in a heap we can follow these steps:

99
 Remove the root element of the heap.

 Replace the root element with the last element of the heap. 90 60
 Ensure that the heap property is maintained after removing
by doing a Bubble down. 50 70 45

85
 5-1-2 . Remove method
?
99 99 45

90 60 90 60
90 60

50 70 45 50 70 45
50 70

 Is the heap property is maintained ?

86
 5-1-2. Remove method

 Remove the root element of the heap.

public Integer remove(){
 Replace the root element with the last if(heap.size()==0){ return null;}
if(heap.size()==1){return
element of the heap.
heap.remove(0); }
 Ensure that the heap property is
int maxValue=heap.get(0);
heap.set(0,heap.remove(heap.size()-
maintained after removing by doing a 1));
BubbleDown(0);
Bubble down.
return maxValue;
}

87
 5-1-2. Remove method

Bubble down process:

• Begin the algorithm with the index of the root node.

• Identify the indices of the left and right children of the current node (leftIndex(i)=2*i+1; rightIndex(i)=2*i+2)

• Compare the value of the current node with the values of its children.
 If the value of the current node is less than the value of the selected child, swap the current node with the selected
child.
 After the swap, update the index of the current node to be the index of the child with which it was swapped.

• Repeat Until Heap Property is Satisfied, where one of the following conditions is met:
 The current node satisfies the heap property.
 The current node becomes a leaf node.

88
 5-1-2. Remove method
private void BubbleDown(int index){
int maxIndex=index;

while(true){
Bubble down function: int leftIndex = leftChild(index);
int rightIndex=rightChild(index);

if(leftIndex<heap.size() &&
heap.get(leftIndex)>heap.get(maxIndex)){
maxIndex=leftIndex;
}

if(rightIndex<heap.size() &&
heap.get(rightIndex)>heap.get(maxIndex)){
maxIndex=rightIndex;
}

if(maxIndex!=index){
swap(index,maxIndex);
index=maxIndex;
}else{
return;
}
89
}
 5-1-1 . Remove method

public static void main(String[] args) {

Heap myHeap = new Heap();
myHeap.insert(90);
myHeap.insert(70);
myHeap.insert(60);
myHeap.insert(50);
System.out.println(myHeap.getHeap());
myHeap.insert(99);
System.out.println(myHeap.getHeap());
myHeap.insert(45);
System.out.println(myHeap.getHeap());

myHeap.remove();
System.out.println(myHeap.getHeap());
}

90
 6 . Hash Table Implementation

What is Hash Table?

• A Hash table is a specific type of data structure, often referred to as an associative array, that is similar to arrays but is
not indexed by integers, but by other forms of data such as strings.

• In array, we store the element whose key is k at a position k of the array. That means, given a key k, we find the element
whose key is k by just looking in the kth position of the array. This is called direct addressing.

• Direct addressing is applicable when we can afford to allocate an array with one position for every possible key. But if
we do not have enough space to allocate a location for each possible key, then we need a mechanism to handle this
case.

91
 6 . Hash Table Implementation

What is Hashing?

• Hashing in the context of hash tables involves using a hash function to convert keys into numerical indices within
an array (or hash table). This process allows for efficient storage and retrieval of key-value pairs.

• A hash function is a mathematical algorithm that takes an input key and generates a numerical value, known as a hash
code or hash value.

• The primary purpose of a hash function in a hash table is to efficiently map keys to indices within the underlying array
structure of the hash table.

92
 6 . Hash Table Implementation

• In the context of hash table, a hash function must be:

 Deterministic: For a given input key, a hash function should always produce the same hash value. This
ensures consistency in mapping keys to indices.
 Uniform Distribution: Ideally, a hash function should distribute hash values evenly across the range of
possible indices in the hash table. This helps minimize collisions and ensures efficient use of the hash table.
 Collision Resistance: While not strictly required, a good hash function should minimize the likelihood of
collisions, where two different keys produce the same hash code.
 Fast Computation: Hash functions should be computationally efficient, allowing for fast computation of hash
codes.

93
 6 . Hash Table Implementation

How Hash function works?

• List of input data

0
 {‘SmartPhone’,4000}
 {‘LapTop’,12000}
Input
Data
1 {‘SmartPhone’,4000}

 {‘Tablet’,3500} 2
 {‘Printer’,2500}
3
 {‘HardDisk’,3000}
 {‘USB’,100} 4
Hash code =1

94
 6 . Hash Table Implementation

What is Collision ?
• In a hash table, a collision occurs when two or more distinct keys hash to the same index or position in the array. This
situation arises because the hash function used to map keys to indices is not perfect or because the array size is
limited compared to the number of possible keys.
• When a collision occurs, it means that there are multiple elements that are supposed to be stored at the same index
in the hash table. This can lead to data loss.

• The main methods to handle collisions when inserting elements into a hash table are:
 Linear Probing: when a collision occurs, the algorithm searches for the next available slot in the hash table by
incrementing the index by a fixed amount (often 1) until an empty slot is found.
 Separate chaining: Instead of storing all elements directly in the hash table's array, each slot in the array
contains a linked list to store multiple elements that hash to the same index.

95
 6 . Hash Table Implementation

Implementation of hash function

• One commonly used approach to create a hash value from a string is the polynomial rolling hash function. Here's a simple
mathematical formula for this hash function:
 Given a string S of length n and a prime number p, the hash value H(S) can be calculated as:

H(S) = σ𝑛−1 𝑖
𝑖=0 𝑆[𝑖] ∗ 𝑝 𝑚𝑜𝑑 𝐿

where:
■ S[i] represents the ASCII value of the i-th character of the string S.
■ p is a prime number chosen to reduce collisions.
■ L is the size of the hash table or the maximum value of the hash code.

96
 6 . Hash Table Implementation

Implementation of hash function

private int hash(String key){

int hash=0;
char[] keyChars = key.toCharArray();
for(int i=0;i<keyChars.length;i++){
int asciiValue=keyChars[i];
hash = (hash+asciiValue*(17^(i+1))) % dataMAp.length;
}
return hash;
}

97
 6 . Hash Table Implementation

Implementation of Hash Table

• To implementation of a hash table using array and separate chaining method requires:
• Creation of an array of fixed-size L.
• The data that will be stored in array is a pair of key and value:
 {String key=“some string”, int value=number}
• The hash function will be used to calculate the hash code (x) of the key:
 H(“some string”)= 𝐱, where 𝐱 ∈ [𝟎, 𝐋].
• Each slot in the array should contains a linked list to store multiple elements that hash to the same index.
• The node could be implemented as a class of three attributes: key of type string, value of type integer, pointer to the
next Node.

98
 6 . Hash Table Implementation
Implementation of Hash Table

public class HashTable { class Node{

private int size=5; String key;
private Node[] dataMAp; int value;
class Node{ Node next;
String key; Node(String k, int
int value;
val){
Node next;
this.key=k;
Node(String k, int val){
this.key=k; this.value=val;
this.value=val; }
} }
}
public HashTable(){
dataMAp = new Node[size];
}
99
}
 6-1. Set method

• The Set function process consisting of the following

steps: public void set(String key,int value){
 Input: key (string), value (integer). int index = hash(key);
Node newNode = new Node(key,
 Calculate the hash of the key to get the index.
value);
 Create a new node with the key and value. if(dataMAp[index]==null){
 If the array is empty, assign the new Node to the dataMAp[index]=newNode;
array.
}else{
Node temp =dataMAp[index];
 Otherwise: while (temp.next!=null){
 traverse through the linked list at at temp=temp.next;
position index until the last node. }
temp.next=newNode;
 Set the next pointer of the last node to the
}
Node. }
100
 6-2. Search method

• The Set function process consisting of the following

steps: public int Search(String k){
 Input: key (string). int index = hash(k);
Node temp =dataMAp[index];
 Calculate the hash of the input key to get the
while (temp!=null){
index. if(temp.key==k) return temp.value;
 Set a Node temp to the head of the linked list at temp=temp.next;
}
position index.
return 0;
 While temp is not null, do the following: }
 If the key of the current node temp is
equal to the input k, return the value of the
current node.
 Move temp to the next node.
101
 6-3. Display method
public void Dispaly(){
• Iterate through each index i in the for(int i=0;i<dataMAp.length;i++){
array. System.out.println(i+":");
• Set temp to the head of the linked list Node temp = dataMAp[i];
while (temp!=null){
at index i.
• While temp is not null: System.out.println("{"+temp.key+"="+temp.value+"}");
 Print the key-value pair. temp=temp.next;
 Move temp to the next node.
}
}

102
 7 . Graph Implementation
Introduction
• In the real world, many problems are represented in
terms of objects and connections between them.
• Graphs can be used to model a wide range of
relationships and structures, including social networks,
computer networks, transportation networks, molecular
structures, and more.
• They provide a powerful framework for analyzing and
solving problems related to connectivity, paths, flows,
and optimisation.
• Graphs can vary in complexity from simple structures
with a few nodes and edges to large, interconnected
networks with millions of nodes and edges.

103
 7 . Graph Implementation
What is a Graph?

• A graph is a data structure that represents a network. It contains a

collection of nodes called vertices, and their connections called
edges.

• An edge can be seen as a path between two nodes.

• Edges can be either directed or undirected.

• If a path is directed then we can move only in one direction.

• In an undirected path we can move in both the directions.

104
 7 . Graph Implementation
What is a Graph?
Undirected graph
• A graph could be also directed (all the edges are directed) or undirected
(all the edges are undirected),

• By default, a graph is considered undirected; however, if there is an

emphasis on directionality, it is referred to as a directed graph.

• When an edge connects two vertices, the vertices are said to be adjacent Directed graph

to each other and the edge is incident on both vertices.

• A graph with no cycles is called a tree. A tree is an acyclic connected

graph.

Acyclic connected graph 105

 7 . Graph Implementation
What is a Graph?

• A weighted graph is a type of graph in which each edge is

assigned a numerical value called a weight. These weights
represent some meaningful quantity associated with the
relationship between the nodes connected by the edge.

• In a networking, the weight of an edge could represent the

physical distance between two network nodes or the latency,
which is the time delay experienced in transmitting data
between the nodes. Lower weights would indicate shorter
distances or lower latencies, which are desirable for efficient
Weighted graph
communication.

106
 7 . Graph Implementation
Graph implementation

• There are several ways to represent graphs, each with its advantages and disadvantages.

• The main ways to represent graphs are:

 Adjacency Matrix: In this method, a matrix (2D array) is used to represent the connections between nodes.
 Adjacency List: In this method, each node maintains a list of its neighboring nodes (adjacent nodes). This can be
implemented using an array of lists, a hash table, or linked lists.

107
 7-1 . Implementation using Adjacency List

• There are several data structures commonly used to

implement a graph with an adjacency list.

• HashMap is on of the data structure that could be used to

implement a graph, where the keys are the vertices and the
values are lists of adjacent vertices.

• This approach provides efficient access to adjacency lists

using hashing, making it suitable for large graphs.

• In this implementation we will study the undirected graph.

108
 7-1 . Implementation using Adjacency List

• Implementing an adjacency list using a HashMap

import java.util.ArrayList;
import java.util.HashMap;
involves several steps:
public class Graph {

private HashMap<String, ArrayList<String>> adjList = new

 Create a HashMap: Initialize a HashMap with HashMap<>();
strings as keys and ArrayList of strings as values.
public boolean addVertex(String vertex) {
if (adjList.get(vertex) == null) {
 Add Vertices: For each vertex in the graph, add adjList.put(vertex, new ArrayList<String>());
return true;
an entry to the HashMap. The key will be the }
string representation of the vertex, and the value return false;
}
will be an empty ArrayList initially.

} 109
 7-1 . Implementation using Adjacency List

 Add Edges: For each edge in the graph,

public class Graph {
add the adjacent vertex to the ArrayList
corresponding to the source vertex in the public boolean addEdge(String vertex1, String vertex2) {
if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {
HashMap.
adjList.get(vertex1).add(vertex2);
 Example: adjList.get(vertex2).add(vertex1);
return true;
}
myGraph.addVertex("A");
return false;
myGraph.addVertex("B");
}
myGraph.addVertex("C");
myGraph.addVertex("E");
}
myGraph.addEdge("A", "B");
myGraph.addEdge("A", "C");
myGraph.addEdge("A", "E");
110
 7-1 . Implementation using Adjacency List

 Traversing: With the adjacency list

public class Graph {
constructed, we can easily traverse the
public void printGraph() {
graph and access adjacent vertices for any for (String key : adjList.keySet()) {
System.out.println(key+" ==> "+adjList.get(key));
given vertex. Simply look up the ArrayList
}
corresponding to the vertex in the HashMap. }

 Example:
}

111
 7-1 . Implementation using Adjacency List

To Remove a Vertex we follow the below steps:

 Check if the vertex to be removed (vertex)

public boolean removeVertex(String vertex) {

exists in adjacency list. if (adjList.get(vertex) == null) return false;

 Iterate through the list of adjacent vertices

(otherVertex) for the vertex to be removed.
for (String otherVertex :
This ensures that all edges incident to the adjList.get(vertex)) {
adjList.get(otherVertex).remove(vertex);
vertex to be removed are properly removed
}
from the graph.

 Remove the vertex itself from the adjacency adjList.remove(vertex);

list.
return true;
}
112
 7-1 . Implementation using Adjacency List
public boolean removeEdge(String vertex1,
To Remove an Edge we follow the same String vertex2) {
process as adding an edge.
if (adjList.get(vertex1) != null &&
 Check if both vertex1 and vertex2 exist adjList.get(vertex2) != null) {

in the adjacency list.

adjList.get(vertex1).remove(vertex2);
 If both vertices exist, proceed to adjList.get(vertex2).remove(vertex1);
remove the edge between them.
Remove vertex2 from the adjacency list
of vertex1 and remove vertex1 from the return true;
}
adjacency list of vertex2. return false;
 This step effectively removes the edge
}

between the two vertices.

113
 7-2 . Implementation using Adjacency Matrix

• To represent graphs in adjacency matrix, we need the

number of vertices, the number of edges and also their
interconnections.

• In this method, we use a matrix with size VxV. The values

of matrix are boolean.

• For A Matrix AdjMatrix, the value of AdjMatrix[u, v] is set to

1 if there is an edge from vertex u to vertex v and 0
otherwise.

• For an undirected graph, the adjacency matrix is symmetric.

114
 7-2 . Implementation using Adjacency Matrix

• For a directed graph, the adjacency matrix need not be symmetric.

• In weighted graph, the non-zero values in the adjacency matrix are replaced by the actual weight
of the edge.

115
 7-3 . Implementation using Adjacency Matrix

Implementation of weighted graph

 Define a 2D array to store the adjacency matrix.
 Define an integer to store the number of vertices.
 Define an array to store the vertex labels.
 Initialize the 2D array.
 Add Vertex:
 Add Edge:

 Display the Graph

116
 7-2 . Implementation using Adjacency Matrix

Implementation of weighted graph public class WeightedGraph {

private int[][] adjacencyMatrix;
 Define a 2D array to store the adjacency matrix. private int numVertices;
 Define an integer to store the number of vertices. private String[] vertices;

 Define an array to store the vertex labels. // Class Constructor

public WeightedGraph(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new
int[numVertices][numVertices];
 Initialize the 2D array with the size based on the vertices = new String[numVertices];
for (int i = 0; i < numVertices; i++) {
number of vertices. for (int j = 0; j < numVertices; j++) {
adjacencyMatrix[i][j] = 0;
}
}
}
}
117
 7-2 . Implementation using Adjacency Matrix

Implementation of weighted graph public void addVertex(int index, String label) {

if (index >= 0 && index < numVertices) {
 Add Vertex: vertices[index] = label;
 Create a method to add a label to a specific } else {
index in the vertex label array. System.out.println("Invalid vertex index.");
 Check if the index is within valid bounds before }
assigning the label. }
 Add Edge:
 Create a method to add a directed edge with a public void addEdge(int source, int destination, int weight) {
specific weight between two vertices. if (source >= 0 && source < numVertices && destination >= 0
 Check if the vertex indices are valid before && destination < numVertices) {
assigning the weight in the 2D array adjacencyMatrix[source][destination] = weight;
} else {
System.out.println("Invalid vertex number.");
}
}

118
 7-2 . Implementation using Adjacency Matrix

Implementation of weighted graph public void DisplayGraph() {

System.out.print(" ");
 Iterates through the adjacency matrix and prints vertex for (int i = 0; i < numVertices; i++) {
labels and edge weights. System.out.print(vertices[i] + " ");
}
System.out.println();
 Displays "0" for entries in the matrix that signify no
edges. for (int i = 0; i < numVertices; i++) {
System.out.print(vertices[i] + " ");
for (int j = 0; j < numVertices; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}

119
 7-3 . Implementation using Adjacency Matrix
public static void main(String[] args) {
WeightedGraph graph = new WeightedGraph(5);
Implementation of weighted graph
// Add vertices
graph.addVertex(0, "A");
graph.addVertex(1, "B");
graph.addVertex(2, "C");
graph.addVertex(3, "D");
graph.addVertex(4, "E");
// Add edges with weights
graph.addEdge(0, 1, 4); // A  B
graph.addEdge(0, 2, 3); // A  C
graph.addEdge(2, 3, 2); // C  D
graph.addEdge(3, 1, 1); // D  B
graph.addEdge(3, 4, 1); // D  E
graph.addEdge(4, 0, 1); // E  A

System.out.println("Adjacency Matrix:");
graph.printGraph();
}
120