Chapter 12 collection (ArrayList LinkedList generic)

Tip: Here you can add the general contents to be recorded in this article:
For example, with the continuous development of artificial intelligence, machine learning technology is becoming more and more important. Many people have started learning machine learning. This paper introduces the basic content of machine learning.

Tip: the following is the main content of this article. The following cases can be used for reference

12.1 array objects

Arrays are containers that can store basic data types or reference data classes. Arrays that store reference data types are called object arrays, such as String [], Person [], Student [].

public static void main(String[] args)
{ 
	//Create an array that stores the Person object 
	Person[] persons = { 
	new Person("Zhang San",20), 
	new Person("Li Si",21), 
	new Person("Wang Wu",22), };
	//Traversal array 
	for(int i = 0 ; i < persons.length; i++){ 
	Person person = persons[i]; 
	System.out.println(person.getName()+"::"+person.getAge());
	}
}

Disadvantages of array
- The length of the array is fixed and cannot be modified once it is created.
- If you need to add elements, you can only create a new array and copy the elements in the original array.
In order to solve the problem of fixed array length, the Java language starts from jdk1 2 the collection frame begins to appear.

12.2 Collection

12.2.1 general

Collection: a collection is a container provided in java that can be used to store multiple data.

Since both sets and arrays are containers, what is the difference between them?

The length of the array is fixed. The length of the collection is variable.
The elements of the same type are stored in the array, and any type of data can be stored. Collections store reference data types. If you want to store basic type data, you need to store the corresponding packaging type.

12.2.2 inheritance system of set classes

Collection: the root interface of a single column collection class. It is used to store a series of elements that conform to certain rules. It has two important sub interfaces, namely Java util. List and Java util. Set . Among them, list is characterized by ordered elements and repeatable elements. Set is characterized by non repeatable elements. The main implementation classes of the list interface are Java util. ArrayList and Java util. The main implementation classes of LinkedList and set interfaces are Java util. HashSet and Java util. LinkedHashSet .

Note: this figure is only our common sets. These sets do not mean that there are only these sets.

The Collection itself is a tool, which is stored in Java Util package. The Collection interface defines the most common content in the single column Collection framework.

12.2.3 Collection interface method

Collection is the parent interface of all single column collections. Therefore, some common methods for single column collections (List and Set) are defined in collection, which can be used to operate all single column collections. The method is as follows:

public boolean add (E) adds the given object to the current collection.
Public Boolean addall (collection <? Extensions E >) adds another collection element to the current collection.
public void clear(): clear all elements in the collection.
Public Boolean remove (E): deletes the given object from the current collection.
public boolean contains(Object obj): determines whether the current collection contains a given object.
public boolean isEmpty(): judge whether the current collection is empty.
public int size(): returns the number of elements in the collection.
public Object[] toArray(): store the elements in the collection into an array.

12.3 iterators

12.3.1 Iterator interface

In program development, it is often necessary to traverse all elements in the collection. To meet this requirement, JDK provides an interface java util. Iterator .
To traverse the Collection, you need to obtain the Collection iterator to complete the iterative operation. The following describes the method of obtaining the iterator:

public Iterator iterator(): get the iterator corresponding to the collection and use it to traverse the elements in the collection.

Here is the concept of iteration:

Iteration: that is, the general acquisition method of Collection elements. Before taking elements, first judge whether there are elements in the set. If there are, take out this element and continue to judge. If there are any, take it out again. Always take out all the elements in the Collection. This extraction method is called iteration in technical terms.

The common methods of Iterator interface are as follows:

public E next(): returns the next element of the iteration.
public boolean hasNext(): returns true if there are still elements that can be iterated.

Next, let's learn how to use the Iterator to iterate over the elements in the collection through a case:

