Directory
1. Concept
2. ArrayList collection frame diagram
3. Common methods of ArrayList
4. Implement ArrayList (Integer) by yourself
4.1 ArrayList construction
4.2 Expansion of ArrayList capacity
4.3 Judging whether it is empty or full
4.4 Whether the pos coordinates are legal (contained)
4.5 Adding and deleting elements of ArrayList
4.6 Containing elements
4.7 get and set
4.8 Get the coordinates of the first element
4.9 Print ArrayList
4.10 Empty ArrayList
1. Concept
ArrayList implements the List interface, which stores elements in a continuous storage block. Unlike arrays, ArrayList can grow dynamically by adding new elements at the end of the sequence. Sequence tables are generally stored in arrays, and data can be added, deleted, checked, and modified on the array, and its elements can be accessed and updated directly through the index of the element.
Note:
- ArrayList is a dynamic array.
- The ArrayList class is a generic collection whose elements are referenced by Object.
2. ArrayList collection framework diagram
Then:
- ArrayList is implemented generically and must be instantiated when used;
- ArrayList implements the RandomAccess interface, then ArrayList supports random access;
- ArrayList implements the Cloneabel interface, then ArrayList supports clone;
- ArrayList implements the Serialzable interface, then ArrayList supports serialization;
- Unlike Vector, ArrayList is not thread-safe, it can be used under single thread, and Vector or CopyOnWriteArrayList can be selected in multi-thread
3.ArrayList common methods
| Method | Explanation |
|---|---|
| add(E e) | Insert an element e |
| add(int index,E e) | Insert e at index position |
| remove(int index) |
Delete the element at index position |
| remove(Object o) |
delete the first encountered o |
| get(int index) | Get the element at the index position |
| set (int index,E e) | Update the element at index position to e |
| clear() | Empty ArrayList |
| indexOf(Object o) | Returns the subscript of the first o |
| lastIndexOf(Object o) | Return the subscript of the last o |
| subList(int fromIndex,int toIndex) | Intercept [fromIndex,toIndex ) element |
| contains(Object o) | Judge whether o |
4. Implement ArrayList (Integer) by yourself
4.1 ArrayList construction
public class MyArrayList {
int[] elem;//store element
public int usedSize = 0;//Number of elements, the size of the ArrayList collection is 0 by default
private static final int DEFAULT_SIZE = 10;//ArrayList collection capacity is 10 by default
//Construction method
public MyArrayList(){
this.elem = new int[DEFAULT_SIZE];
}
...
}
4.2 Capacity expansion of ArrayList
When the number of elements in the ArrayList is not less than the capacity, to expand the capacity is to clone the elements in the ArrayList to a larger array.
private void ensureCapacity() {
// clone the original array into a larger array
elem = Arrays.copyOf(elem,2*elem.length);
}
4.3 Judgment of fullness
Empty: the element is 0, that is, usedSize is 0;
Full: the number of elements is equal to the capacity
//empty
private boolean isEmpty() {
return usedSize == 0;
}
//Full
public boolean isFull() {
return usedSize == this.elem.length;
}
4.4 pos coordinates are legal (contained)
That is, pos>=0 & amp; & amp; pos < usedSize;
//Is it legal
public boolean checkPosInAdd(int pos) {
return pos >= 0 & amp; & amp; pos < usedSize;//legal
}
4.5 Add and delete elements of ArrayList
When inserting elements at the end, it is necessary to judge whether there is enough capacity. If not, it is necessary to expand the capacity, that is, call the ensureCapacity() method in 4.2.
When inserting an element at a specific position, it is necessary to determine whether the coordinates are legal and cannot be greater than the size of the array. If it is greater than the size of the array, an exception is thrown.
When deleting an element, it is necessary to determine whether the coordinates are legal and cannot be larger than the size of the array. If it is larger, an exception is thrown, and it is also necessary to determine whether the element exists. If not, return -1.
// Add elements, by default, add at the end of the array
public void add(int data) {
if(isFull()){
ensureCapacity();
}
this.elem[usedSize] = data;
usedSize++;
}
// add element at position pos
public void add(int pos, int data) {
if(!checkPosInAdd(pos)){
throw new ArrayIndexOutOfBoundsException("Array out of bounds");
}else{
this.elem[pos] = data;
usedSize++;
}
}
//Delete the first encountered key
public void remove(int key) {
if(isEmpty()){
return;
}
int index = indexOf(key);
if(index == -1){
return;
}
for (int i = index; i < usedSize - 1; i ++ ) {
elem[i] = elem[i + 1];
}
usedSize--;
}
//Delete the element at index coordinates
public void removeIndex(int index){
if(!checkPosInAdd(index)){
throw new ArrayIndexOutOfBoundsException("Illegal");
}else{
for (int i = index; i < usedSize; i ++ ) {
elem[i] = elem[i + 1];
}
usedSize--;
}
}
4.6 Containing elements
That is, traverse the entire array to see if it contains this element;
// Determine whether an element is contained
public boolean contains(int toFind) {
for (int i :
this.elem) {
if (i == toFind){
return true;
}
}
return false;
}
4.7 get and set
You can directly return and update the value according to the index, but you need to pay attention to the legality; if it is not legal, an exception will be thrown;
// Get the element at position pos
public int get(int pos) {
if(!checkPosInAdd(pos)){
throw new ArrayIndexOutOfBoundsException("Array out of bounds");
}else{
return elem[pos];
}
}
// Set the element at position pos to [Update to] value
public void set(int pos, int value) {
if(!checkPosInAdd(pos)){
throw new ArrayIndexOutOfBoundsException("out of bounds");
} else {
elem[usedSize] = value;
usedSize++;
}
}
4.8 Get the coordinates of the first element
Traverse the array directly, and return the coordinates of the element encountered for the first time, without returning -1;
// Find the position corresponding to an element
public int indexOf(int toFind) {
for(int i = 0; i < usedSize; i ++ ){
if(elem[i] == toFind){
return i;
}
}
return -1;
}
4.9 Print ArrayList
You can directly traverse the entire array and print it;
public void display() {
for (int i = 0; i < usedSize; i ++ ) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
4.10 Clear ArrayList
Just change the usedSize size to 0 directly;
// Clear the sequence table
public void clear() {
usedSize = 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treeHome pageOverview 47467 people are studying systematically