Detailed explanation of list set

  list Gathering must be familiar to everyone , We also use a lot , But maybe people are using it , It's not true list The collection has a very detailed explanation , Today, I will take you to know in detail list aggregate .

Catalog

  One . The relationship between sets

  Two .List aggregate

3、 ... and .ArrayList aggregate  

for Circular deletion method 01

 for Circular deletion method 02

for Circular deletion method 03

foreach Delete method

Iterators delete 01

Iterators delete elements 02

list Collection deletion method

  Four .LinkedList aggregate

5、 ... and .Vector aggregate  

6、 ... and .CopyOnWriteArrayList aggregate  

---

  One . The relationship between sets

Below is a picture UML chart ,vector,ArrayList,LinkedList Inherit List, Today, I will explain the three collections in detail , The next article will give you more details Set aggregate .

  

---

  Two .List aggregate

  List Set features ：

        Element ordered , And repeatable .( Element order does not mean , We deposit Lits What in the set 1,3,7,6 He gave us from small to large , Or from big to small , The so-called order is that our set has a subscript , Subscript from 0 Start , Then we add it to... In what order list A collection of , Then he is in what order ). 

  

 List A collection of traverse ：

      According to the subscript ,foreach, Iterator traverses data .

 

 Lits Collective expansion ：

      Lits Set when we instance it , Its default initial capacity is 10, When to List The data added to the set exceeds 10 After , He will expand the capacity 0.5 times , After the expansion, it will be 15.

       New capacity = Original capacity + Original capacity * 0.5

 

   notes ：vector,ArrayList,LinkedList They are all inherited. List, So and Lits Set the above three points to be the same .

---

3、 ... and .ArrayList aggregate  

 ArrayList A collection is an inheritance List Of the set of , therefore Lits Some of the characteristics of sets ,ArrayList Also have .

 ArrayList Set characteristics ：

• Simple data structure , If the capacity is exceeded, it will be automatically expanded , Also and List The expansion of the set is the same .
• ArrayList Collection dynamic array , Why is it a dynamic array , Because how much data can an array hold , It is usually fixed , and ArrayList Arrays can be expanded according to data , So it's a dynamic array .
• The internal implementation is based on the underlying array of objects , That is to say ArrayList Collections hold objects .
• ArrayList Collections are not suitable for random deletion and addition .

   

  ArrayList Delete several delete

• for Circular deletion method 01

        There is a very fatal problem with this method , My judgment here is to delete as 3 The data of , Two of the sets are 3 Of , But only one was deleted 3, The result is zero [1, 2, 3, 4, 5, 6]

      Why not 2 individual 3 Delete all ？

      Because when deleting, you will , The original set data is [1,2,3,3,4,5,6], But before we delete 3 When , The assembly will immediately become [1,2,3,4,5,6] the second 3 The subscript of has moved online , and for The loop has reached the subscript 3 Of , And the first one 3 The second one was deleted at the moment 3 The subscript of is 3, But immediately the subscript is 2 了 , So that's why the result is [1, 2, 3, 4, 5, 6], So this method is very large bug There is , Because the data you want to delete is not deleted successfully .
 

package patterndemo02;

import java.util.ArrayList;
import java.util.List;

import org.junit.Before;
import org.junit.Test;


public class Test01 {
	 
	 private List<Integer> list=new ArrayList<Integer>();
	 /**
	  *  The first way to delete 
	  */
	
	 @Before
	 public void list() {
		
		 // Add data to the set 
		 list.add(1);
		 list.add(2);
		 list.add(3);
		 list.add(3);
		 list.add(4);
		 list.add(5);
		 list.add(6);
		 
	 }
	 
	 @Test
	 public void test01() {
		 for(int i=0;i<list.size();i++) {
			 // Judge that the value of the object found is 3 The deletion of 
			 if(list.get(i)==3) {
				 list.remove(i);
			 }
		 }
		 System.out.println(list);
	 }

}

    Get the results  

   

  

•  for Circular deletion method 02

        This approach will 3 All deleted , Because the first judgment is 3 To delete , however i-- It is characterized by , The first time will not be executed immediately i=i-1, Wait for the second execution i=i-1, So the first three... Are deleted normally in the first pass , Delete the second... The second time 3 So the result is [1,2,4,5,6]

       

package patterndemo02;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Before;
import org.junit.Test;


public class Test01 {
	 
	 private List<Integer> list=new ArrayList<Integer>();
	 /**
	  *  The first way to delete 
	  */
	
	 @Before
	 public void list() {
		
		 // Add data to the set 
		 list.add(1);
		 list.add(2);
		 list.add(3);
		 list.add(3);
		 list.add(4);
		 list.add(5);
		 list.add(6);
		 
	 }
	 

	 
	 @Test
	 public void test02() {
		 for(int i=0;i<list.size();i++) {
			 if(list.get(i)==3) {
				 list.remove(i--);
			 }
		 }
		 System.out.println(list);
	 }

}

  Get the results ：

    

  