public static void main(String[] args) { 
	// Create objects using polymorphism 
	Collection<String> coll = new ArrayList<String>(); 
	// Add element to collection 
	coll.add("String of stars"); 
	coll.add("love remains"); 
	coll.add("dog"); 
	//ergodic 
	//Each collection object has its own iterator 
	Iterator<String> it = coll.iterator(); 
	// Generics are the data types that iterate over the elements 
	while(it.hasNext()){ 
	//Determine whether there are iterative elements 
	String s = it.next();//Gets the iterated element 
	System.out.println(s);
	}
	}

12.3.2 implementation principle of iterator

In the previous case, we have completed the whole process of Iterator traversing the collection. When traversing the collection, first obtain the Iterator object by calling the iterator() method of the t collection, and then use the hashNext() method to judge whether there is the next element in the collection. If so, call the next() method to take out the element. Otherwise, it indicates that the end of the collection has been reached, and stop traversing the element.

When the Iterator iterator object traverses the set, it internally uses a pointer to track the elements in the set. In order to enable beginners to better understand the working principle of the Iterator, next, a legend is used to demonstrate the iterative process of the Iterator object:

Before calling the next method of the Iterator, the index of the Iterator is located before the first element and does not point to any element. After calling the next method of the Iterator for the first time, the index of the Iterator will move backward one bit, point to the first element and return the element. When calling the next method again, the index of the Iterator will
The index will point to the second element and return it, and so on until the hasNext method returns false, indicating that the end of the collection is reached and the traversal of the element is terminated.

12.3.3 concurrent modification exception

When traversing a collection with an iterator, you cannot use the method of the collection itself to change the length of the collection. Once it is changed, a concurrent modificationexception will be thrown.

