ডাটা স্ট্রাকচারঃ Two Way Linked List


জাভাতে C বা C++ এর মত পয়েন্টার নাই। পয়েন্টারের কাজ জাভাতে reference এর মাধ্যমে করা হয়। সাধারন বা ওয়ান ওয়ে লিঙ্ক লিস্টের মত খুব সহজেই জাভা প্রোগ্রামিং ভাষা ব্যবহার করে টু ওয়ে লিঙ্ক লিস্ট তৈরী করা যায়।

কোডঃ

//Two Way Linked List
//Author: Milon

import java.util.NoSuchElementException;

//Node class
class Node{
	//Instance variable
	private Object data;
	private Node nextNode;
	private Node previousNode;

	//Constructor
	public Node(){
		data = null;
		nextNode = null;
		previousNode = null;
		}

	public Node(Object item, Node next, Node previous){
		data = item;
		nextNode = next;
		previousNode = previous;
		}

	//Set methods
	public void setData(Object item){
		data = item;
		}

	public void setNextNode(Node next){
		nextNode = next;
		}

	public void setPreviousNode(Node previous){
		previousNode = previous;
		}

	//Get methods
	public Object getData(){
		return data;
		}

	public Node getNextNode(){
		return nextNode;
		}

	public Node getPreviousNode(){
		return previousNode;
		}

	//Overloaded toString() method
	public String toString(){
		return ("" + data);
		}
	}


//Two Way Linked List class

public class TwoWayLinkedList{
	//Instance variable
	private int size;
	private Node head;
	private Node tail;

	//Constructor
	public TwoWayLinkedList(){
		head = tail = null;
		size = 0;
		}

	//Returns is the list empty
	public boolean isEmpty(){
		return head == null;
		}

	//Returns the size of list
	public int size(){
		return size;
		}

	//Insert element at first position
	public void addFirst(Object item){
		if(isEmpty()){
			head = tail = new Node(item, head, tail);
			++size;
			return;
			}
		Node current = new Node(item, head, null);
		head.setPreviousNode(current);
		head = current;
		++size;
		}

	//Insert an element at last
	public void addLast(Object item){
		if(isEmpty()){
			addFirst(item);
			return;
			}
		Node current = new Node(item, null, tail);
		tail.setNextNode(current);
		tail = current;
		++size;
		}

