ArrayList analysis 3 : Remove elements
Reprint please indicate the source ：https://www.cnblogs.com/funnyzpc/p/16421743.html
Deleting elements is a common requirement for collection classes , Very common ; If it is the usual deletion method, there is no need to write this blog , This blog not only analyzes the problems that may be caused by deletion , We will also analyze why we need to borrow iterators to delete from the source code level , At the same time, the deletion methods under different business forms will also be given , Look down if you are interested 🥸
One . Circular and acyclic delete
These are two different business forms , If the index position or element value of the element to be deleted is determined and only one element is deleted , It is usually called directly ArrayList Under the remove Delete method , But that's not the point of this article
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
System.out.println(arr);
arr.remove("c");// remove c
arr.remove(3);// remove d
System.out.println(arr);
}
Another case is to delete multiple elements , Generally, the index position of the element to be deleted cannot be determined , So you need to delete it in the loop ;
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
for(int i=0;i<arr.size();i++){
if("d".equals(arr.get(i))){
arr.remove("d");
}
}
System.out.println(arr);
}
Two . Incorrect usage of deletion
( Wrong usage 1 )
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
for(Object item:arr){
if("d".equals(item)){
arr.remove(item);
}
}
}
( Wrong usage 2 )
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
arr.forEach(item->{
if("d".equals(item)){
arr.remove("d");
}
});
}
Although all are deleted , But the simplified version for Loops and functional loops cannot be deleted ？ To look down ...
3、 ... and . What does ordinary deletion do
This is a ArrayList Of remove Source code ：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work Clearly let GC Do its job （ That is to shrink one position and set it to null, Cutting off the reference will naturally be gc fall ）
return oldValue;
}
This is an iterator remove Source code ：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
about ArrayList Of remove, In fact, the important point is --size , And for iterators remove Not just calling ArrayList The deletion of also needs to update the cursor (cursor) And the current element index location (lastRet), Then the inspiration came , Is it right? Simplified edition for loop as well as Functional expression forEach loop Under the size Turned into constant What about it ？ Yes , In fact, that's how it works , It would be easy to understand if I changed the circular deletion logic to this ：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
for(int i=0;i<6;i++){
if( i==(arr.size()-1) ){
break;
}
if(arr.get(i).equals("d")){
arr.remove(i);
}
}
System.out.println(arr);
}
So every time you enter the loop, you should check the array size Is there a change , Or cross the border , So no matter which way you delete it, you should get Abreast of the times size In this way, it can be safely deleted
Four . Delete logic under different requirements
If you need to ensure complete safe deletion , It is recommended that you use iterators iterator or listIterator：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
Iterator itr = arr.iterator();
while(itr.hasNext()){
Object item = itr.next();
if("d".equals(item)){
itr.remove();
}
}
System.out.println(arr);
}
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
ListIterator itr = arr.listIterator();
while(itr.hasNext()){
Object item = itr.next();
if("d".equals(item)){
itr.remove();
}
}
System.out.println(arr);
}
If you need to get the index of the current iteration element in the iterator or
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
ListIterator lst_itr = arr.listIterator();
while(lst_itr.hasNext()){
int idx = lst_itr.nextIndex();
Object item = lst_itr.next();
System.out.println(idx+"->"+item);
if("d".equals(item)){
lst_itr.remove();
}
}
System.out.println(arr);
}
Of course , If you want to use iterators and get the index position of the current loop element , Want to get the original array again ( Not deleted before ) Index position of , You can try this ：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
int i = 0;
for(ListIterator lst_itr = arr.listIterator();lst_itr.hasNext();i++){
int idx = lst_itr.nextIndex();
Object item = lst_itr.next();
System.out.println(i+" -> "+idx+":"+item);
if("d".equals(item)){
lst_itr.remove();
}
}
System.out.println(arr);
}
5、 ... and . Simplified deletion
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
arr.add("e");
arr.add("d");
System.out.println(arr);
arr.removeIf(item->"d".equals(item));
System.out.println(arr);
}
Simplify the deletion method internal source code ：
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
// Move the remaining elements to the space left by the removed elements , That is, array slimming
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
ha-ha , Is it super complex , Not only internal maintenance removeCount It also needs to be Maintenance version , At the same time, the position of elements also adopts a special way Move , In this way, the efficiency seems not so high , So the seemingly simple usage is not simple at all ...
