Data Structures and Algorithms with Java - Part I (Data Structures)

#DSA  ගැන Google එකේ search කරලම එපා වෙලාද? තමන් හොයපු හරි උත්තරේ තාම හම්බුන් නැද්ද? මෙන්න සරලව ගවේෂකගෙන් DSA ඉගන ගන්න.

ඔන්න ගවේෂක DSA Javaත් එක්ක ප‍ටන් ගන්නවා කට්ටියටම මුල ඉදන් සරලව

මොකක්ද DSA කියන්නෙ?

There are some sub topics under DSA .Let’s see what are they and I will describe them one by one to you

Actually what is an Algorithm?

In a simple way Algorithm is a set of steps to achieve a goal in a particular order.

ඇත්තටම ඇල්ගොරිදම් එකකින් කරන්න පුලුවන් මොනාද?

**********

ඉස්සෙලම බලමු මොනද මේ problem solving steps කියලා

1. Identifying the problem

2. Understanding

3. Identifying alternative solutions

4. Select best solution

5. List down the instruction to solve the problem

6. Checking the result as it was suggested

Let’s categorize the data structures,

We are come with several DSA such as Array, Stack, Queue, Linked List, and Tree.

Array

In array ,

·       Random Access

·       Both can limited and not limited size

Array Implementation,

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package arraystack;

/**
 *
 * @author lahiru dananjaya
 */
public class array {
    
    
    
    
    
    public static void main(String[] args) {
        /**
         * can add any number of elements
         */
        int array_unlimited[]={2,1,6,4,8,7,8,7,8}; 
        
        for (int i = 0; i < array_unlimited.length; i++) {
            System.out.println("Index ["+i+"] is "+array_unlimited[i]);
        }
        /****************************************************************/
        System.out.println();
        /**
         * can add limited number of elements
         */
        
        int array_limited []=new int[4];
        array_limited[0]=4;
        array_limited[1]=6;
        array_limited[2]=5;
        array_limited[3]=1;
    
        for (int i = 0; i < array_limited.length; i++) {
            System.out.println("Index ["+i+"] is "+array_limited[i]);
        }
        
    }
}

         

Stack

          In stack ,

·       Using LIFO(Last In First Out) method

·       Can access only top index

·       Based on array structure

·       Push-insertion

·       Pop-deletion

·       Peek-reading top value

·       IsEmpty/IsFull- check whether empty or full

·       Can use for Recursion, Reverse a word and for Balance parenthesis

Stack Implementation,

package queue;

import java.util.Scanner;

/**
 *
 * @author lahiru dananjaya
 */
public class Stack {
    
    private int top=-1;
    private int size;
    private int pop;
    private char data[];
    
    public void push(char val){
        this.data[++top]=val;
    }
    
    public Stack(int  size){
        this.size=size;
        this.data=new char[size];
    }
    
    public char pop(){
        return data[top--];
     
    }
    
    public boolean isFull(){
        return (top==size-1);
    }
    
    public boolean isEmpty(){
        return (top==-1);
    }
    
    public static void main(String[] args) {
       Scanner c=new Scanner(System.in);
       System.out.println("Enter word");
       
        
        String test=c.next();
        
        Stack s=new Stack(test.length());
        for (int i = 0; i < test.length(); i++) {
           s.push(test.charAt(i));
        }
        
        for (int i = 0; i < test.length(); i++) {
           
            System.out.println(s.pop());
        }
        
                
    }
  
}

Queue

·       First In First Out

Queue Implementation,

import java.util.Scanner;

/**
 *
 * @author lahiru dananjaya
 */
public class Queue {

    private int maxsize;
    private int[] data;
    private int rear=-1;
    private int front=0;
    private int nItem=0;
  /**
   * 
   * @return 
   */
    Queue(int size){
        this.maxsize=size;
        data=new int[maxsize];
    }
       
    public boolean isFull(){
        
        if(nItem==maxsize){
            return true;
        }else{
            return false;
        }
    }
    
    public boolean isEmpty(){
        if(nItem==0){
            return true;
        }else{
            return false;
        }
    }
    
    public void insert(int data){
        this.data[++rear]=data;
        nItem++;
    }
    
    public int remove(){
        nItem--;
        return data[front++];
    }
    
    
    
    public static void main(String[] args) {
        System.out.println("Enter Queue size");
        Scanner s=new Scanner(System.in);
        Queue a=new Queue(s.nextInt());
        
        while(!a.isFull()){
            System.out.println("Enter Data :");
            a.insert(s.nextInt());
        }
        
        while(!a.isEmpty()){
            System.out.println(a.remove());
        }
    }
}

Linked List

·      Ordered sequence

·       No random access

·       Forward and Backward

Linked List Implementation(Refere Code),

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package arraystack;

/**
 *
 * @author lahiru dananjaya
 * This is a referenced code for linked list
 */
class Node {
    Node next;
    int num;
    public Node(int val) {
        num = val;
        next = null;
    }
}

class LinkedList {

    private Node head = null;

    public void append(int val) {
        Node lastNode = getLastNode();
        if (lastNode == null) {
            head = new Node(val);
        } else {
            lastNode.next = new Node(val);
        }
    }

    public void delete(int val) {
        if(head == null){
            return;
        }

        Node prevNode = null;
        Node currNode = head;
        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }
        if(prevNode == null){
            head = head.next;
            return;
        }
        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
            return;
        }
        prevNode.next = currNode.next;
    }

    public void print() {
        System.out.println("");
        if(head == null){
            System.out.print("EMPTY");
            return;
        }
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
    }

    private Node getLastNode() {
        if (head == null) {
            return null;
        }
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        return tmpNode;
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList();
        myList.print();
        myList.append(35);
        myList.append(33);
        myList.print();
        myList.delete(33);
        myList.delete(35);
        myList.delete(35);
        myList.print();
    }
}