Abstract
In daily development, we often create arrays and use methods such as adding and deleting arrays. Now it is time to explore how these methods are implemented in terms of data structures.
The structure of this paper first summarizes the commonly used Array API, then from simple to complex, from basic to combinative ideas, and finally optimize the details. You can organize your thoughts in the order of the article to implement it.
At the end of the article there is a complete code implementation, you can implement as a reference, or do not want to read too much text, directly jump into the code, to see the code to understand yourself is also ok.
In plain English, a dynamic array is an infinite number of elements that can be added without worrying about the number of elements that can be assembled. Its essence is to monitor the remaining space in the array, expand and shrink in time, so that the array dynamically maintain the appropriate size.
The array’s data structures and external API functions are built on common ground, interspersed with some proper code handling. Different coding languages have different implementations, but data structures have been examined for decades, and design logic can be applied to most coding languages.
Common APIS for Array
To sum up, most of the everyday Array apis are covered by the 11 methods listed in the code block below.
The E in the code is the generic type
/** * clears all elements */
public void clear(a)
/** * number of elements * @return */
public int size(a)
/** * whether is empty * @return */
public boolean isEmpty(a)
/** * contains an element * @param element * @return */
public boolean contains(E element)
/** * add element to end * @param element */
public void add(E element)
/** * get the element at index * @param index * @return */
public E get(int index)
/** * set the element in the index position * @param index * @param element * @return original element ֵ */
public E set(int index, E element)
/** * Insert an element * @param index * @param element */
public void add(int index, E element)
/** * remove the index element * @param index * @return */
public E remove(int index)
/** * delete element * @param element */
public void remove(E element)
/** * View the index of the element * @param Element * @return */
public int indexOf(E element)
Copy the codeThe data structure
The data structure of Array mainly includes constructors, member variables that store elements, and member variables that record the number of elements.
public class ArrayList<E> {
/** * Default array size */
private static final int DEFAULT_CAPATICY = 10;
/** * The default identifier */
private static final int ELEMENT_NOT_FOUND = -1;
/** * all elements */
private E[] elements;
/** * Number of elements */
private int size = 0;
/** * initializes the array */
public ArrayList(int capaticy) {
elements = (E[]) new Object[capaticy];
}
/** * Initializes the array (no arguments) */
public ArrayList(a) {
this(DEFAULT_CAPATICY); }}Copy the codeIf you see a elements array property being defined, issue a “?” .
The constructor uses new to create an array, essentially allocating a contiguous space in the heap to store the array. Each index in elements is a pointer to the memory space.
Why apply for heap space to store data?
In memory management, there are stack space and heap space that can store some temporarily created data. The difference is that stack space creation and release are managed by the system, while heap space can be managed by developers themselves. We don’t want to create arrays that we can’t control, so heap space is the best choice.
So why is new applying for heap space? It’s a feature of the code, it doesn’t make any sense, right
Implementation method
The idea is to go from simple to complex
Size is the number of elements in the Array. Size is the number of elements that already exist in the Array
/** * Number of elements *@return* /
public int size() {
return size;
}
/** * is null *@return* /
public boolean isEmpty() {
return size == 0;
}
Copy the codeBecause the elements are stored in the elements array, the method to delete them can be quickly iterated over
/** * clears all elements */
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
Copy the codeThe element method at the index position can be implemented using the array index method
/** * gets the element * at index position@param index
* @return* /
public E get(int index) {
return elements[index];
}
Copy the codeThe element method that sets the index position can also operate directly on the Elements array.
/** * Sets the element * at index position@param index
* @param element
* @returnThe original element ֵ */
public E set(int index, E element) {
E oldElement = elements[index];
elements[index] = element;
return oldElement;
}
Copy the codeAdd elements
After the simple method is implemented, the complex method is implemented. Then implement the basic method first in the complex method.
So now the primary implementation is add(int index, E element)(insert an element in the index position). Why implement it in the first place? Let’s put this problem aside and implement it first
When inserting an element at index, the element at index is moved back one place and then placed at index. Don’t forget to add size plus 1 to the number of elements already stored.
/** * inserts an element * at index position@param index
* @param element
*/
public void add(int index, E element) {
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index] = element;
size++;
}
Copy the codeWe then implement Add (E Element) on top of this method, which inserts an element at the size position. This is why the first implementation inserts an element at the index position.
/** * add the element to the end *@param element
*/
public void add(E element) {
add(size, element);
}
Copy the codeCheck the elements
Following the implementation logic for adding elements, implement the indexOf(E element) (view the indexOf an element) method first. This method needs to handle both non-null and null element cases. If element is null, there is no comparison
/** * View the index of the element *@param element
* @return* /
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
returni; }}}else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
returni; }}}return ELEMENT_NOT_FOUND; // Constant: -1, there is no element in the array
}
Copy the codeBased on this, you can implement contains(E Element) (whether it contains an element). The element index is equal to -1.
/** * Whether to contain an element *@param element
* @return* /
public boolean contains(E element) {
returnindexOf(element) ! = ELEMENT_NOT_FOUND; }Copy the codeRemove elements
Continue to implement the basic method ideas, first implement remove(int index) (delete the index position of the element) method.
The array is iterated from the index position to the end, with successive elements overwriting the preceding ones. Then set the last element to NULL. The size is also going to decrease by 1.
/** * delete element * at index position@param index
* @return* /
public E remove(int index) {
rangeCheck(index);
E oldElement = elements[index];
for (int i = index; i < size; i++) {
elements[i] = elements[i+1];
}
size --;
elements[size] = null;
return oldElement;
}
Copy the codeNext, implement the remove(E Element) method. It gets the index of the Element and then deletes the element at the index position. This is done in both ways.
/** * delete element *@param element
*/
public void remove(E element) {
remove(indexOf(element));
}
Copy the codeAn array
As of now, 11 methods of dynamic arrays have been implemented. After a good flow, start to fill loopholes.
Using the array method, not afraid of the element does not exist, it is necessary to coordinate out of bounds, so we need to pass the index parameter in the method to determine whether out of bounds, if out of bounds, you can not carry out the following code implementation.
/** * check whether coordinates are out of bounds *@param index
*/
private void rangeCheck(int index) {
if (index < 0|| index >= size) { outOfBound(index); }}private void outOfBound(int index) {
throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}
Copy the codeIndex == size; index == size;
private void rangeCheckOfAdd(int index) {
if (index < 0|| index > size) { outOfBound(index); }}Copy the codecapacity
But elements starts with a capacity of 10 elements. If elements exceed elements’ capacity, it needs to be expanded.
When performing the expansion method, it determines whether the capacity is sufficient. If not, it creates a new array with 1.5 times the previous elements capacity, and then iterates through the old array elements and places them in the new array.
/** **@param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity <= oldCapacity) {
return;
}
int newCapacity = oldCapacity + (oldCapacity >> 1); // Expand by 1.5 times
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
Copy the codeRelative, need to shrink? How to achieve capacity reduction? These two problems can be solved according to the actual situation. The idea is similar to capacity expansion.
The overall implementation
Dynamic arrays are perfectly implemented. Next, I will post a complete code, take a look at the code implementation as a whole, and then taste the implementation logic of dynamic array.
@SuppressWarnings({"unused","unchecked"})
public class ArrayList<E> {
/** * Default array size */
private static final int DEFAULT_CAPATICY = 10;
/** * The default identifier */
private static final int ELEMENT_NOT_FOUND = -1;
/** * all elements */
private E[] elements;
/** * Number of elements */
private int size = 0;
/** * initializes the array */
public ArrayList(int capaticy) {
/ / forget
capaticy = (capaticy < DEFAULT_CAPATICY ? DEFAULT_CAPATICY: capaticy);
elements = (E[]) new Object[capaticy];
}
/** * Initializes the array (no arguments) */
public ArrayList(a) {
this(DEFAULT_CAPATICY);
}
/** * clears all elements */
public void clear(a) {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/** * Number of elements *@return* /
public int size(a) {
return size;
}
/** * is null *@return* /
public boolean isEmpty(a) {
return size == 0;
}
/** * Whether to contain an element *@param element
* @return* /
public boolean contains(E element) {
returnindexOf(element) ! = ELEMENT_NOT_FOUND; }/** * add the element to the end *@param element
*/
public void add(E element) {
add(size, element);
}
/** * gets the element * at index position@param index
* @return* /
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/** * Sets the element * at index position@param index
* @param element
* @returnThe original element ֵ */
public E set(int index, E element) {
rangeCheck(index);
E oldElement = elements[index];
elements[index] = element;
return oldElement;
}
/** * inserts an element * at index position@param index
* @param element
*/
public void add(int index, E element) {
rangeCheckOfAdd(index);
ensureCapacity(size+1);
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index] = element;
size++;
}
/** * delete element * at index position@param index
* @return* /
public E remove(int index) {
rangeCheck(index);
E oldElement = elements[index];
for (int i = index; i < size; i++) {
elements[i] = elements[i+1];
}
size --;
elements[size] = null;
return oldElement;
}
/** * delete element *@param element
*/
public void remove(E element) {
remove(indexOf(element));
}
/** * View the index of the element *@param element
* @return* /
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
returni; }}}else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
returni; }}}return ELEMENT_NOT_FOUND;
}
/** **@param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity <= oldCapacity) {
return;
}
int newCapacity = oldCapacity + (oldCapacity >> 1); // Expand by 1.5 times
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private void outOfBound(int index) {
throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}
/** * check whether coordinates are out of bounds *@param index
*/
private void rangeCheck(int index) {
if (index < 0|| index >= size) { outOfBound(index); }}private void rangeCheckOfAdd(int index) {
if (index < 0|| index > size) { outOfBound(index); }}@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("size:").append(size).append("").append("[");
for (int i = 0; i < size; i++) {
if(i ! =0) {
stringBuilder.append(",");
}
stringBuilder.append(elements[i]);
}
stringBuilder.append("]");
returnstringBuilder.toString(); }}Copy the code