Java version and C language version simply use static language to realize dynamic array

One advantage of dynamic language over static language is that the size of array does not need to be determined in advance. It is very useful for some scenes where the length of array is uncertain. Like PHP, you just need to declare the array $arr = array (), and then you can directly $arr [] = 1, $arr [] = 2, $arr [] = 3 In this way, elements are added all the time. When an element is deleted, unset ($arr [1]) is directly used, and the element space is released. However, the native arrays of C and Java are not so convenient. When declaring, the length must be determined in advance, and the compiler allocates the corresponding memory space. However, through some clever practices, the same function can be realized, which is also the main content of this paper.

Java version

Java comes with a collection class ArrayList, which can realize the function of dynamic array. Compared with the native array, it is very convenient to use. When reading the Tomcat source code, I found that for performance reasons, I used the native array instead of the native ArrayList. I implemented a dynamic array myself. The following implementation is directly borrowed from the Tomcat source code.

Realization idea

Add elements dynamically

Initializes an array with a fixed size.

Get the size of the source array and apply for an array 1 bit larger than the original array in the method area.

The key is to call system Arraycopy (SRC, DeST, SRC. Length), copy Src. Length from 0 bit of SRC From the length bit to the 0 bit of DeST, it is more convenient to use the method provided by the system. You can also write a loop to copy.

Put the element to be added in the last bit of the new array.

Return the element and copy the pointer of the new array to the original array variable. The Java array is reference type. After SRC = dest is executed, the two actually point to the same memory address.

Dynamically delete elements

Initializes an array with a fixed size.

Apply for an array one bit smaller than the native array in the method area

Starting from the index bit, move the following elements forward one bit at the same time to overwrite the element to be deleted.

Return the element and point the changed array to the new array

C language version

The implementation of dynamic array in C language is relatively complex, because C language needs to operate pointer and memory. Before starting, you need to define a structure ArrayList and a structure variable ArrayList, which contain two arrays. One is an int pointer, which is used to point to the memory storing int arrays, and the other is a count, which is used to record the length of the array, because through malloc(), Realloc () performs dynamic memory allocation (allocation during program execution). You can't get the correct memory length with sizeof (), so you must define a variable count to record how much memory is applied to the system. Why do you need to create an array with malloc instead of using new int [] directly like Java? This involves a difference between Java and C memory allocation. The array in Java method is stored in the heap, while the memory allocated by the array in C function is stored in the stack. When the function is executed, the memory space of the array will be released. Therefore, malloc needs to apply for space from the stack.

Realization idea

Add elements dynamically

Re apply for a new memory space through realloc(), which is one int longer than the current array, and point to the space through a pointer of type int *.

Put the data in the last bit of the array.

Perform + + operation on the length of the array of records.

Dynamically delete elements

Judge whether the index passed in by the function is valid.

Move the array data greater than index forward by one index.

Re apply for space and reduce the length of the array by an int.

The length of the array of records is -- manipulated.

demo. h

summary

The above is what Xiaobian introduced to you. Java simply uses static language to realize dynamic array. I hope it will be helpful to you. If you have any questions, please leave me a message, and Xiaobian will reply to you in time. Thank you very much for your support for the programming tips website!