1, List interface

1. General

• Inherits the Collection interface, which is a Collection of elements

For example, the order of storing elements is 11, 22, 33. Then, the storage of elements in the set is completed in the order of 11, 22 and 33)

• It is a set with index ， through which the elements in the set can be operated accurately (the same reason as the index of array)

• Unlike ， set ， List ， can have duplicate elements. Use the ， equals ， method of the element to compare whether it is a duplicate element

• The common implementation classes of the List interface are:

• ArrayList collection

• LinkedList collection

2. Abstract methods in the list interface (unique)

• add(int index, Object e): adds the specified element to the specified index of the collection, and the original elements are moved back in turn
• remove(int index): deletes the element at the specified index from the collection, and the return value is the deleted element
• set(int index,E element): replace the element at the specified index with the specified element, and the return value is the element before replacement
• get(int index): gets the element at the specified index and returns it

3. List traversal

List<Person> a = new LinkedList<>();
a.add(new Person("zs",10));
a.add(new Person("lisi",20));
a.add(new Person("wangwu",30));

//Iterator is used to traverse the List
Iterator<Person> iterator = a.iterator();

//Iterator object traversal
while(listItr.hasNext()) {
    System.out.println(listItr.next());
}

//List unique traversal mode
for (int i = 0; i < a.size(); i++) {
    System.out.println(a.get(i));
}

2, ListIterator interface

1. General

• List # not only has its own unique iteration method, but also has its own unique iterator: ListIterator

2. Abstract method of listiterator interface