public static void main(String[] args){ 
	Collection<String> coll = new ArrayList<String>(); 
	coll.add("hello1"); 
	coll.add("hello2"); 
	coll.add("hello3"); 
	coll.add("hello4"); 
	Iterator<String> it = coll.iterator(); 
	while (it.hasNext()){ 
	String str = it.next(); 
	if("hello2".equals(str))
	{ 
	coll.add("hello5");
	}
}

The above program uses the set add method to modify the length of the set during iterator traversal. This operation is not allowed and prohibited. Concurrent modification exceptions will be thrown in the program.

Note: if we use the remove() method of the collection, we will also throw a concurrent modification exception, but deleting the penultimate element will not throw an exception.
Reason: the method that throws the concurrent modification exception is the next() method of the iterator. When the penultimate element is deleted, the loop ends. When the while loop is executed again, the condition is false, the loop stops, and the next() method is not executed, so no exception is thrown.

12.4 enhanced for loop

12.4.1 general

java.lang.Iterable interface. Implementing this interface allows objects to be the target of "foreach" statements. That is, all sub interfaces and implementation classes under the Iterable interface can use the "foreach" statement. A sub interface of the Iterbale interface is the Collection interface, and all the collections we learn are
You can use the "foreach" statement, which also includes arrays.

12.4.2 format

for(Data type variable of element : Collection aggregate or array){ //Write operation code}

Note: it is used to traverse collections and arrays. Generally, only elements are traversed, and CRUD operations on Collection elements cannot be performed during traversal.

12.4.3 traversing arrays and sets

public static void main(String[] args) { 
	int[] arr = {3,5,6,87}; 
	//Using enhanced for traversal arrays 
	for(int a : arr){
	//a represents each element in the array 
	System.out.println(a); 
	}
	Collection<String> coll = new ArrayList<String>(); 
	coll.add("River god"); 
	coll.add("Old river god"); 
	coll.add("God woman"); 
	for(String s :coll){ System.out.println(s); 
	} 
}

12.4.4 enhanced for loop principle

Enhance for to traverse the array collection. After decompiling the class file, it is a traditional form of for loop
Enhance the for traversal collection, and the class file is the iterator after decompilation

12.5 data structure

12.5.1 introduction to data structure

Data structure: how data is stored in memory.

12.5.2 common data structures

The common structures of data storage are stack, queue, array, linked list and red black tree. Let's take a look at:

Stack

Stack: stack, also known as stack, is a linear table with limited operation. Its limitation is that it is only allowed to insert and delete at one end of the target, and it is not allowed to add, find, delete and other operations at any other location.

To put it simply: the set with this structure has the following characteristics for accessing elements

First in and last out (that is, for the elements stored in, the elements behind them can be taken out only after they are taken out in turn). For example, when the bullet is pressed into the magazine, the bullet pressed in first is below, and then the bullet pressed in is above. When shooting, first eject the bullet above, and then eject the bullet below.
The top and exit of the stack are the same.

Here are two nouns to note

Stack pressing: is to store elements. That is, the elements are stored at the top of the stack, and the existing elements in the stack move one position to the bottom of the stack in turn.
Spring stack: that is, take elements. That is, take out the top position elements of the stack, and the existing elements in the stack move one position to the top of the stack in turn.

queue

Queue: queue, referred to as queue for short, is a linear table with limited operation like stack. Its limitation is that it is only allowed to insert at one end of the table and delete at the other end of the table.

In short, the set with this structure has the following characteristics for accessing elements

First in, first out (that is, the stored element can be taken out only after the elements in front of it are taken out in turn). For example, when a small train passes through a cave, the front goes first and the rear goes in; The front comes out first and the rear comes out later.
The entrance and exit of the queue occupy one side respectively. For example, in the following figure, the left side is the entrance and the right side is the exit

array

Array: array is an ordered sequence of elements. Array opens up a continuous space in memory and stores elements in this space. Like a row of rental houses, there are 100 rooms, from 001 to 100, and each room has a fixed number. Through the number, you can quickly find the renter.

In short, the set with this structure has the following characteristics for accessing elements:

Find elements: through the index, you can quickly access the elements at the specified location.
Adding and deleting elements is slow
- Add elements at the specified index position: you need to create a new array, store the specified new elements at the specified index position, and then copy the original array elements to the corresponding index position of the new array according to the index.

Linked list

Linked list: linked list is composed of a series of nodes (each element in the linked list is called a node). Nodes can be generated i dynamically at runtime. Each node consists of two parts: one is the data field that stores the data element, and the other is the pointer field that stores the address of the next node. We often say that the linked list structure includes one-way linked list and two-way linked list. Here we introduce one-way linked list.
In short, the set with this structure has the following characteristics for accessing elements:
- Multiple nodes are connected by address. For example, many people hold hands. Each person uses his right hand to hold the next person's left hand, and so on, so that many people are connected together.
- Slow to find elements: to find an element, you need to find the specified elements backward through the connected nodes
- Add and delete elements quickly

12.6 List set

java.util.List interface, inheriting the collection interface, and an ordered collection (also known as a sequence). Users of this interface can precisely control the insertion position of each element in the list. Users can access an element based on its integer index (position in the list) and search for elements in the list. Unlike the Set interface, the list interface usually allows duplicate elements.

12.6.1 List interface features

The List set is an ordered set, and the order of storage and retrieval is the same.
The List collection allows you to store duplicate elements.
Each element in the List collection has an index.

Tip: when the collection class name is suffixed, List, such as ArraysList and LinkedList, are the implementation classes of the List interface and have the characteristics of the List interface.

12.6.2 List interface specific method (with index)

public void add(int index,E element) inserts an element at the specified position in the list.
public E get(int index) returns the element at the specified position in the list.
public E set(int index,E element) replaces the element at the specified position in the list with the specified element, and returns the element before replacement.
public E remove(int index) removes the element at the specified position in the list and returns the element before it is removed.

12.7 ArraysList set

12.7.1 general

java. util. The structure of the ArrayList collection data store is an array structure. Slow addition and deletion of elements, fast search, unsafe thread and fast running speed. Because the most frequently used functions in daily development are querying data and traversing data, ArrayList is the most commonly used collection.

Many programmers use ArrayList very casually to complete any requirements during development, which is not rigorous. This usage is not advocated.

12.7.2 ArrayList source code analysis

The bottom layer is the Object object array, the data type stored in the array is Object, and the array name is elementData. (it can be analyzed that ArrayList is a collection of array structures)

transient Object[] elementData;

12.8 LinkedList set

12.8.1 general

java. util. The structure of LinkedList set data storage is linked list structure. A collection that facilitates the addition and deletion of elements.
Collection features: fast element addition and deletion, slow search, unsafe thread and fast running speed.
LinkedList is a two-way linked list. What does a two-way linked list look like? Let's use a figure to understand:

12.8.2 LinkedList set specific methods

In the actual development, the addition and deletion of a collection element often involves head and tail operations, and LinkedList provides a large number of methods of head and tail operations. We can understand these methods as

Public void addfirst (E): inserts the specified element at the beginning of this list.
Public void addlast (E): adds the specified element to the end of this list.
public E getFirst(): returns the first element of this list.
public E getLast(): returns the last element of this list.
public E removeFirst(): removes and returns the first element of this list.
public E removeLast(): removes and returns the last element of this list.
public E pop(): pop an element from the stack represented by this list.
public void push(E e): pushes elements into the stack represented by this list.
public boolean isEmpty(): returns true if the list does not contain elements.

LinkedList is a subclass of List. The methods LinkedList in List can be used. We won't introduce them in detail here. We just need to understand the unique methods of LinkedList. During development, the LinkedList collection can also be used as a stack and queue structure.

12.8.3 LinkedList source code analysis

LinkedList member variable analysis:

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, 
Cloneable, java.io.Serializable{ 
	transient int size = 0; 
	transient Node<E> first; 
	transient Node<E> last; 
	}

Resolution: the member variable size is the length, which records the number of storage elements in the collection. first and last represent the beginning and end elements of the linked list respectively, so the linked list can easily operate the beginning and end elements.

LinkedList internal class Node class analysis: (it can be analyzed that LinkedList is a double linked list set)

private static class Node<E> { 
	E item; 
	Node<E> next; 
	Node<E> prev; 
	Node(Node<E> prev, E element, Node<E> next) { 
	this.item = element; 
	this.next = next; 
	this.prev = prev; 
	} 
	}

Resolution: the internal class Node in the LinkedList collection represents the Node object in the linked list. The Node class has three member variables:

item: stored object.
Next: next node.
prev: previous node.

From the source code of Node class, it can be analyzed that LinkedList is a two-way linked list, an object that records the previous Node and the next Node.

12.9 generics

12.9.1 general

When we learned about the collection, we all know that any Object can be stored in the collection. As long as the objects are stored in the collection, they will be promoted to Object type. When we take out each Object and perform corresponding operations, we must use type conversion.
Look at the following code:

public static void main(String[] args) { 
Collection coll = new ArrayList(); 
coll.add("hello"); 
coll.add("kaikeba"); 
coll.add(5);//Because there is no restriction on the collection, any type can be stored in it 
Iterator it = coll.iterator(); 
while(it.hasNext()){ 
//To print the length of each String, you need to convert the iterated object into String type 
String str = (String) it.next(); System.out.println(str.length()); 
} 
}

A problem occurred while the program was running lang.ClassCastException. Why do type conversion exceptions occur? Let's analyze: because any type of element in the Collection can be stored. Causes a runtime ClassCastException to be thrown when fetching. How to solve this problem? Although a Collection can store various objects, in fact, a Collection usually stores only objects of the same type. For example, they are all stored string objects. Therefore, after JDK5, generic syntax is added, so that you can specify classes or methods to support generics when designing the API. In this way, when we use the API, it becomes more concise and gets syntax check at compile time.

Generics: unknown types can be used in advance in classes or methods.

Note: in general, unknown types are used to determine specific types when creating objects. When no generic type is specified, the default class is Object type.

12.9.2 benefits of using generics

What are the benefits of generics?

When the ClassCastException of the runtime is transferred to the compilation time, it becomes a compilation failure.
Avoid the trouble of type forced conversion.

Let's experience it through the following code:

public static void main(String[] args) { 
	Collection<String> list = new ArrayList<String>(); 
	list.add("hello"); 
	list.add("iojij"); 
	// list.add(5);// When the collection has an explicit type, an error will be reported if the storage types are inconsistent 
	// If the collection has specified the specific element type, the iterator will also know the specific traversal element type when using the iterator 
	Iterator<String> it = list.iterator(); 
	while(it.hasNext()){ 
	String str = it.next(); 
	//When you use iterator < String > to control the element type, you don't need to force conversion. The obtained element is directly of String type 
	System.out.println(str.length()); 
} 
}

12.9.3 definition and use of generics

We will make a lot of use of generics in the collection. Here we can learn about generics completely. Generics are used to flexibly apply data types to different classes, methods and interfaces. Pass the data type as a parameter.

Define and use classes that contain generics

Define format:

Modifier  class Class name<Variables representing generics> { }

For example, the ArrayList collection in the API:

Generics are not specific when defined, but become specific when used. Determine the specific data type of the generic when using it.

class ArrayList<E>{ 
	public boolean add(E e){ } 
	public E get(int index){ } 
	.... 
	}

Use generics: that is, when generics are determined.
Determine generics when creating objects
For example, ArrayList = new arraylist();
At this time, the value of variable E is of String type, so our type can be understood as:

class ArrayList<String>{ 
public boolean add(String e){ } 
public String get(int index){ } 
... 
}

For another example, ArrayList = new arraylist();
At this time, the value of variable E is Integer type, so our type can be understood as:

class ArraysList<Integer> { 
	public boolean add(Integer e) { } 
	public Integer get(int index) { } 
	... 
	}

Methods with generics

Define format:

Modifier  <Variables representing generics> Return value type method name(parameter){ }

For example:

public class MyGenericMethod { 
	public <MVP> void show(MVP mvp) { 
	System.out.println(mvp.getClass()); }
public <MVP> MVP show2(MVP mvp) { 
	return mvp; 
	} 
	}

When a method is called, the type of the generic type is determined

public static void main(String[] args) { 
	// create object 
	MyGenericMethod mm = new MyGenericMethod(); 
	// Presentation method tips 
	mm.show("aaa"); 
	mm.show(123); 
	mm.show(12.45); 
	}

Interface with generics

Define format:

public interface MyGenericInterface<E>{ 
public abstract void add(E e); 
public abstract E getE();
}

Use format:
1. Determine the type of generic when defining a class
for example

public class MyImp1 implements MyGenericInterface<String> { 			

	@Override 
	public void add(String e) { // Omit...}
	@Override 
	public String getE() { return null; } 
	}

At this point, the value of generic E is of type String.
2. The type of a generic is always uncertain until the type of the generic is determined when the object is created
for example

public class MyImp2<E> implements MyGenericInterface<E> { 
	@Override 
	public void add(E e) { // Omit...}
	@Override 
	public E getE() { return null; } 
	}

Determine generics:

public static void main(String[] args) { 
MyImp2<String> my = new MyImp2<String>(); 
my.add("aa"); 
}

12.9.4 generic wildcards

When a generic class or interface is used, the generic type in the passed data is uncertain. You can use the wildcard <? > express. However, once the generic wildcard is used, only the common methods in the Object class can be used, and the methods of the elements in the collection cannot be used.

Basic use of wildcards

Generic wildcard: when you don't know what type to use to receive, you can use?,? Indicates an unknown wildcard.
At this time, only data can be accepted, and data cannot be stored in the collection.
For example, you can understand and use it:

public static void main(String[] args) { 
	Collection<Intger> list1 = new ArrayList<Integer>(); 
	getElement(list1); 
	Collection<String> list2 = new ArrayList<String>(); 
	getElement(list2); 
	}
//? Is a wildcard and can receive any type 
public static void getElement(Collection<?> coll){ 
	Iterator<?> it = coll.iterator(); 
	while(it.hasNext()){ System.out.println(it.next()); } 
	}

Note: there is no inheritance relationship for generic types. Collection list = new ArrayList(); This is wrong.

Advanced use of wildcards -- restricted generics

When you set generics before, you can actually set them arbitrarily, as long as they are classes. However, the upper and lower limits of a generic can be specified in JAVA generics.
Upper limit of generics:

Format: type name <? Extensions class > object name
Meaning: only this type and its subclasses can be accepted

Lower bound of generics:

Format: type name <? Super class > object name
Meaning: only this type and its parent type can be accepted

12.9.5 generic qualification cases

Requirements: create teacher class and head teacher class, provide name and age attributes, and both have work methods. Store multiple teacher objects and multiple head teacher objects in two collections. Provide a method that can traverse these two collections at the same time and call the work method.
Employee class:

public abstract class Employee { 
	private String name; 
	private int age; 
public Employee() { }
public Employee(String name, int age) 
{ this.name = name; this.age = age; }
//Omit get/set 
public abstract void work(); 
}

Teacher class:

public class Teacher extends Employee{ 
	public Teacher() { }
	public Teacher(String name, int age) 
	{ 
	super(name, age); 
	}
	@Override3 
	public void work() 
	{ 
	System.out.println("The teacher is in class"); 
	} 
	}

Manager class:

public class Manager extends Employee { 
	public Manager() { }
	public Manager(String name, int age) { super(name, age); }
	@Override 
	public void work() 
	{ System.out.println("The head teacher manages the class"); } 
	}

Test class:

public void main(String[] args) throws UnsupportedEncodingException { 
	List<Teacher> teacherList = new ArrayList<Teacher>(); 
	teacherList.add(new Teacher("Zhang San",30)); 
	teacherList.add(new Teacher("Li Si",32)); 
	List<Manager> managerList = new ArrayList<Manager>(); 
	managerList.add(new Manager("Wang Wu",25)); 
	managerList.add(new Manager("Zhao Liu",23)); 
	getElement(teacherList); 
	getElement(managerList); 
	}
public static void getElement(List<? extends Employee> list){ 
	Iterator<? extends Employee> it = list.iterator(); 
	while (it.hasNext()){ 
	Employee employee = it.next(); 
	System.out.println(employee.getName()+"::"+employee.getAge()); 
	employee.work(); 
	} 
	}

summary

The beauty of generics is that there is no le~

Keywords: Java Maven JavaSE intellij-idea

Added by dmccabe on Sat, 15 Jan 2022 11:05:09 +0200

Programming VIP

Chapter 12 collection (ArrayList LinkedList generic)

Chapter 12 collection (ArrayList LinkedList generic)

12.1 array objects

12.2 Collection

12.2.1 general

12.2.2 inheritance system of set classes

12.2.3 Collection interface method

12.3 iterators

12.3.1 Iterator interface

12.3.2 implementation principle of iterator

12.3.3 concurrent modification exception

12.4 enhanced for loop

12.4.1 general

12.4.2 format

12.4.3 traversing arrays and sets

12.4.4 enhanced for loop principle

12.5 data structure

12.5.1 introduction to data structure

12.5.2 common data structures

Stack

queue

array

Linked list

12.6 List set

12.6.1 List interface features

12.6.2 List interface specific method (with index)

12.7 ArraysList set

12.7.1 general

12.7.2 ArrayList source code analysis

12.8 LinkedList set

12.8.1 general

12.8.2 LinkedList set specific methods

12.8.3 LinkedList source code analysis

LinkedList internal class Node class analysis: (it can be analyzed that LinkedList is a double linked list set)

12.9 generics

12.9.1 general

12.9.2 benefits of using generics

12.9.3 definition and use of generics

Define and use classes that contain generics

Methods with generics

Interface with generics

12.9.4 generic wildcards

Basic use of wildcards

Advanced use of wildcards -- restricted generics

12.9.5 generic qualification cases

summary

Popular Keywords