Ordered Array Data Structure Example

The following is the example code for an ordered array data structure. OrderedArrayDataStructure class encapsulate the array and its algorithms. We could have used binary search to find the position where we can insert element into the array. But for simplicity we can use linear search in insert method.

Ordered Array data structure and algorithms

package com.sneppets.dsalgo;

public class OrderedArrayDataStructure {
	
	//reference to array arr
	private long[] arr; 
	
	//number of elements in the array
	private int n;
	
	//constructor
	public OrderedArrayDataStructure (int arrSize){
		
		//create array
		arr = new long[arrSize];
		
		//no elements yet 
		n = 0;
	}
	
	//method to return number of elements in the array currently
	public int size(){
		return n;		
	}
	
	//find element using binary search
	public int find (long elementKey){
		
		int lBound = 0;

		int uBound = n-1;
		
		int cursIn;
		
		while (true){
			
			cursIn = (lBound + uBound)/2;
			
			if(arr[cursIn] == elementKey){
				
				return cursIn; //found the element
			}
			else if(lBound > uBound){
				
				return n; //can't find it
			}
			else { //divide range logic
				
				if(arr[cursIn] < elementKey) {
					
					lBound = cursIn + 1; //it's in upper half
										
				}
				else {
					
					uBound = cursIn -1; //it's in lower half
				}
				
			} //end of divide range logic
			
		} //end of while
		
	} //end of find
	
	//insert element into array - can use binary search to locate the position where new item will be inserted. But for simplicity we can use linear search in insert().
	public void insert(long element){
		
		int i;
		
		for (i=0; i<n; i++)			
			if(arr[i] > element) //linear search				
				break;
		
		for (int j=n; j>i; j--) //moving bigger ones up				
			arr[j] = arr[j-1];		
			
		arr[i] = element; //insert the element
			
		n++; //increment the size 
		
	} //end of insert
	
	public boolean delete(long element){
		
		int i = find(element); //binary search - to locate the item to be deleted	
	
		if (i == n){ //can't find it
			
			return false;			
		}
		else { //found the element		
			
			for(int j=i; j<n; j++){ //move larger ones down
				
				arr[j] = arr[j+1];
			}			
			
			n--; //decrement size
			
			return true;
		}
		
	} //end of delete function
	
	//display array contents
	public void display(){
		
		for(int i=0; i<n; i++){
			
			System.out.println(arr[i]+ " ");
			
		}
			
	}

}

OrderedArrayDataStructureTest.java

package com.sneppets.dsalgo;

public class OrderedArrayDataStructureTest {
	
	public static void main (String[] args){
		
		//array size
		int arrSize = 10;
		
		//reference to array data structure
		OrderedArrayDataStructure arrayDS;
		
		//create the array
		arrayDS = new OrderedArrayDataStructure(arrSize);
		
		//insert 5 elements
		arrayDS.insert(11);
		arrayDS.insert(33);
		arrayDS.insert(55);
		arrayDS.insert(22);
		arrayDS.insert(44);	
		
		//display array elements
		arrayDS.display();
				
		//search for element 77
		int element = 22;
		
		if(arrayDS.find(element) != arrayDS.size()){			
			System.out.println("Found element "+ element);			
		}
		else{			
			System.out.println("Could not find element "+ element);			
		}
			
		//delete 2 elements
		arrayDS.delete(33);
		arrayDS.delete(55);
		
		//display again
		arrayDS.display();		
	}

}

Output

11 
22 
33 
44 
55 
Found element 22
11 
22 
44