Data structure
Day-1 16/6(Introduction)
It is used in designing
It is abstract data type
It has some set of rules that we cannot change
We uses DS for abstract data type
What is data structure? Defination -> working -> real life example
In computer terms a ds is a specific way to store and organize data in computers memory so that these data can be used efficiently later
It belong to structuring the data
Need of Data Structure
Effiency
Reusability
Abstraction
There is two types of DS
Linear
Non-Linearas
Linear
Array
Queue
Stack
Linked list
Non Linear
Graph
Tree
Day-2 17/6(Array,Linkedlist)
Array
class Student
{
private int rollno;
private string name;
private int marks;
public Student()
{
}
public Student(int rollno, String name, int marks)
{
this.name=name;
this.rollno=rollno;
this.name=name;
}
public void accept()
{
Scanner sc =new Scanner(System.in);
Syso(name,rollno,marks);
sc=name,rollno,marks;
}
public void display()
{
System.out.println(name,rollno,name);
}
}
class Team
{
private int size;
Student s[];
public Team(int size)
{
this.size=size;
s=new Student[size];
for(int i=0;i<size;i++)
s[i]=new Student();
}
public void accept()
{
for(int i=0;i<size;i++)
s[i].accept();
}
public void display()
{
for(int i=0;i<size;i++)
s[i].display();
}
}class Program
{
public ststic void main(String [] arr)
{
Team cri = new Team(11);
cri.accept();
cri.display();
Team kabadi = new Team(7);
kabadi.accept();
kabadi.display();
}
}Linked List
It is Linear Data Structure
It connected via links
Disadventage of Array
Slow searching in array so linked list come
Inseration and deletion is slow in array
fixed size in array
memory weastage in array
Because of this disadvantages of array linked list is come in picture
In other hand linked list able to grow in size as needed
Does not required the shifting of items during inseration or deletion.
Each data value is linked with address of next value
Each element is called node
Data values need not be stored in adjacent memory cell
Structure of Linked List
class Node
{
private int data;
private Node next; //Next is data member which will hold the referance of next variable
// One linked list may have multiple node
public Node()
{
data=0;
next=null;
}
public void display()
{
syso(data);
}
}
class Linkedlist
{
Node head;
createNode(int data);
createLinkedList(int numberOfNodes);
}
class Program()
{
PSVM( )
{
Linkedlist l1= new Linkedlist();
l1.createLinklist(5);
l1.display();
}
}Linked list real program
link = next;
public class Linkedlist
{
private Node head;
public Linkledlist()
{
head=null;
}
public void createLinkedlist(int terms)
{
int data =5;
int i;
node newnode=null,move=null;
for(int i=1;i<=term;i++)
{
newnode=new Node(data); //create new node
if(head==null)
head=newnode;
else
{
move=head;
while(move.getNext())!=null)
{
move=move.getNext();
}
move.setLink(newnode);
}
data=data+5;
}
}
public void display()
{
Node move=head;
while(move!=null)
{
System.out.println(" "+move.getData());
move=move.getLink();
}
}
}
Inseration in linked list
move.setLink(newnode);
Steps for creating Linked List
Ask user number of nodes to insert
Create node first
First check whether the linklist is empty or not, if linklist is empty this node will be first node so assign this node as head
Otherwise travel the linkedlist till the end and attach node at end.
Repeat these steps till number of nodes user entered
Assignments and code for Array and LinkedList
Day3 18/6(Operations on Linkedlist)
Operations on Linkedlist
Add begining
Add mid
Delete first node
Note Head is 200 in below img
Delete Mid Node
Delete last node
Day 4 19/6(Searching algorithms)
Searching algorithms
Linear Search
Binary Search
Day 5 21/6(Sorting LinkedList,Doubly LinkedList)
Sorting LinkedList
Doubly LinkedList
Day 6 22/6(Stack,Dynamaic Stack,Reverse String using Stack)
Stack
Some functions in stact
peak()
isFull()
push
pop
push()
Check stack is full.
if the stack is full produce an error and exit
is the stack is not full increment top to point next empty space
adds data element to the stack locationwhere top is pointing
return success
pop()
Checks if the stack is empty
if the stack is empty produce error and exit
if the stack is not empty access the data element at which top is pointing
decrease the value of top by 1
return success
class MyStack
{
private int top,size;
private int arr[];
public MyStack()
{
size=3;
top=-1;
arr=new int[size];
}
public MyStack(int size)
{
this.size=size;
top=-1;
arr=new int[size];
}
public boolean isEmpty()
{
if(top==-1)
{
return true;
}
else
{
return false;
}
}
public boolean isFull()
{
if(top==size-1)
return true;
else
return false;
}
public void push(int element)
{
if(isFull==true)
{
syso("Stack is full");
return;
}
else
{
top++; //increment top
arr[top]=element;
}
}
// it is mandatery that we have to pass paramert to push
public int pop()
{
int element=-9999;
if(isEmpty()==false)
{
element= arr[top];
top--;
}else
{
syso("Stack is empty")
}
return element;
}
public void display()
{
syso("*** Stack is ***");
for(int i=top;i>=0;i--)
{
syso(" "arr[i]);
}
}
}Push take parameter
pop return parameter
so pop always return something
Dynamaic Stack (LikeList stack)
Create Node class
data and next
default constructor
para constructor
getter setter
toString/display()
Create MyClass
having top as Node data type
default Constructor-assign null to top
implement is empty method which will return status whether stack is empty or not if top is null then stack is empty
push method will take data as parameter
create newnode if top isnull newnode become top else add newnode at beg assign top as new nodepop()
check is stack is not empty
mark first node as del
move top to next node
get del.data into data
assign del is null if empty stack return 99999
display()
assign move=top
displaymove.data
increment or shift move to next node.
repeat till move !=null;
class Node
{
private char data;
private Node next;
publuc Node()
{
data="0";
next=null;
}
public Node(char ch)
{
this.data=ch;
next=null;
}
public String toString()
{
return " "+data;
}
//gettersetter
}
class MyStack
{
Node top;
public MyStack()
{
top=null;
}
public boolean isEmpty()
{
if(top==null)
{
return true;
}else{
return false;
}
}
public void push(char ch)
{
Node newnode=new Node(ch);
if(top==null)
{
top=newnode;
}
else
{
newnode.setNext(top);
top=newnode;
}
}
public char pop()
{
char data='0';
Node del=null;
if(isEmpty()==false)
{
del=top;
data=del.getData();
top=top.getNext();
del=null;
}
return data;
}
public String toString()
{
String str="";
Node move=top;
while(move!=null)
{
str=str+"\n\t"+move.getData();
move=move.getNext();
return str;
}
}
}Reverse String using Stack
Day 7 23/6(C2 Stack,Queue )
C2 Stack
class MyStack
{
private int top1,top2,size;
private int [] arr;
public MyStack()
{
}
public boolean isFull()
{
if(top1==top2-1)
return true
}
public boolean isEmpty()
{
if(top1==-1 && top2==size)
return true;
}
public void pushFront(int data)
{
if(isFull())
{
syso("Stac is full")
}else
{
top1++;
arr[top]=data;
}
}
public void pushBack(int data)
{
if(isFull)
{
syso("Stack is full")
}else
{
top2--;
arr[top2]=data;
}
}
public void display()
{
/*
int i;
for(i=top1;top1!=top2;i=(i-1)%size)
{
syso(" "+arr[i]);
}
double i =0,size =5;
i = (int) ((i-1)-(size*Math.floor((i-1)/size)));
*/
for(i=top1;i>=0;i--)
syso(" "+arr[i]);
for(i=size-1;i>=top2;i--)
syso(" "+arr[i]);
}
}Queue
there is two element i.e front and rear
there is enqueue=insert and dequeue=retrive
Insert element
check whether queue is full or not
increment rear and insert data rear position
delete element
check whether queue is empty or not
increment front and return data avalible at front location
isEMPTY()
public boolean is Empty() { if(rear==front) if(rear==front) return true; }isFull() ''' public boolean isFull() { if(rear=size-1) return true; }
Day 8 24/6(Queue,Dynamic Queue,Circular Queue )
Queue
class MyClassMyQueue {
rear(to insert data)
front (to print exit)
size(size of queue())
array }
public void enQueue(int data) {
check queue is not full
increment rear and add data at rear position
print queue is full }
public int deQueue() {
check queue is not empty
increment front and return data avalible at front position -return -9999 }
public int isFull() {
ifrear reach to size-1 }
public int isEmpty() {
when front and rear pointing to same index
}
public void display() {
from front+1 to rear display all array elements }
Dynamic Queue
class Node
{
Book data;
Node next;
public Node()
{
data=null;
next=null;
}
public Node(Book data)
{
this.data=data;
this.next=null;
}
public String toString()
{
return data.toString();
}
//getter and setter
}
class QueueLinkedList
{
Node rear,front;
public QueueLinkedList()
{
rear=null;
front=null;
}
public boolean isEmpty()
{
if(front==null)
{
rear=null;
return true;
}else
{
retur false;
}
}
public void enQueue( Book data)
{
Node newnode = new Node(data);
if(rear == null)
{
rear=front=newnode;
}else
{
rear.setNext(newnode);
rear=newnode;
}
}
public Book deQueue()
{
Book data=null;
if(isEmpty())
{
return data;
}
else
{
Node del;
del=front;
front=front.getNext();
data=del.getData();
del=null;
}
return data;
}
public String toString()
{
String str="";
Node move;
for(move=front;move!=null;move=move.getNext())
{
str=str+" "move.getData().toString();
}
return str;
}
}
class Book
{
int bookid;
String bookname;
public Book()
{
bookid=0;
bookname=null;
}
public Book(int bookid, String bookname)
{
this.bookid=bookid;
this.bookname=bookname;
}
// getter setters
public String toString()
{
return " "+ bookid "and "+ bookname;
}
}
Circular Queue
Enqueue in circular Queue
check queue is not full -- if it is first element in queue increment rear and front by one add data ar rear position --- change rear and add element in array at rear position rear=(rear+1)%size; -- Print Queue is full
DeQueue element from queue --- check queue is not empty --return value at front position -- change front to next index.
Display circular Queue
-- for(int i=front; i!=rear ; i= (i+1)%size) print arr[i] print last element
front =2 rear=1
i=2 30 i=3 40 i=4 50 i=0 60 i=1 X
Day 9 25/6(Dqueue)
Dqueue
pushBack() }
check queue is not full
if rear =-1
increament the rear and add element }
pushFront() {
check queue is not full
}
Day 10 26/6
Day 11 28/6(tree,AVL Tree,Binary tree types)
tree
Binary tree has max 2 node
General tree has as many node as you want
In binary search tree left must be less than root and right is greater than root
AVL Tree
Balanced Tree
Binary tree types
Full Binary tree
All Internal node have must 0 or 2 nodes Complete binary tree
Nodes are left to right only
Complesary need left node Perfect binary
All the nodes at the same level
Every perfect tree is complete
Implement binary tree
Create Node Class
data
left
right
class BinaryTree { root void addNode(int data) { - create node with data - check if root is null - root is newnode - assign move as root - ask where you want to attach node -left = Check if left is avalible(null) attach at left of move break; - if left is not empty - check if right pointer is null - attach node at right of move - break;
} }
class Node
{
private int data;
private Node left,right;
public Npde ()
{
data=0;
left=rigit=nuu;
}
public Node(int data)
{
data=data
}
}
class BinaryTree
{
private Node root;
public Tree()
{
root=null;
}
get set root
public void addNode()
{
Node newnode=new Node(data);
Node move;
char ans;
Scanner sc = new Scanner();
if(root==null)
{
root=newnode;
syso("ROOT IS CREATED");
}else
{
move = root;
while(true)
{
syso("LEFT or RIGHT of"+move.getData());
ans=sc.next().charAt(0);
if(ans=='l' || ans=='L')
{
if(move.getLeft()==null)
{
move.setLeft((nenode)
break;
}else
{
move=move.getLeft();
}
}else if(ans==r)
{
if (move.getRight()==null)
{
move.serRight(newnode);
break
}else
{
move=move.getRight();
}
}else
{
syso("Wrong option");
break;
}
}
}
void inOrder(Node root)
{
Node move=root;
}
}
}Day 12 29/6(Inorder,Preorder,Postorder,Search Element from tree,Graph)
Print Tree Recrusion function
Inorder (LEFT,ROOT,RIGHT)
public void inOrder(Node root)
{
Node move=root;
if(move!=null)
{
inOrder(move.getLeft());
System.out.println(" "+move.getData());
inOrder(move.getRight());
}
}
Preorder(ROOT,LEFT,RIGHT)
public void preOrder(Node root)
{
Node move=root;
if(move!=null)
{
System.out.println(" "+move.getData());
preOrder(move.getLeft());
preOrder(move.getRight());
}
}
Postorder(LEFT,RIGHT,ROOT)
public void postOrder(Node root)
{
Node move=root;
if(move!=null)
{
postOrder(move.getLeft());
postOrder(move.getRight());
System.out.println(" "+move.getData());
}
}
Recursion function saves values in stack so it print stack wise.
In order gives data in sorted manner
Search Element from tree
Delete Node from tree
Graph
Vertex
Edge
Path
Adjacent Node
in degree o0ut degree
sink node/Source node
Day 13 30/6(Graph,unDirectedGraph,Graph Traversa,Adjency List)
Graph
class Graph
{
int vertex;
int graph[][];
public Graph()
{
vertex =5;
graph=new int[vertix][vertex]
}
public Graph(int size)
{
}
public void acceptGraph()
{
Scanner sc = new Scanner(SI)
syso("Enter adjency of ")
fot(int i=0;i<vertex;i++)
{
for(int j=0j<vertex;j++)
{
syso("[i][j]");
graph[i][j]=sc.nextInt();
}
}
}
public void displayGraph()
{
Scanner sc = new Scanner(SI)
syso("Enter adjency of ")
fot(int i=0;i<vertex;i++)
{
syso();
for(int j=0j<vertex;j++)
{
syso(+graph[i][j]);
}
}
}
}
unDirectedGraph
public void addEdge(int i,int j)
{
graph[i][j]=1;
graph[j][i]=1;
}Graph Traversa
DFS-depth
BFS-level
Adjency List
Day 14 1/7(Hash,time complixity,kruskal Algorithm,Prime's Algo,AVL Tree Balanced Factor)
Hash
time complixity
kruskal Algorithm
Prime's Algo
AVL Tree Balanced Factor
Sort
Sorting
Buebble Sort
Selection Sort
Merge Sort
Shell sort
Data Structure
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
Data structures are used as a framework for organizing and storing information in virtual memory forms.
In evey application
-
-
Array
An array is a collection of items stored at contiguous memory locations.
For Storing data
in heap
-
Linked List
Linked list is linear data structure where each element is dynamically allocated. Each node contain two parts, namely the data and the reference
to overcome disadvantage of array
Data Structure(Ralilway)
-
Compiled by Shreeshail Vitkar
Feel free to fork @ C-dac Notes
Last updated
Was this helpful?