	//Show the first item
	public Object showFirst(){
		if(!isEmpty())
			return head.getData();
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Show the last item
	public Object showLast(){
		if(!isEmpty())
			return tail.getData();
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Remove the first element
	public Object removeFirst(){
		if(head.getNextNode() == null){
			Node current = head;
			head = null;
			tail = null;
			--size;
			return current.getData();
			}
		if(!isEmpty()){
			Node current = head;
			head = head.getNextNode();
			head.setPreviousNode(null);
			--size;
			return current.getData();
			}
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Remove the last element
	public Object removeLast(){
		if(isEmpty()){
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		if(head.getNextNode() == null){
			--size;
			return removeFirst();
			}
		Node current = tail;
		tail = tail.getPreviousNode();
		tail.setNextNode(null);
		--size;
		return current.getData();
		}

	//Check does the item exists in the list
	public boolean contains(Object item){
		Node current = head;
		while(current.getNextNode() != null){
			if(item.equals(current.getData()))
				return true;
			else
				current = current.getNextNode();
			}
		return false;
		}

	//Traversing the list from front
	public String frontTraverse(){
		String str = "[ ";
		if(head != null){
			str += head.getData();
			Node current = head.getNextNode();
			while(current.getNextNode() != null){
				str += ", " + current.getData();
				current = current.getNextNode();
				}
			str += ", " + current.getData();
			}
		str += " ]";
		return str;
		}

	//Traversing the list from rear
	public String rearTraverse(){
		String str = "[ ";
		if(tail != null){
			str += tail.getData();
			Node current = tail.getPreviousNode();
			while(current.getPreviousNode() != null){
				str += ", " + current.getData();
				current = current.getPreviousNode();
				}
			str += ", " + current.getData();
			}
		str += " ]";
		return str;
		}

	}
//Two Way Linked List Implementation class
//Author: Milon

import java.util.Scanner;
import java.util.Random;

public class TwoWayLinkedListImplement{
	public static void main(String args[]){
		TwoWayLinkedList list = new TwoWayLinkedList();
		Scanner input = new Scanner(System.in);
		Random rand = new Random();

		System.out.print("How many item do you want to insert first: ");
		int n = input.nextInt();

		for(int i=0;i<n;i++)
			list.addFirst(new Integer(rand.nextInt(100)));

		while(true){
			System.out.println("\n");
			System.out.println("* * * * * TwoWayLinkedList Implementation * * * * *");
			System.out.println(" 1. Show the list from front.");
			System.out.println(" 2. Show the list from rear.");
			System.out.println(" 3. Insert an element at first position.");
			System.out.println(" 4. Insert an element at last position.");
			System.out.println(" 5. Show the first element.");
			System.out.println(" 6. Show the last element.");
			System.out.println(" 7. Show the list size.");
			System.out.println(" 8. Search an element in the list.");
			System.out.println(" 9. Remove first element.");
			System.out.println("10. Remove last element.");
			System.out.println("11. Exit\n\n");

			System.out.print("Enter your choice: ");
			int choice = input.nextInt();

			switch(choice){
				case 1:
						System.out.println("The whole list from front is:");
						System.out.println(list.frontTraverse());
						break;

				case 2:
						System.out.println("The whole list from rear is:");
						System.out.println(list.rearTraverse());
						break;

				case 3:
						System.out.print("Enter the element: ");
						int item = input.nextInt();
						list.addFirst(new Integer(item));
						System.out.println("Item inserted successfully.");
						break;

				case 4:
						System.out.print("Enter the element: ");
						int element = input.nextInt();
						list.addLast(new Integer(element));
						System.out.println("Item inserted successfully.");
						break;

				case 5:
						System.out.println("The first element is: "+list.showFirst());
						break;

				case 6:
						System.out.println("The last element is: "+list.showLast());
						break;

				case 7:
						System.out.println("List size is: "+list.size());
						break;

				case 8:
						System.out.print("Enter the searching element: ");
						int key = input.nextInt();
						if(list.contains(key))
							System.out.println("Item found.");
						else
							System.out.println("Item not found.");
						break;

				case 9:
						System.out.println("First element " + list.removeFirst() + " removed.");
						break;

				case 10:
						System.out.println("Last element " + list.removeLast() + " removed.");
						break;

				case 11:
						System.exit(1);
						break;

				default:
						break;
				}
			}
		}

	}

ডাটা স্ট্রাকচারঃ Weighted Graph


যে গ্রাফের প্রত্যেকটা এজের(edge) একটা Weight বা মান দেয়া থাকে তাকে Weighted Graph বলে। Weighted graph তৈরীর কৌশল হল-

কোডঃ

//Weighted graph
//Author: Milon

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int n;
    cout<<"Enter the number of nodes: ";
    cin>>n;
    int list[n][n];

    //Initialize
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            list[i][j]=false;
    cout<<"Enter an edge(start_node< >end_node< >weight)"<<endl;
    cout<<"Press (0 0 0) to end:"<<endl;

    //Making graph
    while(true){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0 && b==0 && c==0)
            break;
        if(a>n || b>n || a<=0 || b<=0)
            cout<<"Invalid input"<<endl;
        else{
            list[a-1][b-1]=c;
            //list[b-1][a-1]=true;      //for undirected weighted graph
            }
        }
    cout<<endl;

    //Print adjacency matrix
    cout<<"Adjacency matrix:"<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            printf("%4d",list[i][j]);
        cout<<endl;
        }
    return 0;
    }

ডাটা স্ট্রাকচারঃ Adjacency List


গ্রাফের নোডের সংখ্যা যদি অনেক বেশী হয়, তখন Adjacency Matrix ব্যবহার করে গ্রাফ তৈরী করা অসুবিধাজনক। সেক্ষেত্রে Linked List ব্যবহার করে গ্রাফ তৈরী করা হয়। গ্রাফের এই ধরনের উপস্থাপনাকে Adjacency List বলে।

কোডঃ

//Adjacency list
//Author: Milon

#include<iostream>
#include<cstdlib>
using namespace std;

struct list{
    int val;
    struct list *next;
    };

struct list head[6];

int main(){
    list *ptr,*newnode;
    int data[14][2] = {{1,2},{2,1},{1,5},{5,1},{2,3},{3,2},{2,4},
                       {4,2},{3,4},{4,3},{3,5},{5,3},{4,5},{5,4}};

    //Adjacency list creation
    cout<<"The adjacent list of the graph : "<<endl;
    for(int i=1;i<6;i++){
        head[i].val=i;
        head[i].next=NULL;
        cout<<"Vertix "<<i<<" => ";
        ptr=&(head[i]);
        for(int j=0;j<14;j++){
            if(data[j][0]==i){
                newnode=new list();
                newnode->val=data[j][1];
                newnode->next=NULL;
                while(ptr!=NULL)
                   ptr=ptr->next;
                ptr=newnode;
                cout<<"["<<newnode->val<<"] ";
                }
            }
        cout<<endl;
        }
    return 0;
    }

ডাটা স্ট্রাকচারঃ Directed Graph


Directed Graph আর Undirected Graph এর মধ্যে বিশেষ তফাৎ নেই। শুধুমাত্র পেছনে আসার রাস্তাটা বন্ধ করে দিলেই Undirected Graph টা Directed হয়ে যাবে।

কোডঃ

//Directed graph
//Author: Milon

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int n;
    cout<<"Enter the number of nodes: ";
    cin>>n;
    bool list[n][n];

