The data structure

Data structure is a set of data elements with a certain logical relationship, which applies a certain storage structure in a computer and encapsulates the corresponding operation. It contains three aspects: logical relationship, storage relationship and operation. Different kinds of data structures are suitable for different kinds of applications, and some are even dedicated to specific job tasks. For example, computer networks rely on routing tables to operate, and B-tree height is suitable for database encapsulation.Copy the code

Common data structures

Linear structure

Linear structure refers to a data structure in which there is a "one to one" linear relationship between data elementsCopy the code

Array, Queue, Linked List, Stack

Nonlinear structure

In a nonlinear structure, each data element is no longer held in a linear sequence, and each data element may be associated with zero or more other data elements. According to the relationship, it can be divided into hierarchy structure and group structure.Copy the code

Heap, Hash table, Tree, Graph

An array of

Characteristics of the

1. Simplest and most commonly used structure.
2. Linear structure, so the memory space is continuous
3. Stores a finite number of data of the same type

advantages

The memory space is contiguous, so it has the following advantages

1. The search and modification based on the index are efficient
2. Easy to traverse groups by index

disadvantages

There are also some disadvantages because of the contiguous memory space

1. When you insert or delete an array at a position other than the end of the array, the following elements are forced to move, resulting in low efficiency
2. The memory space is fixed and cannot be automatically expanded
3. Only one type of data can be stored

Hand rolled code

add

Insert the head

public static void main(String[] args) {
    String[] array = new String[3];
    headAdd(array, "hello1");
    headAdd(array, "hello2");
    headAdd(array, "hello3");
    headAdd(array, "hello4");
    for (String i : array) {
        System.out.print(i + "");  
    }
    // Add :hello4, array space is full!
    // hello3 hello2 hello1 
}

public static void headAdd(String[] array, String str) {
    int index = array.length;
    if (null! = array[index-1]) {
        System.out.println("Add." + str + Array space is full!);
    }
    for (int i = index - 2; i > 0; i--) {
        String arr = array[i];
        if(arr ! =null) {
            array[i+1] = arr;
        }
    }
    array[0] = str;
}

Copy the code

Insert the tail

public static void main(String[] args) {
    String[] array = new String[3];
    tailAdd(array, "hello1");
    tailAdd(array, "hello2");
    tailAdd(array, "hello3");
    tailAdd(array, "hello4");
    for (String i : array) {
        System.out.print(i + "");
    }
    // Add :hello4, array space is full!
    // hello1 hello2 hello3 
}

public static void tailAdd(String[] array, String str) {
    int index = array.length;
    if (null! = array[index-1]) {
        System.out.println("Add." + str + Array space is full!);
        return;
    }
    for (int i = 0; i < index; i++) {
        String arr = array[i];
        if (arr == null) {
            array[i] = str;
            break; }}}Copy the code

Specify position insert

public static void main(String[] args) {
    String[] array = new String[3];
    appointAdd(array, "hello1".1);
    appointAdd(array, "hello2".1);
    for (String i : array) {
        System.out.print(i + "");
    }
    // null hello2 hello1 
}

public static void appointAdd(String[] array, String str, int x) {
    int index = array.length;
    if (x >= index) {
        System.out.println("Subscript out of bounds!");
        return;
    }
    if (null! = array[index-1]) {
        System.out.println("Add." + str + Array space is full!);
        return;
    }
    for (int i = index - 1; i >= 0; i--) {
        if(array[i] ! =null) {
            array[i+1] = array[i];
        }
        if (i == x) {
            array[i] = str;
            break; }}}Copy the code

Modify the

public static void main(String[] args) {
    String[] array = new String[3];
    appointAdd(array, "hello1".1);
    update(array, "hello2".1);
    for (String i : array) {
        System.out.print(i + "");
    }
    // null hello2 null
}

public static void update(String[] array, String str, int x) {
    int index = array.length;
    if (x >= index) {
        System.out.println("Subscript out of bounds!");
        return;
    }
    array[x] = str;
}
Copy the code

delete

public static void main(String[] args) {
    String[] array = new String[3];
    appointAdd(array, "hello1".1);
    appointAdd(array, "hello2".1);
    update(array, "hello3".0);
    delete(array, 0);
    for (String i : array) {
        System.out.print(i + "");
    }
    // hello2 hello1 null
}

public static void delete(String[] array, int x) {
    int index = array.length;
    if (x >= index) {
        System.out.println("Subscript out of bounds!");
        return;
    }
    for (int i = x; i < index; i++) {
        if (i < index - 1) {
            array[i] = array[i+1];
            array[i+1] = null; }}}Copy the code

To find the

public static void main(String[] args) {
    String[] array = new String[3];
    appointAdd(array, "hello1".1);
    appointAdd(array, "hello2".1);
    update(array, "hello3".0);
    get(array, 1);
    for (String i : array) {
        System.out.print(i + "");
    }
    // Query data as hello2
    // hello3 hello2 hello1
}

public static void get(String[] array, int x) {
    int index = array.length;
    if (x >= index) {
        System.out.println("Subscript out of bounds!");
        return;
    }
    System.out.println("The query data is:" + array[x]);
}
Copy the code

conclusion

According to the above code can see the most efficient is to modify, query, directly according to the index position can achieve the desired effect; The second is tail insertion, which loops to the last empty position; Finally, insert the head, insert the specified position, delete; Because you have to move other elements;Copy the code

Applicable scenario

Frequent queries have low requirements on storage space and are rarely added or deleted.Copy the code