Data Structures In Java

Notes By Priyanka Ghosh

DATA STRUCTURES
Data Structure is a way to store and organize data so that it can be used efficiently. There are two
types of data structures: - Linear and Non – linear data structures.
 Linear Data Structures: - It refers to the sequential allocation of the data. Stack, Queue and
Linked List are those linear data structures.
 Non-Linear Data Structures: - It refers to the non-sequential allocation of the data. Binary
tree is that non-linear data structures.

 STACK DATA STRUCTURE

Stack is a linear data structure which follows a particular order in which the operations are
performed. A stack is an array like structure, where stack items can only be added or deleted
from the end of the stack. This manner is known as LIFO (i.e. Last In First Out), means element
last inserted would be the first one to be deleted.

The basic operation performed on the stack are: -

 Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.
 Pop: Removes an item from the stack. The items are popped in the reversed order in which
they are pushed. If the stack is empty, then it is said to be an Underflow condition.

Important terms of Stack: -

 Stack Top: It represents the top most position of data in the stack.
 Overflow State: If the stack is full and does not contain enough space to accept the given
item, the stack is then considered to be in an overflow state.
 Underflow State: It means no items are present in stack to be removed i.e. the stack is
empty.

/* Implementation of stack using array */

class Stack
{
int top;
int item[];
Stack(int size)
{
top = -1;
item = new int[size];
}
//Function to insert elements in the stack
void pushItem(int data)
{
if (top == item.length - 1)
{
System.out.println("Stack is Full");
}
else
{
item[++top] = data;
}
}
//Function to delete elements from the stack
int popItem()
{

Notes By Priyanka Ghosh 1|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
//System.out.println("Pop Item : " + item[top]);
return item[top--];
}
}

void display()
{
System.out.println("The items in stack");
for ( int i = top ; i>=0; i--)
{
System.out.println(item[i]);
}
}
}
import java.io.*;
class StackExample
{
public static void main(String[] args) throws IOException
{
Stack stk = new Stack(5);
boolean yes=true;
int ch;
BufferedReader is = new BufferedReader(new InputStreamReader(System.in));

do
{
System.out.println("1).Push\n2).Pop\n3).Exit\n\nEnter Choice");
ch = Integer.parseInt(is.readLine());

switch(ch)
{
case 1: System.out.println("Enter Push Item: ");
stk.pushItem(Integer.parseInt(is.readLine()));
stk.display();
break;
case 2: stk.popItem();
stk.display();
break;
case 3: yes = false;
break;
default: System.out.println("Invalid Choice");
}
}
while(yes==true);
}
}

Notes By Priyanka Ghosh 2|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

 Applications of the Stack

Stack are used whenever LIFO scheme need to be implemented.
Such as: -
 Infix to prefix conversion
 Infix to postfix conversion
 Solving maze problem, etc.

 QUEUE DATA STRUCTURE

A Queue is a linear structure which follows a particular order in which the operations are
performed. Unlike stacks, a queue is open at both its ends. One end is always used to insert data
(enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out
methodology, i.e., the data item stored first will be accessed first. A good example of a queue is
any queue of consumers for a resource where the consumer that came first is served first.

The basic operation performed on the queue are:

 Enqueue (Insert): Adds an item to the queue. If the queue is full, then it is said to be an
Overflow condition.
 Dequeue (Delete): Removes an item from the queue. The items are popped in the same order
in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Important terms of Queue: -
 Front: It represents the front most position of data in the Queue.
 Rear: It represents the rear most position of data in the Queue.
 Overflow State: If the Queue is full and does not contain enough space to accept the given
item, the Queue is then considered to be in an overflow state.
 Underflow State: It means no items are present in Queue to be removed i.e. the Queue is
empty.

/* Implementation of Queue using array */

class Queue
{
int Q[];
int size,rear,front;
Queue(int n)
{
size=n;
Q=new int[size];
rear=front=-1;
}
void insert(int v)
{
if(rear == size-1)
{
System.out.println("\nQueue Overflow\n");
}
else if(front==-1)
{

Notes By Priyanka Ghosh 3|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

front = 0;
Q[++rear]=v;
}
else
{
Q[++rear]=v;
}
}
int delete()
{
int del=0;
if(front==-1 && rear ==-1)
{
System.out.println("\nQueue Underflow\n");
}
else if(front == rear)
{
del = Q[front];
front = -1;
rear = -1;
}
else
{
del= Q[front];
front++;
}
return(del);
}
void show()
{
System.out.println("\nQueue Values:-");
if(front!=-1)
{
for(int i=rear;i>=front;i--)
{
System.out.println(Q[i]);
}
}
}
}
import java.util.*;
class queueOperation
{
public static void main()
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the stack");
int n =sc.nextInt();
Queue q= new Queue(n);
do{
System.out.println("\nOperations on stack");
System.out.println("1.Insert value in Queue");
System.out.println("2.Delete value from Queue");
System.out.println("3.Display values of Queue");

Notes By Priyanka Ghosh 4|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

System.out.println("4.Exit");
System.out.println("Enter the your choice");
int ch = sc.nextInt();
switch(ch)
{
case 1:
System.out.println("Enter the value");
int i=sc.nextInt();
q.insert(i);
q.show();
break;
case 2:
int d=q.delete();
System.out.println("The deleted value is " + d);
q.show();
break;
case 3:
q.show();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong choice");
}
} while(true);
}
}
 Applications of the Queue