• add(E, e): inserts the specified element into the list
• boolean hasPrevious(): traverses the list inversely. If the list iterator has multiple elements, it returns {true, that is, to judge whether there is a previous element
• previous(): returns the previous element of the list

3. List reverse traversal:

Iterator<Person> iterator = a.iterator();
ListIterator<Person> listItr = a.listIterator(a.size());
//Traverse in sequence first and let the cursor reach the end
while(listItr.hasNext()) {
    System.out.println(listItr.next());
}
//Backward Traversal 
//Move previous forward one position before accessing the element pointed to by cursor
while(listItr.hasPrevious()) {
    System.out.println(listItr.previous());
}

3, Concurrent modification exception of iterator

1. Concurrent modification exception of iterator

java.util.ConcurrentModificationException

• In the process of traversal, the set method is used to modify the length of the {set

2. Scenario:

First, modify the set in the process of traversing the set; Secondly, modify the Collection behavior, not the iterator object, but directly modify the Collection object

//Scene implementation
List<String> list = new ArrayList<String>();
list.add("abc1");
list.add("abc2");
list.add("abc3");
list.add("abc4");

//The iterator is used to obtain the collection. When obtaining, judge whether there is an "abc3" object in the collection
//If so, add an element "ABC3"
Iterator<String> it = list.iterator();
while(it.hasNext()){
    String s = it.next();
    //Judge whether the extracted element s has "abc3"
    if(s.equals("abc3")){
        list.add("ABC3");
    }
    System.out.println(s);
}

3. Reasons:

In the iterative process, the set method is used to operate the elements. As a result, the iterator does not know the changes in the set, which is easy to cause data uncertainty. Iterator objects are generated by relying on the current data set (in other words, iterators depend on the data set, and they must correspond)

public class ListDemo{
    public static void main(String[] args) {
       List<Person> a = new LinkedList<>();
       //iterator 
       ListIterator<Person> listItr = a.listIterator();

        a.add(new Person("zs",10));
        a.add(new Person("lisi",20));
        a.add(new Person("wangwu",30));

        while(listItr.hasNext()){
            Person p = listItr.next();
            //This way of adding elements will produce exceptions
            //a.add(new Person("zhaoliu", 40));

            //Solution: use ListIterator object to add elements
            listItr.add(new Person("zhaoliu", 40));
        }
    }
    System.out.println(s);

    //For List, there is another solution to modify the collection while traversing the collection
    for (int i = 0; i < a.size(); i++){
        if("lisi".equals(a.get(i).name)){
            a.add(new Person("zhaoliu", 40));
        }
    }
    System.out.println(a);
    //If you use the add method of ListIterator to add an element to the collection, the position of the element is after the currently traversed element
    //If you add an element using the add(e) method of the collection object, the inserted element is at the end of the table
}

4, ArrayList, LinkedList sets

1. ArrayList set

• The bottom layer adopts the {array structure, which is unsafe for threads, fast query and slow addition and deletion

//An Object type array with length 0 was created
ArrayList al=new ArrayList();
al.add("abc");
//Essence:
//The bottom layer will create an Object array with a length of 10 Object[] obj=new Object[10]
//obj[0]="abc"
//If more than 10 elements are added, the bottom layer will open up a new array with a length of 1.5 * 10
//Copy the elements in the original array to the new array, and then add the last element to the new array

2. LinkedList set

• The bottom layer adopts the {linked list} structure, which is thread unsafe, slow query, fast addition and deletion
• Each query should start from the head or tail of the chain. The query is relatively slow compared with the array, but delete and directly modify the address value of the element record. Do not move a large number of elements
• The index of the LinkedList determines whether to start from the head or the tail. If the element is less than half the length of the element, start from the head. If it is greater than half the length of the element, start from the tail
• LinkedList provides a large number of methods to start and end operations
• Special functions of subclasses: cannot be called polymorphically:

addFirst(E) is added to the beginning of the linked list
addLast(E) is added to the end of the linked list
E getFirst() gets the beginning of the linked list
E getLast() gets the end of the linked list
E removeFirst() removes and returns the beginning of the linked list
E removeLast() removes and returns the end of the linked list

3. Vector set (basically not used)

• The structure of Vector collection data storage is an array structure. It is the earliest collection provided in JDK. It is thread synchronous and thread safe
• The Vector collection has been replaced by ArrayList

5, Set interface

1. Features

• It is a collection with no duplicate elements and no index

• Is a collection that does not contain duplicate elements

• Unordered collection, no index, no duplicate elements stored

• Set out of order: the order of storage and retrieval is different,

• The methods of extracting elements from the Set can be iterator and enhanced for

• The code is completely consistent with ArrayList

• Set collection common implementation classes:

• HashSet collection

• LinkedHashSet collection

6, HashSet (hash table)

1. Features:

• The underlying data structure is a} hash table
• Fast storage and retrieval
• Thread is unsafe and runs fast
• The iterative order of set is not guaranteed
• The permanence of this sequence is not guaranteed

2. Data structure of hash table:

• Load factor: the number of records filled in the table / the length of the hash table
  For example, a loading factor of 0.75 represents 16 positions in the array, in which 16 * 0.75 = 12 elements are stored.
• If the thirteenth (> 12) element is stored, resulting in a long storage chain, which will reduce the performance of the hash table, the hash table will be expanded (re hashed), and an array with a length twice the original length will be opened at the bottom. Copy the old element to the new array, and then add the new element to the array.  
  When {number of stored elements > hash table len gt h * loading factor, the capacity needs to be expanded, so the loading factor determines the capacity expansion time

3. Hash value of string object:

• The hash value of the Object is an ordinary decimal integer. It is calculated by the method of Object class {public int hashCode(), and the calculation result is an integer of {int}
• The String class rewrites the hashCode() method. See the source code

4. Stored procedure of hash table

Access principle:
For each new element, the following three steps should be taken:
1. First, call the {hashCode() method of this class to calculate the hash value
2. Find out whether the old element with the same hash value as the new element is stored in the container. If not, go to step 3
3. The new element will be compared with the old element under the index position one by one by using the {equals method Equals (old element), return  true, stop the comparison, explain the duplication and no longer store it. If it is compared with the old elements under the index position through the  equals  method, return  false, indicate that there is no duplication and store it

Stored procedure for hash table

Find out whether the old element with the same hash value as the new element is stored in the container. If not, go to step 3

3. The new element will be compared with the old element under the index position one by one by using the {equals method Equals (old element), return  true, stop the comparison, explain the duplication and no longer store it. If it is compared with the old elements under the index position through the  equals  method, return  false, indicate that there is no duplication and store it

[external chain picture transferring... (img-q04mwuo3-162840832162)]

Stored procedure for hash table