Foreword

Next, we went into collection learning. After reading a lot of articles, it was very boring to explain the principles. Any mature solution appears to solve the problem. If you introduce it through actual problems and then explain the original ideal, you must learn more with less effort. From me From the day I wrote the blog, I was thinking about how to make the children’s shoes that read the article understand what I was explaining in an easy-to-understand way. Even if the article is long, it will not feel boring if it is progressively layered, so my mind Here is constantly turning at height to find a suitable example. The set learning will be divided into three parts: example introduction, source code analysis and data structure analysis.

Getting Started with Collections

Let ’s take an example to introduce the assembly. When we go to school, we take physical education classes. First, the physical education teacher will ask us how many students stand in pairs to register, and then they are free to dissolve and rest, haha. The physical education teacher asked us to stand in pairs. At this time, it is good to store data in the array. We assume that the physical education teacher needs 5 people to stand in pairs, so this also corresponds to the capacity of the array initialization. After having the capacity, the next step is to The required place is at the specified position, which is like adding elements to the array. Now we will implement this requirement in Java. First we define a queuing class. According to the idea of ​​object-oriented encapsulation, we provide external operation methods, so in this class, we define private arrays, and then define the number of elements in the collection, as follows:

 

 

public  class QueueDemo {

    private  int Size;

    private Integer [] Elements;

}

 

 

According to our analysis, we stand in pairs of 5 people, so when we initialize the queue class, we initialize the array capacity, that is, we initialize the capacity in the constructor, as follows:

 

 

public  class QueueDemo {

    // array size 
    private  int Size;

    // Array 
    private Integer [] Elements;
    
    // Initialize array capacity 
    public QueueDemo ( int capacity) {
        Elements = new Integer [capacity];
    }

}

 

 

After we initialize the capacity, the next step is to start queuing for the corresponding students. At this time, it is corresponding to add elements to the array, so we encapsulate a method of adding, and the size of the array is incremented by 1, as follows:

    // Add element 
    public  void Add (Integer element) {
        Elements [Size] = element;
        Size ++ ;
    }

For each step, we loop through and print out the elements in the array, so next we override the toString method, as follows:

 

 

  // Override toString print element 
    @Override
     public String toString () {
         int length = Elements.length;
        StringBuilder sb = new StringBuilder ();
        sb.append ( "[" );
         for ( int i = 0; i <length; i ++ ) {
            sb.append (Elements [i]);
            if (i! = length-1 ) {
                sb.append ( "," );
            }
        }
        return sb.toString ();
    }

 

 

We have completed the first step of class queuing. Next, we instantiate the above queuing class and add elements (we consider the elements as the names of the students when queuing), and finally print the elements, as follows:

 

 

public  class Main {

    public  static  void main (String [] args) {
        QueueDemo demo = new QueueDemo (5 );
        demo.Add ( 1 );
        demo.Add ( 2 );
        demo.Add ( 3 );
        demo.Add ( 4 );
        demo.Add ( 5 );
        System.out.println (demo);
    }
}

 

 

When the students lined up, the physical education teacher found that the students in the queue were of different heights, and then exchanged between the students and students according to the height. This also corresponds to the method we need to encapsulate the inserted elements, because we initialize the array capacity as 5. When we insert an element at the specified index, reprinting the element will necessarily throw an array exception, which involves expanding the capacity of the array. We will temporarily define the method of inserting the element at the specified index, as follows:

public  void Insert ( int index, Integer element) {
        
}

After arranging the teams according to the height, the physical education teacher thinks that only 4 people need to be arranged in one column, and the remaining one goes to the other pairs. This also corresponds to deleting the elements in the array. Similarly, we define the deletion method. The elements after the deleted elements need to be moved forward by one, and the last position is empty, and the size of the array is reduced by one, as follows:

 

 

// Remove element 
public  void Remove (Integer element) {
         int index = GetIndex (element);
         for ( int i = index; i <Elements.length-1; i ++ ) {
            Elements [i] = Elements [i + 1 ];
        }
        Elements [Size -1] = null ;
        Size - ;
}

 

 

Next let’s delete and print the elements, as follows:

        // Remove element 
        demo.Remove (3 );
        System.out.println (demo);

Java_enrty_series_[6]_Principles_of_dynamic_array_0.png

Because we set the last element of the array to empty, it should be deleted when printing, and we continue to rewrite the toString method rewritten as follows:

 

 

    @Override
     public String toString () {
         int length = Elements.length;
        StringBuilder sb = new StringBuilder ();
        sb.append ( "[" );
         for ( int i = 0; i <length; i ++ ) {
             if (Elements [i] == null) {
                continue ;
            }
            sb.append (Elements [i]);
            if (i! = length-1 ) {
                sb.append ( "," );
            }
        }
        if (sb.charAt (sb.length ()-1) == ',') {
            sb.delete (sb.length ()-1 , sb.length ());
        } 
        sb.append ( "]" );
         return sb.toString ();
    }

 

 

Java_enrty_series_[6]_Principles_of_dynamic_array_1.png

Next, the physical education teacher asked for the count. For example, according to the name of the classmate, that is, the number of the element (which corresponds to the index in the array), so at this time we encapsulate a method to get the specified element, as follows :

 

 