QUEUE is used when things don’t have to be processed immediately, but have to be
processed in First In First Out order. This property of Queue makes it also useful in
following kind of scenarios.
a. When a resource is shared among multiple consumers. Examples include CPU
scheduling, Disk Scheduling.
b. When data is transferred asynchronously (data not necessarily received at same rate as
sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

 CIRCULAR QUEUE

A Circular Queue is a linear data structure in which the operations are performed based on FIFO
(First In First Out) principle and the last position is connected back to the first position to make a
circle. It is also known as ring buffer, circle buffer.
 Characteristics of a Circular Queue
 First In First Out (FIFO) principle.
 The last position connects back to the first position (circular).
 Uses two pointers:
 front – points to the front element.
 rear – points to the last element.

Notes By Priyanka Ghosh 5|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

Circular Queue Operations

The formula to increment the front and rear pointers to make them go round and round over and again
will be, front = (front + 1) % size or rear = (rear + 1) % size.
/* Implementation of Circular Queue using array */
class CQueue
{
int a[];
int front, rear;
int size;
CQueue(int s)
{
size = s;
a = new int[size];
front = rear = -1;
}

boolean empty()
{
if(front == -1)
return true;
else
return false;
}

void destroy()
{

Notes By Priyanka Ghosh 6|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

front = rear=-1;
}

void insert(int x)
{
int p;
p = (rear+1)% size;
if(p == front)
System.out.println("Queue Overflow ");
else
{
rear = p;
a[rear] = x;
if(front == -1)
front = 0;
}
}

int delete()
{
int x = a[front];
if(front == rear)
front = rear = -1;
else
front =(front+1)% a.length;
return x;
}

void display()
{
if(front == -1)
System.out.println("Queue underflow");
else
{
System.out.println("Elements of Queue are");
int i = front;
while(i != rear)
{
System.out.println(a[i]);
i = (i+1)% a.length;
}
System.out.println(a[i]);
}
}
}// End of Queue class
import java.util.Scanner;
class CircularQueue
{
public static void main(String args[])
{
Scanner sc =new Scanner(System.in);
System.out.print("Enter the size of the queue : ");
int size = sc.nextInt();
CQueue q = new CQueue(size);

Notes By Priyanka Ghosh 7|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

int ch;

do
{
System.out.println("Menu\n1.Insert\n2.Delete\n3.display\n4.destroy\n5.exit\n");
System.out.println("Enter choice :");

ch=sc.nextInt();
switch(ch)
{
case 1:
System.out.println("Enter data to insert");
int x=sc.nextInt();
q.insert(x);
break;
case 2:
if(q.empty())
System.out.println("Queue underflow");
else
{
int z =q.delete();
System.out.println("data deleted =" + z );
}
break;
case 3:
q.display();
break;
case 4:
q.destroy();
break;
case 5:
System.exit(0);
default :
System.out.println("Wrong Choice");
}
}while(true);
}//end main
}//end CircularQueue

 Applications of the Circular Queue

 CPU Scheduling (Round-Robin Algorithm)
 Multimedia Buffers (Audio/Video Streaming)
 Printer Queue Management
 Memory Management / Circular Buffers
 Network Data Packet Management
 Undo Operations in Applications
 Traffic Systems / Call Centers

Notes By Priyanka Ghosh 8|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

 DEQUE
The Deque is a double-ended queue. It helps in adding and removing data elements from a data
structure from either front or rear. It can be used either as a FIFO or a LIFO. Examples of FIFO
and LIFO are Queue and Stack respectively.

 Operations On Deque:
Mainly the following four basic operations are performed on queue:
 insertFront(): Adds an item at the front of Deque.
 insertRear(): Adds an item at the rear of Deque.
 deleteFront(): Deletes an item from front of Deque.
 deleteRear(): Deletes an item from rear of Deque.

/* Implementation of Circular Queue using array */

import java.util.*;
class Deque
{
int dq[];
int size,f,r;
Deque(int s)
{
size = s;
dq = new int[size];
f=-1;
r=-1;
}
void pushAtRear(int n)
{
if(r==size-1)
System.out.println("Deque is overflow at rear end!");
else
{
if(f==-1 && r==-1)
f=r=0;
else
r=r+1;
dq[r]=n;
}
}
void pushAtFront(int n)
{
if(f==0)
System.out.println("Deque is overflow at front end!");
else
{
if(f==-1&&r==-1)
f=r=0;
else

Notes By Priyanka Ghosh 9|P a ge

Data Structures In Java
Notes By Priyanka Ghosh

f=f-1;
dq[f]=n;
}
}
void popFront()
{
int d;
if(f==-1)
System.out.println("Deque is empty");
else
{
d=dq[f];
System.out.println(d+"is popped");
if(f==r)
f=r=-1;
else
f=f+1;
}
}
void popRear()
{
int d;
if(f==-1)
System.out.println("DQ is empty");
else
{
d=dq[r];
System.out.println(d+"is popped");
if(f==r)
f=r=-1;
else
r=r-1;
}
}
void display()
{
System.out.println("The Deque is:");
for(int i=f;i<=r;i++)
System.out.println(dq[i]);
}
public static void main()
{
Scanner in=new Scanner(System.in);
System.out.println("Enter capacity");
Deque d=new Deque(in.nextInt());
int c;
do
{
System.out.println("MENU\n1)Insert at front\n2)Insert at rear\n3)Delete at front\n4)Delete at
rear\n5)Display\n6)Exit");
System.out.println("Enter your choice:");
c=in.nextInt();
switch(c)
{

Notes By Priyanka Ghosh 10 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

case 1:
System.out.println("Enter item:");
d.pushAtFront(in.nextInt());
break;
case 2:
System.out.println("Enter item:");
d.pushAtRear(in.nextInt());
break;
case 3:
d.popFront();
break;
case 4:
d.popRear();
break;
case 5:
d.display();
break;
case 6:
System.exit(0);
default:
System.out.println(" Wrong Choice");
}
}
while(true);
}
}
 Applications of Deque
 Undo/Redo Functionality
 Job Scheduling in OS (Multi-level Queue)
 Cache Implementation (LRU Cache)

 SINGLY LINKED LIST

