Handwritten ArrayList using Java
Almost all languages have arrays, and Java is no exception. The characteristic of array is that the length must be determined during initialization. Even if the capacity reaches, it cannot be automatically expanded to meet the requirements, Therefore, we can use the dynamic array (ArrayList) to realize the array that can be automatically expanded. Refer to the official ArrayList implementation of Java: java.util.ArrayList. The bottom layer of ArrayList is array, which is equivalent to the enhanced version of array. It can automatically expand the capacity and add, delete, modify and query data.
be careful:
The following uses dynamic arrays to represent ArrayList and arrays to represent Object []
Private property
At least it needs to represent the size of the dynamic array and the basic array elements [], so it should have the following attributes:
public class ArrayList<E> {
/**
* Dynamic array size
*/
private int size;
/**
* Dynamic array
*/
private E[] elements;
}
Note that generics are used here to facilitate the sequential storage of similar data (data of the same type)
Construction method
Nonparametric construction method: create an array of default capacity;
Parameterized construction method: create an array with a specified capacity.
Since default is involved, we can specify a constant as the default capacity, which can be as much as we need.
/**
* Dynamic array default capacity
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Parameterless construction, creating an array of default size
*/
public ArrayList(){
}
/**
* Parametric construction, create an array according to the capacity
* @param capacity Custom capacity
*/
public ArrayList(int capacity){
}
be careful:
capacity refers to how many elements the dynamic array can hold, not how many elements have been stored in it. Generally, the length of the array elements.length is equal to him.
size refers to how many elements the dynamic array already has.
Nonparametric structure
Create an Object array of default capacity, and then force type conversion.
public ArrayList(){
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
Parametric structure
To create an array with a specified capacity, you need to control the size of the incoming capacity. Negative numbers are not allowed.
public ArrayList(int capacity){
if (capacity<=0) capacity = DEFAULT_CAPACITY; //If the incoming capacity is not a natural number, it is forced to be the default capacity
elements = (E[]) new Object[capacity];
}
Basic method
Imitation Java util. ArrayList, the following basic methods are obtained, including basic addition and deletion of query elements.
public class ArrayList<E> {
/**
* Dynamic array size
* @return Dynamic array size
*/
public int size(){}
/**
* Is the dynamic array empty
* @return Is the dynamic array empty
*/
public Boolean isEmpty(){}
/**
* Add element
* @param element element
*/
public void add(E element){}
/**
*
* 0 1 2 3 4 5 6 7 8 9
* 1 2 3 4 5 6 7 8
* Adds an element to the specified location
* @param index position
* @param element element
*/
public void add(int index,E element){}
/**
*
* 0 1 2 3 4 5 6 7 8 9
* a b c 1 d e f g h
* Removes the element at the specified location
* @param index position
*/
public void remove(int index){}
/**
* Deletes the specified element
* @param element element
*/
public void remove(E element){}
/**
* Empty elements in dynamic array
*/
public void clear(){}
/**
* Modify the element at the specified location
* @param index position
* @param element element
*/
public void set(int index,E element){}
/**
* Gets the element at the specified location
* @param index position
* @return element
*/
public E get(int index){}
/**
* Determine whether the array contains the element
* @param element element
* @return true Contains, false does not contain
*/
public Boolean contains(E element){}
/**
* The subscript of the first occurrence of the element
* @param element element
* @return subscript
*/
public int indexOf(E element){}
@Override
public String toString() {}
}
size()
Returns the size of a dynamic array
public int size(){
return size;
}
isEmpty()
Returns whether the dynamic array is empty and determines whether the size is 0
public Boolean isEmpty(){
return size == 0;
}
toString()
Print the dynamic array, which can be based on your own needs
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("ArrayList{");
string.append("size=" + size + ", elements=[");
for (int i = 0; i < size; i++) {
string.append(elements[i]);
if (i != size -1) { //Do not add a comma at the end of the last element
string.append(", ");
}
}
string.append("]");
string.append("}");
return string.toString();
}
indexOf() and contains()
The index of the first occurrence of the element returned by indexOf() (circular array. If there is such an element, the index will be returned. If the index is - 1, it means there is no such element)
public int indexOf(E element){
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) return i; //Return subscript if element exists
}
return -1;
}
contains() determines whether the element exists. indexOf() is used to determine whether the element exists. If there is a subscript, it indicates that the element exists. If there is no subscript, it does not exist
public Boolean contains(E element){
return indexOf(element) >= 0;
}
get()
Returns the array element of the specified subscript
public E get(int index){
return elements[index];
}
set()
Inserts an element into the specified subscript
public void set(int index,E element){
elements[index] = element;
}
add()
Add elements to the end of the dynamic array.
public void add(E element){
elements[size] = element;
size++;
}
Overload the method add(int index, E element) to add elements to the specified location, and the original elements will move backward in turn. The purpose of element movement is to empty the elements of index subscript, so the index subscript and its subsequent elements need to be moved back in turn. The order of moving should be
Note that the first is to move the last one first. If you move from the index, the latter will be overwritten. Move it one by one, and then the element at the index subscript will be empty, and then insert the element to be inserted.
public void add(int index,E element){
for (int i = size; i > index ; i--) { //The elements move back in turn
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
Similarly, in fact, add(E element) is to add elements to the end of the dynamic array, so you can directly call the overloaded method and specify the subscript as the end (size).
public void add(E element){
add(size,element);
}
remove()
Remove the element at the specified position. After removing the element at the specified position, the element at the specified position will be deleted, and then the elements behind the specified position will move forward in turn.
Note that you don't have to delete the specified element. In Java features, As long as a memory address is no longer pointed to, it will be garbage collected (regarded as deletion), so directly use the following elements to directly overwrite the elements with the specified subscript. The address of the original element is not pointed to, so it will be deleted. Finally, set the last element to null. However, it should be noted that deletion moves the front first and then the back. If it moves from back to front, it will be overwritten.
public void remove(int index){
for (int i = index; i < size-1 ; i++) { //Move the elements forward in turn
elements[i] = elements[i+1];
}
elements[size-1] = null; //Set the last element of the array to null
size--;
}
clear()
Clear the dynamic array and directly set all positions to null, then the address of the previous element will not be pointed to and will be deleted.
public void clear(){
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
Subscript out of bounds
When the above method passes in the index, the index may exceed the limit, such as being negative or exceeding the upper limit. Therefore, it is necessary to control the effective range of the index, and check it every time it is passed in, and an exception will be thrown when an error occurs.
be careful
The index range of add() is different from that of remove(), get(), and set(). Adding elements allows you to add elements to the last position of the dynamic array, so index can access size, but deletion, query and modification are based on the existence of elements in the dynamic array, so index cannot access size, remember!!!
checkIndex()
Check the subscript index when it is not added. It cannot be less than 0 or greater than or equal to size (0 < index < size)
private void checkIndex(int index){
if (index<0||index>=size) indexOutOfBoundsException(index);
}
checkIndexAdd()
Check the subscript index when adding. It cannot be less than 0 or greater than size (0 < index ⩽ \leqslant ⩽size)
private void checkIndexAdd(int index){
if (index<0||index>size) indexOutOfBoundsException(index);
}
indexOutOfBoundsException()
Custom exception thrown when subscript is out of bounds
private void indexOutOfBoundsException(int index){
throw new IndexOutOfBoundsException("index="+index+", size="+size);
}
Dynamic capacity expansion
The advantage of dynamic array over traditional array is that it can be dynamically expanded, but in fact, the bottom layer still uses array expansion. In essence, it uses new capacity array to fill the original data. This will involve many problems of bottom memory consumption and resource optimization. It will not be explained here, but mainly how to realize it.
Capacity expansion can only occur when adding elements, and it is the size of the dynamic array when adding elements, that is, when the number of elements just reaches the capacity, it should be expanded:
- Judge that the number of dynamic array elements has reached the array capacity, indicating that it is full and needs to be expanded
- The new array capacity is 1.5 times the current array capacity
- Creates an array with a new array capacity size
- The old array assigns values to the new array in turn
- The pointer to the old array points to the new array
public void add(int index,E element){
checkIndexAdd(index);
if (size == elements.length){ //If the size of the dynamic array has reached the array capacity (full)
int nowCapacity = elements.length; //The current dynamic array capacity is the array length
int newCapacity = nowCapacity + (nowCapacity >> 1); //Expand to 1.5 times the current capacity
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) { //The old array assigns values to the new array in turn
newElements[i] = elements[i];
}
elements = newElements; //The elements object points to newElements
System.out.println(nowCapacity + "Expansion to" + newCapacity);
}
for (int i = size; i > index ; i--) { //The elements move back in turn
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
We propose array expansion separately (to improve maintainability and readability)
private void ensureCapacity(){
if (size == elements.length){ //If the size of the dynamic array has reached the array capacity (full)
int nowCapacity = elements.length; //The current dynamic array capacity is the array length
int newCapacity = nowCapacity + (nowCapacity >> 1); //Expand to 1.5 times the current capacity
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) { //The old array assigns values to the new array in turn
newElements[i] = elements[i];
}
elements = newElements; //The elements object points to newElements
System.out.println(nowCapacity + "Expansion to" + newCapacity);
}
}
Comprehensive:
private void ensureCapacity(){
if (size == elements.length){ //If the size of the dynamic array has reached the array capacity (full)
int nowCapacity = elements.length; //The current dynamic array capacity is the array length
int newCapacity = nowCapacity + (nowCapacity >> 1); //Expand to 1.5 times the current capacity
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) { //The old array assigns values to the new array in turn
newElements[i] = elements[i];
}
elements = newElements; //The elements object points to newElements
System.out.println(nowCapacity + "Expansion to" + newCapacity);
}
}
public void add(int index,E element){
checkIndexAdd(index);
ensureCapacity();
for (int i = size; i > index ; i--) { //The elements move back in turn
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
summary
After solving the properties such as the size of the dynamic array, the array stored by the elements, and some basic addition, deletion, modification and query methods, as well as the processing of subscript out of bounds and the core dynamic expansion part, the most basic dynamic array ArrayList is roughly completed:
public class ArrayList<E> {
/**
* Dynamic array size
*/
private int size;
/**
* Dynamic array
*/
private E[] elements;
/**
* Dynamic array default capacity
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Parameterless construction, creating an array of default size
*/
public ArrayList(){
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* Parametric construction, create an array according to the capacity
* @param capacity Custom capacity
*/
public ArrayList(int capacity){
if (capacity<=0) capacity = DEFAULT_CAPACITY; //If the incoming capacity is not a natural number, it is forced to be the default capacity
elements = (E[]) new Object[capacity];
}
/**
* Dynamic array size
* @return Dynamic array size
*/
public int size(){
return size;
}
/**
* Is the dynamic array empty
* @return Is the dynamic array empty
*/
public Boolean isEmpty(){
return size == 0;
}
/**
* Error message of out of range after work
* @param index
*/
private void indexOutOfBoundsException(int index){
throw new IndexOutOfBoundsException("index="+index+", size="+size);
}
/**
* Check the index when adding elements
* @param index
*/
private void checkIndexForAdd(int index){
if (index<0||index>size) indexOutOfBoundsException(index);
}
/**
* index during check, deletion and modification
* @param index
*/
private void checkIndex(int index){
if (index<0||index>=size) indexOutOfBoundsException(index);
}
/**
* Ensure the capacity (if the dynamic array element size reaches the capacity of the current dynamic array, expand the capacity)
*/
private void ensureCapacity(){
if (size == elements.length){ //If the size of the dynamic array has reached the array capacity (full)
int nowCapacity = elements.length; //The current dynamic array capacity is the array length
int newCapacity = nowCapacity + (nowCapacity >> 1); //Expand to 1.5 times the current capacity
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) { //The old array assigns values to the new array in turn
newElements[i] = elements[i];
}
elements = newElements; //The elements object points to newElements
System.out.println(nowCapacity + "Expansion to" + newCapacity);
}
}
/**
* Add element
* @param element element
*/
public void add(E element){
add(size,element);
}
/**
*
* 0 1 2 3 4 5 6 7 8 9
* 1 2 3 4 5 6 7 8
* Adds an element to the specified location
* @param index position
* @param element element
*/
public void add(int index,E element){
if (element == null) throw new NullPointerException("Add not allowed null");
checkIndexForAdd(index);
ensureCapacity(); //Ensure array capacity (expand if full)
for (int i = size; i > index ; i--) { //The elements move back in turn
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
/**
*
* 0 1 2 3 4 5 6 7 8 9
* a b c 1 d e f g h
* Removes the element at the specified location
* @param index position
*/
public void remove(int index){
checkIndex(index);
for (int i = index; i < size-1 ; i++) { //Move the elements forward in turn
elements[i] = elements[i+1];
}
elements[size-1] = null; //Set the last element of the array to null
size--;
}
/**
* Deletes the specified element
* @param element element
*/
public void remove(E element){
remove(indexOf(element));
}
/**
* Empty elements in dynamic array
*/
public void clear(){
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* Modify the element at the specified location
* @param index position
* @param element element
*/
public void set(int index,E element){
checkIndex(index);
elements[index] = element;
}
/**
* Gets the element at the specified location
* @param index position
* @return element
*/
public E get(int index){
checkIndex(index);
return elements[index];
}
/**
* Determine whether the array contains the element
* @param element element
* @return true Contains, false does not contain
*/
public Boolean contains(E element){
return indexOf(element) >= 0;
}
/**
* The subscript of the first occurrence of the element
* @param element element
* @return subscript
*/
public int indexOf(E element){
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) return i; //Return subscript if element exists
}
return -1;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("ArrayList{");
string.append("size=" + size + ", elements=[");
for (int i = 0; i < size; i++) {
string.append(elements[i]);
if (i != size -1) { //Do not add a comma at the end of the last element
string.append(", ");
}
}
string.append("]");
string.append("}");
return string.toString();
}
}