generic paradigm
Set
TreeSet
01. Generics - Overview
The role of generics? Is a new feature introduced in JDK5. It provides a mechanism for type safety checking at compile time Benefits of generics? 1. The possible problems at runtime are advanced to the compilation period 2. Casts are avoided
public class Demo {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add(123);
Iterator it = list.iterator();
while (it.hasNext()) {
//Object next = it.next();
//int length = next. length(); // The object class does not have a length method
//Strong rotation
String next = (String) it.next();
/*
If there are other data types besides String in the element, a conversion exception will be reported:
java.lang.ClassCastException
*/
System.out.println(next);
}
}
}02 . Use of generic classes
Where generics can be used 1. After class: generic class 2. Method: generic method 3. After interface: Generic interface understand Our common generic class is ArrayList ArrayList has no generics before JDK4, which will have disadvantages (there will be exceptions during forced conversion, and the amount of code is increased to solve the disadvantages) In order to solve these disadvantages, ArrayList after JDK5 is designed as a generic class Generics represent unknown types that can be determined when creating objects be careful If a class is followed by < E >, it indicates that it is a generic class When creating a generic class object, you must determine the specific data type for the generic
03. Generic - Custom generic class
Definition format of generic class
< type >: Specifies the format of a type
Write arbitrarily in angle brackets according to the definition rules of variables. Generally, write a capital letter
For example, < E >, < T >, < Q >, < m >
< type 1, type 2 >: specify mu lt iple types of formats
Multiple types are separated by commas
For example, < e, t >, < Q, M >, < K, V >
Definition format of generic class
Modifier class class name < type > {}
//Class test
class Test{
public static void main(String[] args) {
//Create object, specify type
Box<String> box = new Box<>();
box.setElement("Code to express to the goddess");
System.out.println(box.getElement());
//Create object, specify type
Box<Integer> box2 = new Box<>();
box2.setElement(18);
System.out.println(box2.getElement());
}
}
//Custom generic class
public class Box<T> {
//Member variable, type generic
private T element;
//Provide getXxx and setXxx methods
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
}04. Generic - use of generic methods
Use of generic methods in Java Looking at the API, we found that ArrayList has two methods 1. Object oArray(); Returns an array representation of a collection 2. < T> T[] toArray(T[] arr); Returns the representation of an array of the specified type of a collection
Code example
public class Demo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("Zhang San");
list.add("Li Si");
list.add("Wang Wu");
//1. Object toArray(); Returns an array representation of a collection
Object[] objects = list.toArray();
System.out.println(Arrays.toString(objects)); //The types obtained are all Object types. It is inconvenient to call methods
//2. <T> T[] toArray(T[] arr); Returns the representation of an array of the specified type of a collection
String[] strings = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(strings)); //At this time, all the elements obtained are of String type
}
}05. Generic - Custom generic method
Definition format of generic method
Modifier < type > return value type method name (type variable name)
For example, public < T > void show (T) {}
Requirements:
Define a method that receives a collection and four elements (specified by the data type caller)
Add an element to the collection and return
Code example
public class Demo {
public static void main(String[] args) {
//Test 1: the element is of String type
ArrayList<String> list1 = addElement(new ArrayList<String>(), "Fei Zhang", "Liu Bei", "Guan Yu", "Zhao Yun");
System.out.println(list1);
//Test 2: the element is of type int
ArrayList<Integer> list2 = addElement(new ArrayList<Integer>(), 11, 22, 33, 44);
System.out.println(list2);
}
//Modifier < type > return value type method name (type variable name)
public static <T> ArrayList<T> addElement(ArrayList<T> list, T t1, T t2, T t3, T t4) {
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
return list;
}
}06. Generic - Generic interface
Examples of generic interfaces in Java?
public interface List<E> extends Eollection<E>..
The user is ArrayList. Continue the generic type (method 1)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable..
How to use generic interfaces?
Mode 1 The implementation class is not generic. The implementation class is also defined as a generic class. The specific data type is determined only when the implementation class object is created
Mode 2 The implementation class determines the specific data type
Definition format of generic interface?
Modifier interface interface name < T > {}
Code example
//Class test
public class Demo {
public static void main(String[] args) {
//Test method 1: determine the specific data type when creating the implementation class object
InterImpl1<String> i1 = new InterImpl1<>();
i1.method("Dark horse programmer");
//Test method 2: since the type has been determined, you can directly create the implementation class object without determining the specific data type
InterImpl2 i2 = new InterImpl2();
i2.method(100);
}
}
//Custom generic interface
interface inter<T> {
public abstract void method(T t);
}
//Mode 1 The implementation class is not generic. The implementation class is also defined as a generic class. The specific data type is determined only when the implementation class object is created
class InterImpl1<T> implements inter<T> {
@Override
public void method(T t) {
System.out.println(t);
}
}
//Mode 2 The implementation class determines the specific data type
class InterImpl2 implements inter<Integer>{
@Override
public void method(Integer integer) {
System.out.println(integer);
}
}
07. Generic wildcard
Type wildcard: <? > ArrayList<?>: Represents an ArrayList collection whose element type is unknown, and its elements can match any type Upper limit of type wildcard: <? Extensions type > ArrayList<? Extensions Number >: indicates that the type is Number or a subclass of Number Type wildcard lower limit: <? Super type > ArrayList<? Super Number >: indicates that the type is Number or the parent class of Number
Sample code
public class Demo {
public static void main(String[] args) {
/*
Integer Inherit from Number inherit from Object
*/
//The type is any type
method01(new ArrayList<Integer>());
method01(new ArrayList<Number>());
method01(new ArrayList<Object>());
//The type is Number or a subclass of Number
method02(new ArrayList<Integer>());
method02(new ArrayList<Number>());
//method02(new ArrayList<Object>()); // If the parent type of Number is passed, an error is reported
//The type is Number or the parent of Number
//method03(new ArrayList<Integer>()); // If the subtype of Number is passed, an error is reported
method03(new ArrayList<Number>());
method03(new ArrayList<Object>());
}
//The type is any type
public static void method01(ArrayList<?> list) {
}
//The type is Number or a subclass of Number
public static void method02(ArrayList<? extends Number> list) {
}
//The type is Number or the parent of Number
public static void method03(ArrayList<? super Number> list) {
}
}08. Set overview
Single column set Collection interface List interface (repeatable) ArrayList implementation class LinkedList implementation class Set interface (non repeatable) TreeSet implementation class} HashSet implementation class
09. Set basic usage
Set set features
1. Weight removal
2. Inconsistent access order
3. There is no method with index, so you can't use ordinary for to traverse, and you can't get / delete elements through index
Set set exercise
Store string and traverse
Code example
public class Demo {
public static void main(String[] args) {
Set<String> set = new TreeSet<>();
set.add("cc");
set.add("dd");
set.add("aa");
set.add("aa");
set.add("bb");
set.add("bb");
//Traversal 1: normal for cannot
//for (int i = 0; i < set.size(); i++) {
//System.out.println(set.get(i)); // There is no way to manipulate the index
//}
//Traversal 2: iterator
Iterator<String> it = set.iterator();
while (it.hasNext()){
System.out.println(it.next());
}
System.out.println("-----------");
//Traversal 3: enhanced for
for (String s : set) {
System.out.println(s);
}
}
}
10. TreeSet - basic use
TreeSet set features
1. Weight can be removed
2. Inconsistent access order
3. Elements can be sorted according to rules (focus)
TreeSet set exercise 1
The access order of Integer is inconsistent, but the storage order of Integer is inconsistent
TreeSet set exercise 2
Store the Student object and traverse it (an error is reported because there is no sorting rule)
Code example
public class Demo {
public static void main(String[] args) {
}
//TreeSet set exercise 2
private static void test02() {
//Store the Student object and traverse
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("Fei Zhang",18));
set.add(new Student("Guan Yu",19));
set.add(new Student("Liu Bei",20));
System.out.println(set); //An error is reported because there is no sorting rule
}
//TreeSet set exercise 1
private static void test01() {
//Store integers of type Integer and traverse
TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(3);
set.add(4);
set.add(1);
set.add(2);
System.out.println(set); //[1, 2, 3, 4, 5] although the access order is inconsistent, it is orderly
}
}
11. Use of TreeSet natural sorting Comparable
Introduction to Comparable interface API
The interface imposes an overall sort on each of its implementation classes, which is called "natural sort"
The compareTo method of class is called "natural sorting method"
Steps for using natural sorting Comparable
1. Construct TreeSet set with null parameters
2. The user-defined class shall implement the Comparable interface
3. Rewrite the compareTo method in the Comparable interface
Code example
public class Demo {
public static void main(String[] args) {
//1. Construct TreeSet set with null parameters
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("Liu Bei",20));
set.add(new Student("Fei Zhang",18));
set.add(new Student("Guan Yu",19));
//Traversal set
for (Student stu : set) {
System.out.println(stu);
/*
Student{name='Zhang Fei ', age=18}
Student{name='Guan Yu ', age=19}
Student{name='Liu Bei ', age=20}
*/
}
}
}
//2. The user-defined class shall implement the Comparable interface
public class Student implements Comparable<Student> {
//3. Rewrite the compareTo method in the Comparable interface
@Override
public int compareTo(Student o) {
/*
return Age of current object - the age of the stored object
If the return value is negative, it means that the stored element is a small value and stored on the left
If the return value is 0: it means duplicate and not saved
If the return value is a positive number, it means that the stored element is a large value and stored on the right
*/
int result = this.age - o.age;
return result;
}
12. Natural sequencing - Exercise
demand
Sort by age from small to large. If the age is the same, sort by initials
If the name and age are the same, it is considered to be the same person and does not exist
Code example
public class Demo {
public static void main(String[] args) {
//Create a collection add elements
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("zhangsan", 24));
set.add(new Student("lisi", 18));
set.add(new Student("wangwu", 24));
set.add(new Student("zhaoliu", 24));
set.add(new Student("chenglong", 58));
//Traversal set
for (Student stu : set) {
System.out.println(stu);
/*
Student{name='lisi', age=18}
Student{name='wangwu', age=24} //w In front of z
Student{name='zhangsan', age=24} //Details: z, h and a are the same. Compare n and o, and n is in front of o
Student{name='zhaoliu', age=24}
Student{name='chenglong', age=58}
*/
}
}
}
class Student implements Comparable<Student> {
@Override
public int compareTo(Student s) {
/*
Sort age from small to large: if the age of the current object - the age of the stored object
Negative number: indicates that the stored element is a small value, which is stored on the left
0: means duplicate, continue to judge the name!
Positive number: indicates that the stored element is a large value, which is stored on the right
*/
int result = this.age - s.age;
//result is 0: it means duplicate, continue to judge the name!
return result == 0 ? this.name.compareTo(s.name) : result;
}
...
}13. Use of TreeSet Comparator
Steps for using Comparator to sort comparators
1. Use the structure with parameters to create a TreeSet set
2. Comparator sorting is to let the set construction method receive the implementation class object of comparator and rewrite the compare method
3. When rewriting the compare method, it should be noted that the sorting rules must be written according to the required "primary condition" and "secondary condition"
demand
Customize the Teacher class. The attributes are name and age
Sort by age. If the age is the same, sort by name
Code example
public class Demo {
public static void main(String[] args) {
//Comparator sorting is to let the collection construction method receive the implementation class object of comparator and rewrite the compareTo method
TreeSet<Teacher> set = new TreeSet<>(new Comparator<Teacher>() {
@Override
public int compare(Teacher t1, Teacher t2) {
//When rewriting the compareTo method, note that the collation must be written according to the required "primary condition" and "secondary condition"
//[1] Main conditions: specific age
int result = t1.getAge() - t2.getAge();
//[2] Secondary condition: name
return result == 0 ? t1.getName().compareTo(t2.getName()) : result;
}
});
//Add elements and traverse the collection
set.add(new Teacher("zhangsan", 24));
set.add(new Teacher("lisi", 18));
set.add(new Teacher("wangwu", 24));
set.add(new Teacher("zhaoliu", 24));
set.add(new Teacher("chenglong", 58));
for (Teacher tea : set) {
System.out.println(tea);
/*
Student{name='lisi', age=18}
Student{name='wangwu', age=24} //w In front of z
Student{name='zhangsan', age=24} //Details: z, h and a are the same. Compare n and o, and n is in front of o
Student{name='zhaoliu', age=24}
Student{name='chenglong', age=58}
*/
}
}
}14. TreeSet - Comparison of two comparison methods
Natural sorting Comparable:
The user-defined class implements the Comparable interface, rewrites the compareTo method, and sorts according to the return value
Comparator sort comparator
Take the implementation class of the Comparator interface as a parameter, pass it to the parameter structure of TreeSet, rewrite the compare method, and sort according to the return value
By default, natural sorting is used. When natural sorting does not meet the current demand, comparator sorting is used
Return value rule
If the return value is negative, it means that the stored element is a small value and stored on the left
If the return value is 0: it means duplicate and not saved
If the return value is a positive number, it means that the stored element is a large value and stored on the right
Practice needs
Store four strings, "c","ab","df","qwer"
Sort by length in ascending order, and sort by initials as long as possible
Code example
public class Demo {
public static void main(String[] args) {
/*
1. Check the String source code and find that String has implemented the natural sorting interface
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence,
Constable, ConstantDesc {
2. However, sorting according to the initial letter does not meet the requirements of the topic
3. So you need to use the comparator to sort!
*/
TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
//[1] Sort by length: ascending
int result = s1.length() - s2.length();
//[2] Secondary condition: alphabetical
return result == 0 ? s1.compareTo(s2) : result;
}
});
set.add("df");
set.add("c");
set.add("qwer");
set.add("ab");
System.out.println(set);
}
}15. Data structure - binary tree
Naming convention
TreeSet tree structure - a member of the Set system
ArrayList array structure - a member of the List system
LinkedList linked List structure - a member of the List system
Classification of trees?
Binary tree
Binary lookup tree
Binary balanced tree
Red black tree (red black tree at the bottom of TreeSet set)
Each element in the tree structure is called a node (object), which contains four parts
1. Parent node location
2. Value
3. Left sub node position
4. Right child node location
be careful
If there is no parent node, the address of the parent node is null
If there are no more child nodes, the child node address is null
In the tree structure, the number of child nodes of each node is called degree (degree without son is 0, degree with two sons is 2)
be careful
In a binary tree, the degree of any node must be less than or equal to 2
The number of layers in a binary tree graph is called tree height
The top layer is called the root node
Centered on the root node,
The graph expanded by the left sub node is called the left sub tree (the sub tree also has tree height)
The graph expanded by the right sub node is called the right sub tree (the sub tree also has tree height)
be careful
Ordinary binary trees have no storage rules
16. Data structure - binary lookup tree
Binary lookup tree?
Also known as "binary sort tree", or "binary search tree"
characteristic?
1. There are at most two child nodes on each node
2. The left child node of each node is smaller than itself
3. The right child node of each node is larger than itself
Summary: any node increases from left to right
17. Data structure - binary tree finding and adding nodes
The nodes are stored according to the rules of binary search tree
07 04 10 05
Storage rules?
The small one is on the left
The big one is on the right
The same does not exist
07 ＾ 07 - > no one compares. You are the root node
↓↓ 04 - > compared with the root node, less than the root node is saved to the left
04 # 10 # 10 - > compared with the root node, larger than the root node is stored on the right
↓ ↓
05 ＾ 05 - > compared with the root node, smaller than the root node is stored on the left, but there are people on the left (in the binary tree, the degree of any node must be less than or equal to 2), so compared with node 04, larger than node 04 is stored in the child node on the right
Thinking: if 11 comes in now, how can I save it?
18. Data structure - balanced binary tree
Balanced binary tree?
The height difference between the left and right subtrees of a binary tree shall not exceed 1 (it is not required that the tree height is completely the same)
The left and right subtrees of any node are balanced binary trees
19. Balanced binary tree - left-handed
Mechanism of ensuring binary tree balance
1. Left hand rotation
2. Right hand rotation
Rotation triggered mechanism (key memory)
When a node is added, the tree is no longer a balanced binary tree, and rotation will be triggered
Left-handed?
Pull the right side of the root node to the left, and the original right child node becomes the root node
And transfer the redundant (no one wants) left child node to the degraded root node as the right child node
20. Balanced binary tree - right rotation
Left-handed? Pull the left side of the root node to the right, and the original left child node becomes the root node And transfer the redundant (no one wants) right child node to the degraded root node as the right and left child node
21. Balanced binary tree - Summary
Binary tree - > no storage rule, low search efficiency ↓ Binary search (search / sort) tree - > degree of each node < = 2. Judging from the root node, the left child node is smaller than itself and the right child node is larger than itself ↓ Balanced binary tree - > height difference between left and right subtrees < = 1 ↓ If the addition of new nodes breaks the balance - > trigger the mechanism to ensure the balance of binary tree ↓ Left / right rotation - > mainly look at pulling towards that side
22. Balanced binary tree - left and right
Due to the different positions of adding data, there are four cases of rotation
Left: when the left subtree of the left subtree of the root node is inserted, the balanced binary tree is unbalanced
Left and right: when a node is inserted into the right subtree of the left subtree of the root node, the balanced binary tree is unbalanced
Right: when a node is inserted into the right subtree of the right subtree of the root node, the balanced binary tree is unbalanced
Right left: when the left subtree of the right subtree of the root node is inserted, the balanced binary tree is unbalanced
be careful:
Rotation ensures balanced binary tree balance. It may not rotate only once, but may rotate many times
Based on each node, it can be rotated
23. Balanced binary tree - right and right left
