2022.8.20 - Generics, Data Structure, Collection 1

I. Generics

introduce

Generic is a new syntax added after JDK5 that can prebranch unknown types in classes, interfaces, or methods.
Adding generics ensures that there is only one type of data in the collection, which is handled well, and error messages can be prompted at compile time, otherwise problems will not be reported until run time, avoiding the hassle of type forcing.
Generics are mainly applied to the parameter and return value types of methods. What is the actual type of reception, when the generic will be converted to the actual type, it will be flexible and variable.
Generics simplify the development of API s by allowing ambiguous data types in classes or interfaces to be determined in the usage phase during the design process.
Define classes with generics

Define methods with generics

Define interfaces with generics

Getting started with generic wildcards

<1>Overview

There is no inheritance relationship between the use of generics, and you cannot accept objects of other generic types for variables that have already been assigned generics, that is, to keep the defining statements consistent when defining generics or not to write after them.

For example: ArrayList list = new ArrayList()//incorrect format, generic does not have inheritance relationship

<2>Use question marks for generic wildcards? Express. Definition interval used to limit generic data types. Individually used to represent any type has the same effect as not writing.

<3> ArrayList without generics is also an object by default, but if you explicitly write it out, then follow the rule that there is no inheritance between generics, that is, you cannot receive a determined generic object. The left figure explicitly writes so that no other objects can be added, and the right one can be added.
Generic Restricted - >= Subclass or <=Parent Class to limit scope

New objects cannot be added to a method because only one side of the interval can be determined, the other side can always be changed, the compiler cannot determine, and it is not appropriate to make a new subclass a parent, so the method is generally only used to do some work with incoming collections.

Generic Wildcard Application Scenario

package com.itheima.demo03_Generic wildcards.p02 Generic Restriction;

import java.util.ArrayList;

public class Test1 {

    public static ArrayList<Fu> list = new ArrayList<>();
    public static ArrayList<Zi> list2 = new ArrayList<>();
    public static ArrayList<Sun> list3 = new ArrayList<>();

    public static Fu f = new Fu();
    public static Zi z = new Zi();
    public static Sun s = new Sun();

    public static void main(String[] args) {
        ArrayList<Fu> list = new ArrayList<>();
        ArrayList<Zi> list2 = new ArrayList<>();
        ArrayList<Sun> list3 = new ArrayList<>();

        show(list);
        show(list2);
        //show(list3);

        //show2(list);
        show2(list2);
        show2(list3);
        
        show3(list);
        show3(list2);
        show3(list3);
  }
    
//Since there is a restriction that the parameter must be at least Zi class and above (that is, Zi's parent class), when I add an object with such an argument, I can only add it lower than I do
    //Zi class at the lowest type, the lowest collection generic that will be passed in in the future must be Zi class, so the subclass type of Zi class must be operable
    private static void show(ArrayList<? super Zi> list) {
        //list.add(f);
        list.add(z);//Yes?
        list.add(s);//Yes?

    }
    
//Here, because the range of parameters is limited to Zi class and below, so when I use actual parameters, I don't know how low the bottom is, so I dare not add any, because only lower than me
    //The lowest type is uncertain, and future incoming set generics are not necessarily subclasses, so there is no guarantee that subclasses of subclasses will be added.
    private static void show2(ArrayList<? extends Zi> list) {

        //list.add(f);
        //list.add(z);
        //list.add(s);

    }
    
    public static void show3(ArrayList list) {
        list.add(new Zi());
    }

}

class Fu {
}

class Sun extends Zi {
}

class Zi extends Fu {
}

2. Data structure

Summary
- Data structure: This is how data is stored and represented, which helps us choose a more appropriate set because different sets store data using different data structures, with different advantages and disadvantages.
- Common data structures: stacks, queues, arrays, chains, and red and black trees.
Stack structure

Queue structure
Array structure
Chain List Structure
Tree structure - "height" divides left height and right height to determine whether a node is balanced or not is to compare left and right height of a node

<1>Binary Tree - If the number of children per node in the tree does not exceed 2, then the tree is a binary tree.

<2>Binary Find Tree
- The binary tree condition is satisfied, and the left subtree node values are less than or equal to the root node, and the right subtree node values are greater than or equal to the root node, which helps query and excludes half of the data at a time.
- Problem: Limping - If there is a tree like a chain and there is no branch, it's actually no difference when searching, it's also a slow way to find it.
<3>Balanced Binary (Find) Tree
- The absolute height difference between the left and right subtrees is no more than 1, and both subtrees are a balanced binary tree
- Avoid "cripple" phenomenon, reduce tree height, improve search efficiency
- How balanced binary (find) trees are maintained
  
  When a new node is inserted, check to see if the insertion disrupts the tree balance, and if so, rotate to change the tree structure.
  
  * Right-handed: the right son of the left son disconnects the old father, the old father and the new father. See Balanced Binary Tree Rotated Right
  
  * Left-handed: the left son of the right son disconnects from the old father, the old father from the old one, and the right son ascends to the new one. See Balanced Binary Tree Left Rotation and Left Rotation Example Diagram
<4>Red-Black Tree-Black-Red to keep balance by ensuring the same number of black nodes in each path

3. Collection

Summary
A single-column collection in a collection - Collection

Ordered or out-of-order element access refers to whether the order of data stored is a,b,c, and the order of data taken out is also a,b,c
- From Universal to Special
  1. Describes the methods common to the Collection class and all its subclasses, illustrated with ArrayList, and supported by others.
  2. Describes some of the ways List is unique to you
  3. Introducing LinkedList's own unique approach
- Single Column Set Universal Method
  
  The toArray() method, which is a method of converting to an array, specifies the length of the converted array, generally the number of elements in the original set.
- Iterator-Mode 1 is used to traverse a set If an iterator uses a set to add elements during an iteration, it will report concurrent exceptional errors, because the iterator will always remember that the length is different from the original, and if it adds it will also use an iterator.
- Traversing Sets - Mode 2 - Enhancement for