    //Initialize
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            list[i][j]=false;
    cout<<"Enter an edge(start_node end_node)"<<endl;
    cout<<"Press (0 0) to end:"<<endl;

    //Making graph
    while(true){
        int a,b;
        cin>>a>>b;
        if(a==0 && b==0)
            break;
        if(a>n || b>n || a<=0 || b<=0)
            cout<<"Invalid input"<<endl;
        else{
            list[a-1][b-1]=true;
            //list[b-1][a-1]=true;      //for undirected graph
            }
        }
    cout<<endl;

    //Print adjacency matrix
    cout<<"Adjacency matrix:"<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            printf("%4d",list[i][j]);
        cout<<endl;
        }
    return 0;
    }

ডাটা স্ট্রাকচারঃ Undirected Graph


গ্রাফ অত্যন্ত গুরুত্বপূর্ণ ডাটা স্ট্রাকচার। বাস্তবধর্মী সমস্যা সমাধানে গ্রাফের কোন বিকল্প নেই।

গ্রাফ তৈরী করার কয়েকটি পদ্ধতি রয়েছে। এদের মধ্যে সবচেয়ে সহজ হচ্ছে Adjacency Matrix. Adjacency Matrix এর মাধ্যমে আনডিরেক্টেড গ্রাফ তৈরী করার পদ্ধতি হচ্ছে-

কোডঃ

//Undirected graph
//Author: Milon

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int n;
    cout<<"Enter the number of nodes: ";
    cin>>n;
    bool list[n][n];

    //Initialize
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            list[i][j]=false;
    cout<<"Enter an edge(start_node end_node)"<<endl;
    cout<<"Press (0 0) to end:"<<endl;

    //Making graph
    while(true){
        int a,b;
        cin>>a>>b;
        if(a==0 && b==0)
            break;
        if(a>n || b>n || a<=0 || b<=0)
            cout<<"Invalid input"<<endl;
        else
            list[a-1][b-1]=list[b-1][a-1]=true;
        }
    cout<<endl;

    //Print adjacency matrix
    cout<<"Adjacency matrix:"<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            printf("%4d",list[i][j]);
        cout<<endl;
        }
    return 0;
    }