[Java basics 15] data structures and generics

1. Data structure

Data structure is a way of organizing and storing data at the bottom. It refers to the way in which data is arranged.

1.1 stack

Features: first in first out, last in first out

Similar to the bullet clip of a gun, the bullet pressed at the bottom of the clip will be fired last. The entrance and exit are at the head of the stack

1.2 queue

Features: first in, first out, last in, last out

Like a water pipe, the water that flows in first will flow out first. The incoming data is the head of the team and the outgoing data is the tail of the team.

1.3 array

Find data by index

Because the array has an index, the query is fast and the deletion and insertion efficiency is low

1.4 linked list

The linked list is similar to the plot of a role game. When the previous task is completed, it will point to the next one. The following is the structure of the linked list:

Complete linked list diagram:

Insert data into the list:

The more complex two-way linked list saves not only the address of the next data, but also the address of the previous data:


  • The linked list storage address is discontinuous because there is an address to store the next data.
  • The linked list query is relatively slow. You have to start from scratch every time.
  • The addition and deletion of the linked list is faster. You can modify the address point.

1.5 binary tree

It literally means a tree divided into two forks. In fact, it is a structure similar to this. One node, and then two child nodes are divided below. The two child nodes are divided into two child nodes respectively, and so on.

Structure diagram:


  • There is only one root node, and each node has at most two child nodes
  • Those with the same parent node are siblings
  • The maximum degree of each parent node is 2 and the minimum is 0
  • The height of the leaf node is 1, the parent node is 2, and so on to the root node
  • The root node is the first layer

1.5. 1 binary tree storage and fast search

The order is stored according to the rule that the left side of the node is less than or equal to the parent node and the right side is greater than the parent node, which is convenient for searching and sorting. Next, create a binary tree. Each leaf includes upper node, left node, right node and data.

// Example of a binary tree
public class Leaf {

    private int data;

    private Leaf top;
    private Leaf left;
    private Leaf right;

    public Leaf() {

    public Leaf(int data) {
        this.data = data;
    // get and set

public class LeafTest {
    public static void main(String[] args) {
        Leaf superLeaf = null;
        int[] x = {56, 86, 8, 95, 45, 34, 19, 20};

        for (int i = 0; i < x.length; i++) {
            if (i == 0) {
                superLeaf = new Leaf(x[i]);
            } else {
                addLeaf(superLeaf, x[i]);

    public static void addLeaf(Leaf leaf, int data) {
        if (leaf != null) {
            int superData = leaf.getData();

            if (data <= superData) {
                if (leaf.getLeft() == null) {
                    leaf.setLeft(new Leaf(data));
                } else {
                    addLeaf(leaf.getLeft(), data);
            } else {
                if (leaf.getRight() == null) {
                    leaf.setRight(new Leaf(data));
                } else {
                    addLeaf(leaf.getRight(), data);

// Query binary tree
public class LeafSearch {
    public static int x = -1;

    public static void main(String[] args) {
        int[] array = {56, 86, 8, 95, 45, 34, 19, 20};

        Leaf leaf = LeafTest.getLeaf(array);

        searchIndex(leaf, 8);


    private static void searchIndex(Leaf leaf, int i) {
        if (leaf != null) {
            int data = leaf.getData();
            if (data == i) {
                x = leaf.getIndex();
            } else if (data < i) {
                searchIndex(leaf.getRight(), i);
            } else if (data > i) {
                searchIndex(leaf.getLeft(), i);
        } else {
            x = -1;

The above is a simple example. The actual binary tree is only relatively wide, including complete binary tree, full binary tree, balanced binary tree, red black tree and so on. A series of explanations will be held in detail in the future.

2. Generics

From jdk1 For features introduced after 5, type constraints can be performed and checked at the compilation stage. Generics only support reference types. All interfaces and implementation classes of the collection system support generics.
Generics can be placed on classes, methods, and interfaces.

2.1 placing on class

// Format, t is only a generic identifier and can be any representation. Common: T,K,V,E
 Modifier  class Class name<T>{}
// Example
public class MyArrayList<T> {
    private ArrayList list = new ArrayList();

    public void add(T t) {

    public void remove(T t) {

public class Demo {
    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();

2.2 generic methods

Generic methods are used on methods to facilitate the creation of general methods. Generics are used on methods so that they can receive any type, and methods have universal types.

// format
 Modifier  <generic paradigm> Return type method name(parameter list ){}
public class MyFunction {
    public static <T> void print(T t) {

public static void functionTest() {

2.3 generic interfaces

// format
 Modifier  interface Interface class name<Generic variable>{}
public interface MyInterface<E> {
    void println(E e);

public class MyInterfaceImpl<E> implements MyInterface<E> {
    public void println(E e) {

public static void interfaceTest() {
    MyInterfaceImpl<String> myInterface = new MyInterfaceImpl<>();
    // Only String type can be passed at this time

    MyInterfaceImpl<Integer> myInterface1 = new MyInterfaceImpl<>();
    // Only Integer types can be passed at this time

2.4 generic wildcard (?)

Generic wildcard?,? It can be equipped with any type. There are two situations when using it:

  • \<? Extensions type \ >:? A generic type can only be a type or a subclass of a type
  • \<? Super type \ >:? The lower limit of wildcards. Generics can only be types or other classes
// Example
public class GenericImpl<E> {
    public void getSize(Collection<? extends E> collection) {

public static void test() {
    GenericImpl<Object> generic = new GenericImpl<>();

    List<Object> list = new ArrayList<>();


3. Variable parameters

Variable parameters are mainly used in formal parameters and can receive multiple parameters. It is essentially an array. Variable parameter transfer is more flexible
, you can not pass one, more or arrays. The main features are as follows:

  • A parameter list can only have one parameter
  • Variable parameters can only be placed at the end of the formal parameter list
// format
 type... Parameter name
private static void paramTest(String... strings) {
    for (int i = 0; i < strings.length; i++) {

paramTest("sa", "as");
String[] x = {"1", "2"};

At the end of this chapter, it is used for personal learning and introduction to Xiaobai. Don't spray it! I hope you can praise the collection support!

Source code [GitHub] [code cloud]

Keywords: Java

Added by rem on Mon, 03 Jan 2022 21:54:55 +0200