• for Circular deletion method 03

    Let's look at this picture to better understand , The picture is a little ugly .

   

 

package patterndemo02;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Before;
import org.junit.Test;


public class Test01 {
	 
	 private List<Integer> list=new ArrayList<Integer>();
	 /**
	  *  The first way to delete 
	  */
	
	 @Before
	 public void list() {
		
		 // Add data to the set 
		 list.add(1);
		 list.add(2);
		 list.add(3);
		 list.add(3);
		 list.add(4);
		 list.add(5);
		 list.add(6);
		 
	 }
	 

	 @Test
	 public void test03() {
		 for(int i=list.size()-1;i>=0;i--){
			 if(list.get(i)==3){
			  list.remove(i);
			 }
			}
	 }
	 
	 

}

  The results of

 

 

    

• foreach Delete method

  

      This method is a very serious problem , Because of the wrong report , So don't use foreach Delete .

    

	 public void test04() {
		 for(Integer i:list){
			    if(i==3) list.remove(i);
			}
		 System.out.println(list);
	 }
	 

    This method has a very interesting place , That is, he can delete the penultimate element , No mistake. , Will be deleted successfully , This is also a small bug.

   

	 @Test
	 public void test04() {
		 for(Integer i:list){
			    if(i==3) {
			    	list.remove(5);
			    }
			}
		 System.out.println(list);
	 }

  

    Why use foreach Delete error report ？？？
    First foreach In essence, an iterator is created , Let's look at the source code first .

     

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}
		
		//1.
        public boolean hasNext() {
            return cursor != size;
        }

		//2.
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

		//3.
        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();
            }
        }
        
        //4.
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

      Pay attention to this method  

        

​
   //4.
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

​

 modCount： Number of changes  

When list transfer add When the method is used ,add The method will be right modCount Realization ++ operation , As in the above example , A total of add()4 Time ,
be modCount=4.
This value is assigned to the iterator's during the iterator initialization process expectedModCount,
Now ：modCount==expectedModCount==4.
 

When we are right list modify , be modCount+1, here ,modCount==5,

and expectedModCount Still 4,

because ：modCount != expectedModCount, So throw an exception ！
 

notes ：

So we use iterators to delete , Because the iterator can keep these two numbers the same , Using iterators does not appear like using foreach That's what happened .

 

• Iterators delete 01

      Use iterators to delete data from a collection , First, there will be no data to delete , Not deleted , Or delete more , Error reporting will not occur , The reason why using iterators does not report errors , Because the iterator can keep those two numbers equal , So it's not like foreach That happens .

   
	 @Test
	  public void test05() {
		  Iterator<Integer> it=list.iterator();
		  while(it.hasNext()) {
			  Integer vaule=it.next();
			  if(vaule==3) {
				  it.remove();
			  }
		  }
	  }

    The result ：[1, 2, 4, 5, 6] 

  

• Iterators delete elements 02

    The second way to use iterators , But this method is a whole leak , Will report an error directly .

    Why did you report an error ?

    The iterator actually copies an identical collection in another thread for traversal . When using a set of remove Method to delete an element , Iterators don't know , So an exception will be thrown . 

    

 @Test
	  public void test06() {
		 Iterator<Integer> it=list.iterator();
		 while(it.hasNext()){
		  Integer value=it.next();
		   if(value==3){
		   list.remove(value);
		  }
		}
		System.out.println(list);
		
	  }

• list Collection deletion method

    This statement is to delete the subscript 2 The elements of

list.remove(2);

      Delete the element as 2 Of

 

list.remove(Integer.valueOf(2));

  Four .LinkedList aggregate

•   and List Set usage is the same
•   Thread unsafe
• LinkedList Collections implement bidirectional Linked list Interface , Realize the linked list from head to tail element and the linked list from tail to head element , The goal is to increase the retrieval efficiency of elements  
• Suitable for random addition or deletion

5、 ... and .Vector aggregate  

• Thread safety
• Vector All methods in are thread synchronized , All carry synchronized keyword , So his Parallel performance is slow , Not recommended

Why is the performance slow ？

For example , For example, a toilet has three positions , A man went to the bathroom , He just closed the outermost door , He went to the bathroom alone , But he just needs a place , But he locked the gate , Others can only wait outside , As a result, he took a position himself , The other two are empty . That is to say Vector He'll lock it once he gets in , When the execution inside is completed , Before going to another . That is, a principle of synchronous lock .

6、 ... and .CopyOnWriteArrayList aggregate  

• Thread safety , comparison Veator Better performance
• Suitable for reading more , Write less scenes
• Reprint when writing
• Final consistency

    CopyOnWriteArrayList What do you mean by set writing time repetition and final consistency ？

   CopyOnWriteArrayList Set this set , I think it is very interesting , When we need to operate on this data , He will copy the data in the original set , Then, you can copy the elements in the past collection , This is the time of writing , When the modification is completed , This modified set will be given to the original array , This is the ultimate consistency .

 

  That's all for today's study ！！！ The next article brings you set A detailed explanation of the collection .