// Get the specified element index 
public  int GetIndex (Integer element) {
         for ( int i = 0; i <Elements.length-1; i ++ ) {
             if (! Elements [i] .equals (element)) {
                 continue ;
            }
            return i;
        }
        throw  new RuntimeException ("Not found" );
}

 

 

Then we try to get the queued position of class 4 as follows:

System.out.println ("The position of class 4 is:" + demo.GetIndex (4));

Java_enrty_series_[6]_Principles_of_dynamic_array_2.png

At this point, we have completed the basic requirements for queuing, but it is not enough. For example, we are customizing the initial capacity. Here we specify 5. After the delete operation, there are 4 elements in the final array. If we add another At least 2 or more elements, printing array elements will throw an exception at this time, so in order to solve this problem, we will automatically expand the array, that is, modify the addition method. When adding elements, we need to determine whether the array capacity has been exceeded If it exceeds, we will expand the capacity of the array to twice the capacity of the existing array, then how should we judge? We judge by array size and array capacity, as follows:

 

 

    public  void Add (Integer element) {
         if (Size> = Elements.length) {
            Elements = Arrays.copyOf (Elements, 2 * Elements.length);
        } 
        Elements [Size] = element;
        Size ++ ;
    }

 

 

 

 

public  static  void main (String [] args) {
        QueueDemo demo = new QueueDemo (5 );
        demo.Add ( 1 );
        demo.Add ( 2 );
        demo.Add ( 3 );
        demo.Add ( 4 );
        demo.Add ( 5 );
        System.out.println (demo);
        // Remove element 
        demo.Remove (3 );
        System.out.println (demo);
        System.out.println ( "The position of Class 4 is:" + demo.GetIndex (4 ));

        demo.Add ( 6 );
        demo.Add ( 7 );
        System.out.println (demo); }

 

 

Java_enrty_series_[6]_Principles_of_dynamic_array_3.png

When we queue up, we give 5 people, which means that the initial capacity of the array is 5, which is not flexible enough. If the physical education teacher has clearly specified how many columns must stand, we can directly receive the signal specified by the physical education teacher. For example, if the initialization capacity of the array is explicitly specified, this will not only guarantee that no exception will be thrown, but also will not affect the performance overhead caused by the expansion when adding and inserting elements. If the number of stations in a column is not explicitly specified, We can also initialize the capacity by default, which is the most flexible, everything has not changed and has the best performance. As follows, we define a default initialization capacity and transform the queue constructor, as follows:

 

 

    private  int DEFAULT_CAPACITY = 10 ;

    public QueueDemo () {
        Elements = new Integer [DEFAULT_CAPACITY];
    }

    public QueueDemo ( int capacity) {
        Elements = new Integer [capacity <= 0? DEFAULT_CAPACITY: capacity];
    }

 

 

At this point, we have not implemented the Insert method of inserting elements at the specified index position. Since we want to insert the specified index position, we must first check whether the specified index position exceeds the size of the array, and then move the element after the specified index backward by one bit, and finally leave Insert at the specified index position, as follows:

 

 

public  void Insert ( int index, Integer element) {
         if (Size <= index || index <0) {
            throw new RuntimeException ("Out of array boundary");
        }
        System.arraycopy (Elements, index, Elements, index + 1,
                Size- index); 
        System.out.println ( this );
        Elements [index] = element;
        Size ++ ;
 }

 

 

 

 

        QueueDemo demo = new QueueDemo ();
        demo.Add ( 1 );
        demo.Add ( 2 );
        demo.Add ( 3 );
        demo.Add ( 4 );
        demo.Add ( 5 );
        System.out.println (demo);
        // Remove element 
        demo.Remove (3 );
        System.out.println (demo);
        System.out.println ( "The position of Class 4 is:" + demo.GetIndex (4 ));

        demo.Add ( 6 );
        demo.Add ( 7 );
        System.out.println (demo);

        // Insert element 
        demo.Insert (2, 20 );
        System.out.println (demo);

 

 

Java_enrty_series_[6]_Principles_of_dynamic_array_4.png

As above, we first check whether the specified index is less than 0 or whether it exceeds the size of the array, otherwise an exception is thrown. Then we use the built-in method to copy from the element after the specified index position, that is, Index + 1, and the length of the last copied element is Size -Index. At this time, the specified index position data is still 4, and finally we replace the value of the specified index position with the value we want to insert.

Summary

The above is our implementation of a relatively complete queuing requirement. Of course, there are some small problems with parameter checking. It must be clear that many children’s shoes are seen here. In fact, what we have implemented is a collection in Java. With the foundation of this lesson In the next lesson, we will be handy for ArrayList source code analysis. Thanks for reading. See you in the next section.

Java entry series [1] string creation method

Java entry series [2] string features

Java entry series [3] stringbuilder string buffer

Java entry series [4] packaging class

Java entry series [5] inheritance abstract classes interfaceson

Java entry series [6] Principles of dynamic array

Java entry series [7] collection arraylist

Java entry series [8] principles of doubley linked list alogrithm

Java entry series [9] linkedlist source code analysis

Java entry series [10] Hash algorithm principle

Java entry series [11] Hashtable source code analysis

Java entry series [12] Hashcode and equals

Java entry series [13] Principles of the read-black tree algorithmn method

Java entry series [14] Hashmap source code ananlysis

 

Orignal link:https://www.cnblogs.com/CreateMyself/p/11440876.html