The linked list is a linear data structure that contains a sequence of elements such that each element
links to its next element in the sequence. Each element in a linked list is called "Node". A node
contains two fields i.e. data stored at that particular address and the pointer which contains the
address of the next node in the memory. The last node of the list contains pointer to the null.

 Features of Linked List

 The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
 List size is limited to the memory size and doesn't need to be declared in advance.
 Empty node cannot be present in the linked list.
 We can store values of primitive types or objects in the singly linked list.

Notes By Priyanka Ghosh 11 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

 Why Linked List over array?

Arrays can be used to store linear data of similar types, but arrays have the following
limitations.
 The size of array must be known in advance before using it in the program.
 Increasing size of the array is a time taking process. It is almost impossible to expand the
size of the array at run time.
 All the elements in the array need to be contiguously stored in the memory. Inserting any
element in the array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations of an array. Using
linked list is useful because,
 It allocates the memory dynamically. All the nodes of linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
 Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available memory
space.
 Advantages Over Arrays: -
 Dynamic size
 Ease of insertion/deletion

 Drawbacks: -
 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.
 Extra memory space for a pointer is required with each element of the list.
 Not cache friendly. Since array elements are contiguous locations, there is locality of
reference which is not there in case of linked lists.

 Operations on Single Linked List: -

The following operations are performed on a Single Linked List

 Insertion
 Insert at beginning

Notes By Priyanka Ghosh 12 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

 Insert at end

 Insert at position

 Deletion
 Delete at position

 Display
 Count of node

/*Implementation of Singly linked list */

import java.util.Scanner;
// Class Node
class Node
{
int data;
Node Link;

Notes By Priyanka Ghosh 13 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

// Default Constructor
public Node()
{
Link = null;
data = 0;
}
// Parameterized Constructor
public Node(int d,Node n)
{
data = d;
Link = n;
}
}

// Class linkedList
class linkedList
{
Node start;
Node end ;
public int size ;

// Constructor
public linkedList()
{
start = null;
end = null;
size = 0;
}
// Function to insert an element at begining
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.Link=start;
start = nptr;
}
}
// Function to insert an element at end
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;

Notes By Priyanka Ghosh 14 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

}
else
{
end.Link = nptr;
end = nptr;
}
}
// Function to insert an element at position
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.Link ;
ptr.Link = nptr;
nptr.Link = tmp;
break;
}
ptr = ptr.Link;
}
size++ ;
}
//Function to delete an element at position
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.Link;
size--;
}
else if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.Link;
}
end = t;
end.Link = null;
size --;
}
else
{
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)

Notes By Priyanka Ghosh 15 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

{
Node tmp = ptr.Link;
tmp = tmp.Link;
ptr.Link = tmp;
break;
}
ptr = ptr.Link;
}
}
size-- ;
}
// Function to display elements
public void display()
{
System.out.print("\nSingly Linked List = ");
if (size == 0)
{
System.out.println("empty\n");
}
else if (start.Link == null)
{
System.out.println(start.data);
}
else
{
Node ptr = start;
System.out.print(start.data + "->");
ptr = start.Link;
while (ptr.Link != null)
{
System.out.print(ptr.data + "->");
ptr = ptr.Link;
}
System.out.print(ptr.data + "\n");
}
}

public void nodeCount()

{
Node ptr = start;
int count=0;
while(ptr!=null)
{
count = count +1 ;
ptr = ptr.Link;
}
System.out.println("No.of node present"+ count);
}
}

/* Class SinglyLinkedList */
public class SinglyLinkedList
{
public static void main(String[] args)

Notes By Priyanka Ghosh 16 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

{
Scanner scan = new Scanner(System.in);
//Creating object of class linkedList
linkedList list = new linkedList();
System.out.println("Singly Linked List Test\n");
char ch;
// Perform list operations
do
{
System.out.println("\nSingly Linked List Operations\n");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. count");

int choice = scan.nextInt();

switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.size )
System.out.println("Invalid position\n");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.size )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 5:
list.nodeCount();
System.out.println("No.of node present"+ list.size);
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
// Display List

Notes By Priyanka Ghosh 17 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
 Application of Singly Linked List
 Dynamic Memory Allocation
 Stacks and Queues Implementation
 Symbol Table or Hash Table Collision Resolution
 Polynomial Arithmetic
 Sparse Matrices Representation

 BINARY TREE

A binary tree is a hierarchical data structure in which each node has at most two children
generally referred as left child and right child.

Binary Tree: Common Terminologies

 Root: Topmost node in a tree. From the above figure, A is the root node of the tree.
 Parent: Every node (excluding a root) in a tree is connected by a directed edge from
exactly one other node. This node is called a parent. From the above figure, B, C, E
and G are parent node of the tree.
 Child: A node directly connected to another node when moving away from the root.
 Subtree: Any part of the tree which follows the property of the tree is known as
Subtree of the tree.
 Leaf/External node: Node with no children. From the above figure, D, H, I, F and J
are leaf node of the tree.
 Internal node: Node with atleast one children. From the above figure, B, C, E and G
are internal node of the tree.

Notes By Priyanka Ghosh 18 | P a g e

Data Structures In Java
Notes By Priyanka Ghosh

 Sibling: A node is said to be sibling of another node only if both the node have same
parents. From the above figure, B and C, D and E, F and G, H and I are siblings of
the tree.
 Depth of a node: Number of edges from root to the node. From the above figure, the
depth of E is 2.
 Height of a node: Number of edges from the node to the deepest leaf. Height of the
tree is the height of the root. From the above, the Height of the tree is 3 and Height of
node E is 1.
 Level: The level of a node is defined by 1 + the number of connections between the
node and the root i.e. level = depth + 1
 Degree of the node: The degree of a node is the number of children of that node. In
this case, root node has 2 children. So, the degree of root node of 2.
 Degree of the tree: The maximum degree of any node is called the degree of a tree.
In this case, root node has the maximum degree 2. So, the degree of tree is 2.
Traversal of Binary Tree
Traversal is a process to visit all the nodes of a tree and may print their values too. Because,
all nodes are connected via edges (links) it always start from the root (head) node. That is,
any node of the tree cannot be accessed randomly. There are three ways which are used to
traverse a tree:-

 Pre-order Traversal: - Traverse the root first then traverse into the left sub-tree and
right sub-tree respectively. This procedure will be applied to each sub-tree of the tree
recursively.

Pre order traversal: - F, B, A, D, C, E, G, I, H

 In-order Traversal: - Traverse the left sub-tree first, and then traverse the root and the right
sub-tree respectively. This procedure will be applied to each sub-tree of the tree recursively.

In order traversal: - A, B, C, D, E, F, G, H, I

 Post-order Traversal: - Traverse the left sub-tree and then traverse the right sub-tree
and root respectively. This procedure will be applied to each sub-tree of the tree
recursively.

Post order traversal: - A, C, E, D, B, H, I, G, F

Notes By Priyanka Ghosh 19 | P a g e