Java data structure array of Power nodes Java College

  • 2020-06-23 00:21:23
  • OfStack

What's the use of arrays? When you need to size up 30 Numbers, an array is a good way to store them. When you are the head teacher of a class, an array is also useful for recording the number of absences of those students each time. Arrays can be inserted, deleted, searched, etc.

1) Creation and memory allocation

There are two types of data in Java, basic types and object types, also known as reference types. Java treats arrays as objects and USES the new operator when creating arrays.


 int array[] = new int[10]; 

Now that is an object, then array array is a reference, according to Java programming thought (1) - 1 are objects of memory allocation, array will create a space on the stack, and storage space to save the array storage address, really is to save the object, new operation opened up the space in the heap, then array address first.

Initialization:


public class UseArray { 
   public static void main(String[] args) { 
     int array[] = new int[10]; 
     System.out.println(array[2]); 
     UseArray a[] = new UseArray[12]; 
     System.out.println(a[1]); 
     int array2[] ={1,2,3,4,5,5,6}; 
   } 
 } 

The value in the array after new is initialized to 0 by default, while the initialization of the object is empty. null can also be initialized by {}.

2) Use after array encapsulation


public class UseArray { 
   private int[] array; 
   private int number = 0; 
   public UseArray(int max){ 
     array = new int[max]; 
   } 
   public void insert(int value){ 
     array[number] = value; 
     number++; 
   } 
   public int find(int value){ 
     for (int i= 0; i < number; i++) { 
       if(array[i]==value) 
         return i; 
     } 
     return number; 
   } 
   public boolean delete(int value){ 
     int index = find(value); 
     if(index != number){ 
       for (int i = index; i < number-1; i++) { 
         array[i] = array[i+1]; 
       } 
       number--; 
       return true; 
     } 
     return false; 
   } 
   public void display(){ 
     for (int i = 0; i < number; i++) { 
       System.out.printf(array[i]+" "); 
     } 
   } 
   public static void main(String[] args) { 
     UseArray ua = new UseArray(5); 
     ua.insert(1); 
     ua.insert(2); 
     ua.insert(6); 
     ua.insert(7); 
     ua.insert(3);       
     ua.display(); 
     if(ua.find(5) != ua.number){ 
       System.out.println("find,the number index is "+ua.find(5)); 
     }else{ 
       System.out.println("not found!"); 
     } 
     if(ua.delete(5)!=true){ 
       System.out.println("can not delete!"); 
     } 
    ua.display(); 
   } 
 } 

Encapsulate the entire array, replacing the number of arrays with number, inserting data regardless of which index to insert, and of course, you can customize the method of a specific index.

Not introduced the method is simple, but there is a defect in delete there, in fact just left from removing elements, so, although number decreased, but the last one element is not deleted, just when display output display hidden, but next time to insert elements, the new element will replace the last one element position.

3) Search optimization -- 2 points search


 public int find(int value){ 
     int start = 0; 
     int end = number-1; 
     while(end>=start){ 
       int index =(end + start)/2;  
       if(array[index]==value){ 
         return index; 
       }else if(array[index] >value){ 
         end = index-1; 
       }else {  
         start = index+1; 
       } 
     } 
     return number; 
   } 

A 2 point search is only possible if the array is already ordered. At first index was written as end and start subtracted, creating an endless cycle. It's really the addition. 1,2,3,6,7. index=2, value=7, 3 is less than 7, start=3, then index wants the middle number between 3 and 4, so it's the sum divided by 2,6 is less than 7, start=4, find to 7.

4) Large O representation

Set N as the total number of data, add and insert one data time as K. So the total linear lookup time is T=K*N/2, because the lookup is about half of the comparison.

T=k*log2(N). Large O notation, O can be seen as order of, which is about the same meaning, k/2 is also a constant, so can be seen as O(N).

The downside of arrays is that they're fixed in size, they're slow to find, and if you're always looking for millions of data, would you still use arrays? No, so the selection of data structure should be combined with the actual situation to achieve the maximum efficiency value.


Related articles: