current position:Home>Data structure and common collection summary

Data structure and common collection summary

2022-01-27 03:44:39 madreain

Data structure and common collection summary

data structure ( English :data structure) It's stored in the computer 、 How to organize data . Data structure is a kind of data structure with certain logical relationship , Apply a storage structure to a computer , And encapsulates the data element set of the corresponding operation . It contains three aspects , logical relationship 、 Storage relationships and operations . Different kinds of data structures are suitable for different kinds of applications , And some are even dedicated to specific job tasks .

In short, the data structure ( English :data structure) It's the organization of data 、 Management and storage formats , Its purpose is to access and modify data efficiently .

Data structures are mainly divided into : Array (Array)、 Stack (Stack)、 queue (Queue)、 Linked list (Linked List)、 Trees (Tree)、 Hash table ( Also called hash table )(Hash)、 Pile up (Heap)、 chart (Graph). The data structure can be divided into linear tables ( The full name is linear storage structure . Using linear tables to store data can be understood in this way , namely “ String all the data in one line , And then store it in physical space ”, Contains a one-dimensional array 、 Stack 、 queue 、 Linked list ) And nonlinear tables

️ There are only two ways to store data structures : Array ( Sequential storage ) And the list ( Chain store )

Time complexity

In computer science , The time complexity of the algorithm (Time complexity) It's a function , It qualitatively describes the running time of the algorithm . This is a function of the length of the string representing the input value of the algorithm . Time complexity is often large O Symbolic representation , The lower order and first term coefficients of this function are not included . When using this method , Time complexity can be called asymptotic , That is to say, when the input value approaches infinity .

Representation

「 Big O Symbolic representation 」, namely T(n) = O(f(n)), stay Big O In symbolic representation , The formula of time complexity is : T(n) = O( f(n) ), among f(n) Represents the sum of execution times per line of code , and O Represents a positive proportional relationship

Common time complexity levels

  • Constant order O(1)
  • Logarithmic order O(logN)
  • Linear order O(n)
  • Linear logarithmic order O(nlogN)
  • Square order O(n²)
  • Cubic order O(n³)
  • K Order of second order O(n^k)
  • Exponential order (2^n)

The complexity of the algorithm is generally divided into the following steps

  • Find out the basic statements in the algorithm : The most frequently executed statement in the algorithm is the basic statement , It's usually the innermost circulatory body .
  • Count the number of times a basic statement has been executed : You only need to calculate the number of basic statement executions , That is, as long as the highest power of the function is correct , All the coefficients of the lower power and the highest power can be ignored . This can simplify algorithm analysis , Focus on the most important point : growth rate .
  • Use big Ο Represents the time performance of the algorithm : Put the number of basic statement execution times into large order Ο In the mark .

It's a big one O There are usually three rules for notation

  • With constant 1 Replace all the addition constants in runtime ;
  • Only the highest order term in the time function ;
  • If the highest order term exists , Then the coefficient before the highest order term is omitted ;

The example analysis

Here are some common examples to help us understand time complexity

1. Constant order O(1)

No matter how many lines of code are executed , As long as there is no complex structure such as circulation , So the time complexity of this code is very high O(1), Examples are as follows

int i = 0;// Do it once 
int j = 1;// Do it once 
++i;// Do it once 
j++;// Do it once 
int m = i + j;// Do it once 
int n = j - i;// Do it once 
 Copy code 

When the above code is executed , Each line of code is executed once , Not with the scale of the problem n Change by change , The time it takes does not increase with the growth of a variable , So no matter how long this kind of code is , Even if there are tens of thousands of lines , Both can be used. O(1) To represent its time complexity .

2. Logarithmic order O(logN)

Code first and then analyze , here n First, an uncertain number

int i = 1;// Do it once 
while(i<n)
{
    i = i * 2;// perform log2^n
}
 Copy code 

As you can see from the code above , stay while Inside the loop , Every time i*2 And then reassign it to i, After finishing ,i distance n Will get closer and closer . Suppose we're cycling j After that ,i> n 了 , Now exit the current loop , in other words 2 Of j To the power of n, that j=log2^n, In other words, the cycle log2^n Later , That's the end of the code . So we get that the time complexity of this code is T(n)=O(logn).

3. Linear order O(n)

Here we use a frequently used code to analyze

int j = 0;// perform 1 Time 
for(i=1; i<=n; i++)// perform n Time 
{
   j = i;// perform n Time 
   j++;// perform n Time 
}
 Copy code 

In this code for The code in the loop will execute n All over , So it takes time to n Changed by , So this kind of code can be used T(n)=O(n) To represent its time complexity .

4. Linear logarithmic order O(nlogN)

Linear logarithmic order O(nlogN) It's really easy to understand , Time complexity is O(logn) Code loop for N All over , So its time complexity is n * O(logN), That's it. O(nlogN). The reference codes are as follows

for(m=1; m<n; m++)// perform n Time 
{
    i = 1;// perform n Time 
    while(i<n)
    {
        i = i * 2;// perform n*logN Time 
    }
}
 Copy code 

First while The time complexity in the loop is logarithmic O(logN), And logarithmic order O(logN) The same reason as the example of , And then this while The loop will be based on the outer layer for The execution of the loop will be executed n Time , So is T(n)=O(nlogN)

5. Square order O(n²)

Square order O(n²) It's easier to understand , If you put O(n) The code of , Its time complexity is O(n²) 了 . Typical is double for Examples of loops

for(i=1; i<=n; i++)// perform n Time 
{
   for(j=1; j<=n; j++)// perform n*n Time 
    {
       k = j;// perform n*n Time 
       k++;
    }
}
 Copy code 

This code is nested in two layers n loop , So the time complexity is zero O(n*n), namely T(n)=O(n²)

If we put the outer layer for Cyclic n Change to m, What's the complexity of his time

for(i=1; i<=m; i++)// perform m Time 
{
   for(j=1; j<=n; j++)// perform m*n Time 
    {
       k = j;
       k++;
    }
}
 Copy code 

The first layer of this code is nested m loop , The second level is n loop , So the time complexity is zero O(mn), namely T(n)=O(mn)

6. Cubic order O(n³)

Refer to the square order above O(n²) Example , We can infer the cubic order O(n³) Is nested three layers n loop , The example code is as follows

for(i=1; i<=n; i++)// perform n Time 
{
   for(j=1; j<=n; j++)// perform n*n Time 
    {
     for(k=1; k<=n; k++)// perform n*n*n Time 
      {
       o = k;
       o++;
      }
    }
}
 Copy code 

This code is nested three layers n loop , So the time complexity is zero O(nnn), namely T(n)=O(n³)

7. K Order of second order O(n^k)

So you can also get K Order of second order O(n^k) It's nesting k layer n loop , So there is no example

8. Exponential order (2^n)

The most common scenario for exponential order is to find subsets ( Give a group No repeating elements Array of integers for nums, Returns all possible subsets of the array ( Power set )), The example code is as follows

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> output = new ArrayList();
    output.add(new ArrayList<Integer>());

    for (int num : nums) {// perform n Time 
      List<List<Integer>> newSubsets = new ArrayList();
      for (List<Integer> curr : output) {//
        newSubsets.add(new ArrayList<Integer>(curr){{add(num);}});
      }
      for (List<Integer> curr : newSubsets) {
        output.add(curr);
      }
    }
    return output;
  }
 Copy code 

The time complexity is T(n)=O(n*2^n)

️ The law of addition : The total complexity is equal to the complexity of the code with the largest magnitude

️ Multi segment code takes the maximum : For example, there are single loop and multiple loops in a piece of code , So take the complexity of multiple cycles .

Spatial complexity

Spatial complexity (Space Complexity) It is a measure of the amount of storage space temporarily occupied by an algorithm during operation , Remember to do S(n)=O. (f(n)). For example, the time complexity of direct insertion sorting is O(n^2), The space complexity is O(1) . But the general recursive algorithm must have O(n) The complexity of space , Because every recursion stores the return information .

Representation

Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during its operation , It also reflects a trend , We use it S(n) To define . Spatial complexity S(n) = O(f(n))

Common time complexity levels

  • Constant order O(1)
  • Linear order O(n)
  • Square order O(n²)

The example analysis

1. Constant order O(1)

If the temporary space required for the algorithm to execute does not follow a certain variable n The size of , That is, the space complexity of this algorithm is a constant , Can be expressed as O(1)

int i = 0;
int j = 1;
++i;
j++;
int m = i + j;
int n = j - i;
 Copy code 

In code i、j、m、n The space allocated does not change with the amount of data processed , So its spatial complexity S(n) = O(1)

2. Linear order O(n)

Analyze the code directly

int[] m = new int[n];// The memory size occupied by this line of code is n
for(i=1; i<=n; ++i)// The following loop does not allocate new space 
{
   j = i;
   j++;
}
 Copy code 

In this code , first line new An array came out , The size of this data is n, Of this code 2-6 That's ok , Although there is a cycle , But there is no new space , therefore , The space complexity of this code mainly depends on the first line , namely S(n) = O(n)

The space complexity of special recursive algorithm

void fun1(int n){
  if(n<=1){
    return;
  }
  fun1(n-1);
}
 Copy code 

Suppose we pass in parameters here 6, that fun1(n=6) The call information of is put on the stack first . Next, call the same method recursively ,fun1(n=5) The call information of is put on the stack . And so on , Recursion gets deeper and deeper , There are more and more elements on the stack . When n=1 when , Recursion end condition reached , perform return Instructions , Way out of the stack . Final ,“ Method invocation stack ” All the elements of will be out of the stack one by one . From above “ Method invocation stack ” The process of getting in and out of the stack can be seen , The memory space required to perform a recursive operation is proportional to the depth of the recursion . The spatial complexity of pure recursive operations is also linear , If the depth of recursion is n, So the complexity of space is O(n), namely S(n)=O(n).

3. Square order O(n²)

int[][] matrix = new int[n][n];
 Copy code 

The two-dimensional array in this code is n*n, namely S(n) = O(n²)

️️️ In an algorithm , Considering the quality of an algorithm is based on the comparison of time complexity and space complexity , The least time and the least space must be the best , Sometimes we have to choose between time complexity and space complexity according to the specific situation . Most of the time , Time complexity is more important , We'd rather allocate more memory space , Also improve the execution speed of the program .

Array (Array)

An array is a structure that can store multiple elements continuously in memory , The allocation in memory is also continuous , The elements in the array are accessed through the array subscript , Array index from 0 Start . Arrays are stored sequentially in memory , Therefore, the logical sequence table can be well implemented .

Arrays are stored sequentially in memory

Memory is composed of successive memory units , Each memory unit has its own address . stay In these memory units , Some are occupied by other data , Some are idle . Every element in the array , It's all stored in small memory units , And the elements are closely arranged , You can't mess up the order in which elements are stored , You can't skip a storage unit for storage .

Instance to explain

int[] nums=new int[]{3,1,2,5,4,9,7,2};
 Copy code 

 Memory storage of array

In the diagram above , The orange grid represents free storage units , The gray grid represents the occupied storage unit , The red continuous grid represents the location of the array in memory . Different types of arrays , The number of bytes occupied by each element is also different , This diagram is just a simple schematic diagram .

Basic operations of arrays

Adding, deleting, modifying and querying arrays

  • First of all, let's say increase : To add new data to the array, you must first judge whether the inserted subscript is outside the range of the array , If it exceeds, throw an exception ; Then judge whether the size of the array is full , If it is full, the current array size 2 To expand the capacity of , Re assign values after capacity expansion ; Then it's really inserted , Insert the words , You need to move the data of the current position and its subsequent position back one bit , Then insert the new data into the current location , Move first and then insert .
  • Then delete : The logic of deleting an array is similar to that of adding an array , Just delete first and then move
  • Then change : If you change it , Judge the modified index Whether the location exists , There is no throw exception , Modify the assignment directly if it exists
  • Better say check : If you check , Judge the modified index Whether the location exists , There is no throw exception , If it exists, directly query the return value

Let's use the code to realize the addition, deletion, modification and query of the array according to this idea


public class DataStructureArray {

    /**
     *  Code implementation of array addition, deletion, modification and query operation 
     * 3,1,2,
     *
     * @param args
     */
    public static void main(String[] args) {
        MyArray myArray = new MyArray(2);
        // increase 
        myArray.add(0, 3);
        myArray.add(1, 1);
        myArray.add(2, 2);
        System.out.print("\n increase  ");
        myArray.outPut();
        // Delete 
//        myArray.delete(3);// An array 
        myArray.delete(1);
        System.out.print("\n Delete  ");
        myArray.outPut();
        // Change 
//        myArray.update(2, 1);// An array 
        myArray.update(1, 1);
        System.out.print("\n Change  ");
        myArray.outPut();
        // check 
        System.out.print("\n check  "+myArray.get(0));
    }

    public static class MyArray {

        private int[] myArray;
        private int size;

        public MyArray(int capacity) {
            this.myArray = new int[capacity];
            size = 0;
        }

        /**
         *  increase 
         *
         * @param index
         * @param element
         */
        private void add(int index, int element) {
            if (0 <= index && index <= size) {
                // First, judge whether the expansion is needed 
                if (size >= myArray.length) {
                    // Array capacity 
                    resize();
                }
                // from index The position begins to move , Loop right to left , Move elements one by one to the right 
                for (int i = size - 1; i >= index; i--) {
                    myArray[i + 1] = myArray[i];
                }
                myArray[index] = element;
                size++;
            } else {
                throw new IndexOutOfBoundsException(" Out of range of array actual elements ");
            }
        }

        /**
         *  Array capacity 
         */
        private void resize() {
            // What we take here is 2 Double expansion 
            int[] myNewArray = new int[myArray.length * 2];
            // data copy, Copy the old array data to the new array 
            System.arraycopy(myArray, 0, myNewArray, 0, myArray.length);
            // To assign a value 
            myArray = myNewArray;
        }

        /**
         *  Delete 
         *
         * @param index
         * @return
         */
        private int delete(int index) {
            if (0 <= index && index < size) {
                // Get deleted elements 
                int deleteElement = myArray[index];
                // And then index The element on the right of the position moves one bit to the left 
                for (int i = index; i < size - 1; i++) {
                    myArray[i] = myArray[i + 1];
                }
                size--;
                return deleteElement;
            } else {
                throw new IndexOutOfBoundsException(" Out of range of array actual elements ");
            }
        }

        /**
         *  Change 
         *
         * @param index
         * @param element
         */
        private void update(int index, int element) {
            if (0 <= index && index < size) {
                myArray[index] = element;
            } else {
                throw new IndexOutOfBoundsException(" Out of range of array actual elements ");
            }
        }


        /**
         *  check 
         *
         * @param index
         * @return
         */
        private int get(int index) {
            if (0 <= index && index < size) {
                return myArray[index];
            } else {
                throw new IndexOutOfBoundsException(" Out of range of array actual elements ");
            }
        }

        /**
         *  Output data 
         */
        private void outPut() {
            for (int i = 0; i < size; i++) {
                System.out.print(myArray[i]);
            }
        }
    }


}

 Copy code 

Advantages and disadvantages of array

From the implementation of the code, we can see , Arrays have very efficient query capabilities , Given the subscript, you can quickly query the corresponding elements , Speaking of this , Let's mention the binary search method , The idea of this algorithm is often used to solve practical problems when brushing the algorithm ; conversely , We can also see from the code implementation level that the addition and deletion of arrays is very time-consuming , Move the data every time . Therefore, we conclude that the array is suitable for query operation 、 Not suitable for adding or deleting .

A common collection of array implementations

ArrayList Is a dynamically modified array , We can take a look at its source code to deepen our understanding of the implementation of arrays Vector It's also a dynamic array , It's synchronous , Is an array that can be resized .

Linked list (Linked List)

A linked list is a physical storage unit that is discontinuous 、 Nonsequential storage structure , The logical order of data elements is achieved by the order of Pointers in a linked list . A linked list consists of a series of nodes ( Each element in a linked list is called a node ) form , Nodes can be generated dynamically at run time . Each node has two parts : One is the data domain where the data elements are stored , The other is a pointer field that stores the address of the next node . Compared to linear table order structure , The operation is complicated .

Storage of linked list in memory

The linked list adopts the method of inserting needles at every turn , Each node of the linked list is distributed in different bits of memory Set up , rely on next The pointer is related . In this way, the scattered debris space can be used flexibly and effectively .

The same data as the above array , The linked list is stored as follows

 Memory storage of linked list

Basic operations of linked lists

The addition, deletion, modification and query of linked list

  • First of all, let's say increase : Add data to the linked list , We must first judge whether it is an empty linked list , If it's empty , Direct assignment ; The insertion position of the insertion element is the head , Of the node to be inserted next Point to the current head node , Then set the head node to the current value The insertion position of the insertion element is the tail , Change the tail node's next Point to the current node , Then set the tail node to the current value Insert the element in the middle , Get the previous node of the insertion position first , Set the next node to be inserted is the current node ( That is, the of the previous node next node ), Then set the previous node next Is currently inserted
  • Then delete : The logic of deleting a linked list is similar to that of adding
  • Then change : If you change it , First find the current node , Then set the value of the current node
  • Better say check : If you check , We have to start from the node , Head of the node next, Again next, Keep checking until

Let's use the code to realize the addition, deletion, modification and query of the linked list according to this idea


public class DataStructureLinkedList {

    /**
     *  Code implementation of linked list addition, deletion, modification and query operation 
     * 3,5,7,
     *  Associative common arrays :LinkedList
     *
     * @param args
     */
    public static void main(String[] args) {
        MyLinked myLinked = new MyLinked();
        myLinked.add(0, 3);
        myLinked.add(1, 5);
        myLinked.add(2, 7);
        System.out.print("\n increase  ");
        myLinked.output();
//        myLinked.delete(0);
        myLinked.delete(1);
//        myLinked.delete(2);
        System.out.print("\n Delete  ");
        myLinked.output();
        myLinked.update(0,9);
        System.out.print("\n Change  ");
        myLinked.output();
    }

    public static class MyLinked {

        private Node head;
        private Node last;
        private int size;

        public class Node {
            int data;
            Node next;

            public Node(int data) {
                this.data = data;
            }
        }

        /**
         *  increase 
         *
         * @param index
         * @param element
         */
        private void add(int index, int element) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException(" Beyond the range of linked list nodes ");
            }
            Node currentNode = new Node(element);
            // Head insertion 
            if (index == 0) {
                // Empty list 
                if (head == null) {
                    head = currentNode;
                    last = currentNode;
                    // Head insertion 
                } else {
                    currentNode.next = head;
                    head = currentNode;
                }
                // Tail insertion 
            } else if (index == size) {
                last.next = currentNode;
                last = currentNode;
                // Intermediate insertion 
            } else {
                Node preNode = get(index - 1);
                currentNode.next = preNode.next;
                preNode.next = currentNode;
            }
            size++;
        }

        /**
         *  Delete 
         *
         * @param index
         * @return
         */
        private Node delete(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException(" Beyond the range of linked list nodes ");
            }
            Node deleteNode = null;
            // Head node delete 
            if (index == 0) {
                deleteNode = head;
                head = head.next;
                // Tail node delete 
            } else if (index == size - 1) {
                Node preNode = get(index - 1);
                deleteNode = last;
                preNode.next = null;
                last = preNode;
                // Delete intermediate nodes 
            } else {
                Node preNode = get(index - 1);
                preNode.next = preNode.next.next;
                deleteNode = preNode.next;
            }
            size--;
            return deleteNode;
        }


        /**
         *  Change 
         *
         * @param element
         */
        private void update(int index, int element) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException(" Beyond the range of linked list nodes ");
            }
            Node node = get(index);
            node.data = element;
        }


        /**
         *  check 
         *
         * @param index
         * @return
         */
        private Node get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException(" Beyond the range of linked list nodes ");
            }
            Node temp = head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }

        private void output() {
            Node temp = head;
            while (temp != null) {
                System.out.print(temp.data);
                temp = temp.next;
            }
        }
    }


}

 Copy code 

The advantages and disadvantages of linked list

Linked list is a fast write operation , Slow reading operation , In the actual application scenario , Those who need to add and delete data frequently are suitable to use linked lists

A common set of linked list implementations

LinkedList It's a two-way list , We can check its source code to deepen our understanding of the implementation of linked list

️️️ Speaking of this , We have finished introducing arrays and linked lists , Actually ️ There are only two ways to store data structures : Array ( Sequential storage ) And the list ( Chain store ).

Stack (Stack)

Stack ( English :stack) Also known as stack or stack , It's an abstract data type in computer science , Only at one end of an ordered linear data set ( Called the top of the stack , English :top) Add data ( English :push) And remove data ( English :pop) Arithmetic . So follow the last in, first out (LIFO, Last In First Out) Principle operation of .

It is often compared with another ordered linear data set queue . We will also talk about .

The stack is like a badminton tube ( One end is closed , The other end is open ), Put badminton into the cylinder , Put it first near the bottom of the cylinder , Put it close to the inlet of the cylinder . This is equivalent to a push The process of entering the stack . that , To take out these Badminton , You can only take... In the reverse order of putting , Take out first After that , Then take out the first , It is impossible to take out the badminton first placed in the innermost part first . This is equivalent to a pop The process of getting out of the stack .

The basic operation of the stack

The basic operation of stack is only entering stack and exiting stack , Into the stack, (push) It's just putting new elements on the stack , You can only put elements from the top side of the stack , The position of the new element will be the new top of the stack . The stack, (pop) It's just popping elements out of the stack , Only the top of stack elements are allowed to leave the stack , The previous element of the stack element will become the new top of the stack . Next, we use array and linked list to realize stack .

Array implementation stack


import java.util.Stack;

public class DataStructureUseArrayRealizeStack {

    /**
     *  Here, the stack is implemented with an array 
     *
     * @param args
     */
    public static void main(String[] args) {
        MyStack myStack = new MyStack(3);
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.print("\n Push  ");
        myStack.output();
//        myStack.push(4);// Out of stack size 
        myStack.pop();
        myStack.pop();
        myStack.pop();
        System.out.print("\n Out of the stack  ");
        myStack.output();
//        myStack.pop();// There is no data in the stack 

    }

    public static class MyStack {

        private int[] data;
        private int size;
        private int topIndex;

        public MyStack(int size) {
            data = new int[size];
            this.size = size;
            topIndex = -1;
        }

        private void push(int element) {
            if (isFull()) {
                throw new IndexOutOfBoundsException(" Out of stack size ");
            } else {
                data[topIndex + 1] = element;
                topIndex++;
            }
        }

        private int pop() {
            if (isEmpty()) {
                throw new IndexOutOfBoundsException(" There is no data in the stack ");
            } else {
                int[] newdata = new int[data.length - 1];
                for (int i = 0; i < data.length - 1; i++) {
                    newdata[i] = data[i];
                }
                int element = data[topIndex];
                topIndex--;
                data = newdata;
                return element;
            }
        }

        private boolean isFull() {
            return data.length - 1 == topIndex;
        }

        private boolean isEmpty() {
            return topIndex == -1;
        }

        private void output() {
            for (int i = 0; i < data.length; i++) {
                System.out.print(data[i]);
            }
        }

    }

}


 Copy code 

Linked list implementation stack



public class DataStructureUseLinkeListdRealizeStack {

    /**
     *  Use linked list to realize stack 
     *  We first need to implement the linked list , And then realize the stack according to the linked list 
     *
     * @param args
     */
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.print("\n Push  ");
        myStack.output();
        myStack.pop();
        myStack.pop();
        System.out.print("\n Out of the stack  ");
        myStack.output();
        myStack.pop();
//        myStack.pop();// There is no data in the stack 

    }

    public static class MyStack {

        private LinkedList linkedList;

        private MyStack() {
            linkedList = new LinkedList();
        }

        private void push(int element) {
            linkedList.addToFirst(element);
        }

        private int pop() {
            if (linkedList.isEmpty()) {
                throw new IndexOutOfBoundsException(" There is no data in the stack ");
            } else {
                return linkedList.deleteFirst();
            }
        }

        private void output() {
            linkedList.output();
        }

        /**
         *  node 
         */
        private class Node {
            private int data;
            private Node next;

            private Node(int data) {
                this.data = data;
            }
        }

        /**
         *  Linked list 
         */
        private class LinkedList {
            private Node first;

            private LinkedList() {
                first = null;
            }

            private boolean isEmpty() {
                return first == null;
            }

            /**
             * @param element
             */
            private void addToFirst(int element) {
                Node newNode = new Node(element);
                newNode.next = first;
                first = newNode;
            }

            private int deleteFirst() {
                Node firstNode = first;
                first = first.next;
                return firstNode.data;
            }

            private void output() {
                Node currentNode = first;
                while (currentNode != null) {
                    System.out.print(currentNode.data);
                    currentNode = currentNode.next;
                }
            }

        }

    }

}


 Copy code 

The characteristics of the stack

advantage : Because the structure of storing data in the stack is to extract the data put in later ( Last in, first out ), When the latest data is needed for some operations , Choosing a stack as the data structure is the most appropriate .

shortcoming : When accessing any data in the stack , We need to start with the latest data , Low efficiency .

A common collection of stack implementations

Stack yes Vector A subclass of , It implements a standard LIFO stack .

queue (Queue)

queue , Also known as queue (queue), An abstract data type in computer science , First in, first out (FIFO, First-In-First-Out) The linear table . In concrete application, it is usually realized by linked list or array . Queues are only allowed on the back end ( be called rear) Insert operation , On the front end ( be called front) Delete operation .

Queues operate like stacks , The only difference is that queues only allow new data to be added at the back end .

The queue is like a one-way tunnel on a highway , All vehicles passing through the tunnel are only allowed to enter from the tunnel entrance , Drive out of the tunnel exit , Retrograde... Is not allowed . therefore , To get the vehicle out of the tunnel , Only in the order they enter the tunnel , First in vehicles first out , After entering the vehicle, drive out , No vehicle can jump over the vehicle in front of it and drive out in advance .

Basic operations of queues

The basic operation of queue is just entering and leaving the queue . The team (enqueue) It's putting new elements in the queue , Elements are only allowed at the end of the team , The next position of the new element will be the new tail . Out of line operation (dequeue) It's to get elements out of the queue , You are only allowed to move elements on the head side of the team , The last element of the exit element will become the new team leader . Queue is also an array and linked list, which can realize the operation of queue , We also implement this queue from array and linked list .

Array implementation queue


public class DataStructureUseArrayRealizeQueue {

    /**
     *  Here we use arrays to implement queues ( Circular queue )
     *
     * @param args
     */
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue(4);
        myQueue.enQueue(1);
        myQueue.enQueue(2);
        myQueue.enQueue(3);
        myQueue.enQueue(4);
        System.out.print("\n The team  ");
        myQueue.output();
//        myQueue.enQueue(5);//  Length of queue exceeded 
        myQueue.deQueue();
        myQueue.deQueue();
        System.out.print("\n Out of the team  ");
        myQueue.output();
        myQueue.enQueue(6);
        System.out.print("\n Join the team again  ");
        myQueue.output();
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.deQueue();
//        myQueue.deQueue();//  The queue is empty 
    }

    public static class MyQueue {

        private int[] data;
        private int front;// Team head 
        private int rear;// A party 

        private MyQueue(int capacity) {
            this.data = new int[capacity + 1];// The position of the pointer at the end of the line is always empty 1 position , So the maximum capacity of the queue is smaller than the length of the array  1. Therefore, when we implement here, we use... When setting the array length capacity + 1
            front = rear = 0;
        }

        /**
         *  The team 
         *
         * @param element
         */
        private void enQueue(int element) {
            if (isFull()) {
                throw new IndexOutOfBoundsException(" Length of queue exceeded ");
            } else {
                data[rear] = element;
                rear = (rear + 1) % data.length;// Here is the circular queue , So not directly rear++, But through the loop of the array to find the next team tail subscript 
            }
        }

        /**
         *  The queue is full , Whether the queue is full is determined by dividing the end of the queue subscript by the length of the array, and whether the remainder and the head of the queue subscript are equal 
         *
         * @return
         */
        private boolean isFull() {
            return (rear + 1) % data.length == front;
        }

        /**
         *  Out of the team 
         */
        private int deQueue() {
            if (isEmpty()) {
                throw new IndexOutOfBoundsException(" The queue is empty ");
            } else {
                int element = data[front];
                front = (front + 1) % data.length;
                return element;
            }
        }

        /**
         *  empty 
         *
         * @return
         */
        private boolean isEmpty() {
            return front == rear;
        }

        private void output() {
            // Start from scratch , The accumulation here is cyclic 
            for (int i = front; i != rear; i = (i + 1) % data.length) {
                System.out.print(data[i]);
            }
        }
    }

}


 Copy code 

Linked lists implement queues



public class DataStructureUseLinkeListdRealizeQueue {

    /**
     *  Use linked list to realize queue 
     *
     * @param args
     */
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.enQueue(1);
        myQueue.enQueue(2);
        myQueue.enQueue(3);
        myQueue.enQueue(4);
        System.out.print("\n The team  ");
        myQueue.output();
        myQueue.deQueue();
        myQueue.deQueue();
        System.out.print("\n Out of the team  ");
        myQueue.output();
        myQueue.enQueue(6);
        System.out.print("\n Join the team again  ");
        myQueue.output();
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.deQueue();
        System.out.print("\n Get out of the team again  ");
        myQueue.output();
    }

    public static class MyQueue {

        private Node head;
        private Node rear;
        private int size;

        private MyQueue() {
            head = null;
            rear = null;
            size = 0;
        }

        private void enQueue(int element) {
            Node newNode = new Node(element);
            if (isEmpty()) {
                head = newNode;
            } else {
                rear.next = newNode;
            }
            rear = newNode;
            size++;
        }

        private boolean isEmpty() {
            return head == null;
        }

        private int deQueue() {
            if (isEmpty()) {
                throw new NullPointerException(" Queue has no data ");
            } else {
                Node node = head;
                head = head.next;
                size--;
                return node.data;
            }
        }

        private void output() {
            Node node = head;
            while (node != null) {
                System.out.print(node.data);
                node = node.next;
            }
        }

        /**
         *  node 
         */
        private class Node {
            private int data;
            private Node next;

            private Node(int data) {
                this.data = data;
            }
        }

    }


}

 Copy code 

Characteristics of the queue

Queue is a special linear structure . It's only allowed at the front of the table (front) Delete operation , And at the back end of the table (rear) Insert operation . The end of the insertion operation is called the tail of the queue , The end of the delete operation is called the queue head . The first element inserted in the queue will also be deleted first , The corresponding last inserted element will be deleted finally . So the queue is also called “ fifo ”(FIFO—first in first out) The linear table , And stack (FILO-first in last out) Just the opposite .

A common collection of queue implementations

  • deque :Deque
  • The blocking interface is not implemented :
    • LinkedList : Realized Deque Interface , Restricted queues
    • PriorityQueue : Priority queue , Essentially, maintain a sequence table . It can be sorted naturally or passed comparator Constructor to implement custom sorting .
    • ConcurrentLinkedQueue: Based on the list Thread safe queues . Add delete O(1) lookup O(n)
  • Implement the blocking interface : Realization BlockingQueue Five blocking queues of the interface , Its characteristics : When a thread is blocked , Instead of adding or deleting elements directly , But when there is space or element , To operate .
    • ArrayBlockingQueue: Bounded queues based on arrays
    • LinkedBlockingQueue: Unbounded queue based on linked list
    • PriorityBlockingQueue: Unbounded queue based on priority
    • DelayQueue: Queue based on time priority
    • SynchronousQueue: Queue without container inside More special -- Its unique thread one-to-one pairing communication mechanism

The main task scenario of queue is task scheduling and control 、 Handle concurrent tasks

Hash table ( Also called hash table )(Hash)

Hash table (Hash table, Also called hash table ), Is according to the key (Key) Direct access to data structures in memory storage locations . in other words , It works by calculating a function of the key value , Map the data you want to query to a location in the table to access records , This speeds up the search . This mapping function is called the hash function , The array that holds the records is called a hash table .

A popular example is , To find someone's number in the phone book , You can create a list of people in alphabetical order ( That is to establish a person's name {\displaystyle x}x To the initial {\displaystyle F(x)}F(x) A functional relation of ), The initial is W Find in table of “ king ” Last name's phone number , Obviously, it's much faster than direct search . We use people's names as keywords ,“ Taking the first letter ” It's the function rule of the hash function in this example {\displaystyle F()}F() , The hash table of the alphabet . The key words and function rule can be determined arbitrarily in theory .

Hash function ( Also called hash functions )

Hash function ( English :Hash function) Also known as hash algorithm 、 hash function , It's about creating small numbers from any kind of data “ The fingerprint ” Methods . Hash functions compress messages or data into digests , Make the amount of data smaller , Fix the format of the data . This function scrambles and mixes the data , Recreate a value called hash (hash values,hash codes,hash sums, or hashes) The fingerprints of . Hash values are usually represented by a short string of random letters and numbers .[1] Good hash functions rarely have hash conflicts in the input field . In hash tables and data processing , Don't suppress conflicts to differentiate data , It makes database records more difficult to find .

Now , Hashing algorithms are also used to encrypt passwords stored in the database (password) character string , Because the hash value calculated by the hash algorithm (Hash Value) With irreversible ( Can't reverse calculate back to the original value ) The nature of , Therefore, it can effectively protect the password .

  • Common hash function
    • direct addressing : Take the key or a linear function value of the key as the hash address . namely hash(k)=k or hash(k)=a*k+b, among a,b Constant ( This hash function is called its own function )
    • Digital analysis : Suppose the keyword is with r A number based on , And the possible keywords in the hash table are known in advance , The hash address is composed of several digits of the keyword .
    Square with the middle method : The middle bits after the keyword is squared are the hash addresses . In general, when selecting hash function, you may not know all about keywords , Which of them is not necessarily appropriate , And the middle digits of a number squared are related to each bit of the number , Thus, the hash address obtained by randomly distributed keywords is also random . The number of digits taken depends on the table length .
    • Folding method : Divide keywords into parts with the same number of digits ( The number of digits in the last part can be different ), And then you take the sum of these parts ( Give up the carry ) As a hash address .
    • Random number method : Use rand() Equal random function construction .
    • Division and remainder : The keyword is not longer than the hash table m Number of numbers p The remainder after division is the hash address . namely hash(k)=k mod p,p< =m. Not only can the keyword be modeled directly , It can also be done in folding 、 Take the module after the operation of the middle square . Yes p The choice of is very important , Usually take the prime number or m, if p Bad choice , It's prone to conflict .

Resolution of hash conflicts

  • Open address method :key After hashing , It is found that the local value has been occupied , You can add... To this address continuously 1, Until you encounter an empty address .

  • Then the hash method : happen “ Collision ” after , But for key Then hash part of the .

  • Chain address : The chain address method is by putting key Mapped to the same address value, Make a linked list

The basic operation of a hash table

The basic operation of hash table involves the method of adding, deleting, modifying and querying , Let's analyze... One by one

  • increase (put)/ Change : Is to insert a new key value pair into the hash table ( stay JDK In is called Entry). for example : We're going to call hash.put("001"," Zhang San "), It means to insert a group key=001.value=" Zhang San " The key/value pair . Let's analyze the specific steps , First, we need to hash key=001 Convert to array subscript index; If the subscript at this time index There is no element in the corresponding position , So let's just take this Entry Fill to array subscript index The location of the value of ; At this time, let's think about , Because the array length is limited , When inserted Entry More and more times , Different key The subscripts obtained by hashing may be the same , When the same subscript appears index When , How do we deal with this situation , This involves hash conflicts , We also listed the methods to solve hash conflicts above .HashMap The chain address method is used in . At this time, let's think again , Because the array length is set when instantiating the array , In contrast, the query of linked list will be very slow when the amount of data is large . When the hash table stores more and more key value pairs , We're going to consider expanding , When it comes to capacity expansion, it involves the load factor ( loadFactor The load factor is related to the expansion mechanism , It means that if the capacity of the current container , It's up to the maximum we set , We are about to start the expansion operation . Take an example to explain , Avoid Xiaobai not understand : For example, the current container capacity is 16, The load factor is 0.75,16* 0.75=12, in other words , When the capacity reaches 12 We will expand the capacity when we need to . His role is simple , It is equivalent to the threshold of a capacity expansion mechanism )
  • check (get): The read operation is through the given Key, In the hash table Find the corresponding Value. for example : We're going to call hash.get("001"), It means to find Key=001 Of Entry The corresponding value in the hash table . Let's also analyze how to do it By hash function , hold Key Convert to array subscript index; Find array subscript index The corresponding element , If this element's Key=001, So we found ; If this Key No 001 It doesn't matter , Because each element of the array corresponds to a linked list , We can slowly look down the linked list , See if you can find a connection with Key Matching nodes .
  • Delete (remove): If you delete it, you can also find key The hash function of finds the corresponding subscript and then deletes it


public class DataStructureHash {

    /**
     *  Here we simply implement a hash table , Refer to the specific implementation of all aspects HashMap
     *
     * @param args
     */
    public static void main(String[] args) {
        MyHash myHash = new MyHash();
        myHash.put(0, 1);
        myHash.put(1, 2);
        myHash.get(0);
        myHash.remove(0);
    }


    public static class MyHash {

        private static final int DEFAULT_INITAL_CAPACITY = 5;// Defines the default length 

        private static final float LOAD_FACTOR = 0.75f;// Load factor 

        private Entry[] table = new Entry[DEFAULT_INITAL_CAPACITY];// initialization 
        private int size = 0;// Kazakhstan watch size 
        private int use = 0;// Number of addresses used 

        private class Entry {
            int key;// keyword 
            int value;
            Entry next;// Linked list 

            public Entry(int key, int value, Entry entry)// Constructors 
            {
                this.key = key;
                this.value = value;
                this.next = entry;
            }
        }

        /**
         *
         * @param key
         * @param value
         */
        public void put(int key, int value) {
            int index = hash(key);// adopt hash Method transformation , The direct method is adopted 

            if (table[index] == null)// Indicates that the location is not used 
            {
                table[index] = new Entry(-1, -1, null);
            }

            Entry tmp = table[index];
            if (tmp.next == null)// Indicates that the location is not used 
            {
                table[index].next = new Entry(key, value, null);
                size++;
                use++;
                if (use >= table.length * LOAD_FACTOR)// Determine whether capacity expansion is needed 
                {
                    resize();// Expansion method 
                }
            } else {// Used , Then directly expand the linked list 
                for (tmp = tmp.next; tmp != null; tmp = tmp.next) {
                    int k = tmp.key;
                    if (k == key) {
                        tmp.value = value;
                        return;
                    }
                }

                Entry temp = table[index].next;
                Entry newEntry = new Entry(key, value, temp);
                table[index].next = newEntry;
                size++;
            }

        }


        /**
         *
         *  Delete , The method of deleting the intermediate value of the linked list 
         * @param key
         */
        public void remove(int key)
        {
            int index = hash(key);
            Entry e = table[index];
            Entry pre = table[index];
            if (e != null && e.next != null) {
                for (e = e.next; e != null; pre = e, e = e.next) {
                    int k = e.key;
                    if (k == key) {
                        pre.next = e.next;
                        size--;
                        return;
                    }
                }
            }
        }

        /**
         *  adopt key extract value
         * @param key
         * @return
         */
        public int get(int key)
        {
            int index = hash(key);
            Entry e = table[index];
            if (e != null && e.next != null) {
                for (e = e.next; e != null; e = e.next) {
                    int k = e.key;
                    if (k == key) {
                        return e.value;
                    }
                }
            }
            return -1;
        }

        /**
         *  Number of return elements 
         * @return
         */
        public int size() {
            return size;

        }

        /**
         *  Hash table size 
         * @return
         */
        public int getLength() {
            return table.length;
        }


        /**
         *  Capacity expansion 
         */
        private void resize() {
            int newLength = table.length * 2;
            Entry[] oldTable = table;
            table = new Entry[newLength];
            use = 0;
            for (int i = 0; i < oldTable.length; i++) {
                if (oldTable[i] != null && oldTable[i].next != null) {
                    Entry e = oldTable[i];
                    while (null != e.next) {
                        Entry next = e.next;
                        int index = hash(next.key);
                        if (table[index] == null) {
                            use++;
                            table[index] = new Entry(-1, -1, null);
                        }
                        Entry temp = table[index].next;
                        Entry newEntry = new Entry(next.key, next.value, temp);
                        table[index].next = newEntry;
                        e = next;
                    }
                }
            }

        }

        /**
         *  obtain key The subscript ( hash function )
         * @param key
         * @return
         */
        private int hash(int key) {
            return key % table.length;
        }

    }

}

 Copy code 

The advantages and disadvantages of hash table

advantage : Hash tables are not only fast , Programming is also relatively easy

shortcoming : Hash table also has some disadvantages. It is based on array , After the array is created, it is difficult to expand. When some hash tables are basically filled , The performance degradation is very serious , Therefore, although the program must be clear about how much data will be stored in the table ( Or be prepared to periodically move data to a larger hash table , It's a time-consuming process ). and , There is no easy way to do this in any order 〔 For example, from small to large 〕 Traverse the data items in the table .

A common collection of hash table implementations

HashMap、HashTable、ConcurrentHashMap

Trees (Tree)

Trees ( English :tree) It's an abstract data type (ADT) Or implement the data structure of this abstract data type , It is used to simulate the data set with tree structure . It is from n(n> 0) Finite nodes make up a set with hierarchical relationships . Call it "it". “ Trees ” Because it looks like an upside down tree , That is to say, it is root up , And leaf down . It has the following characteristics :

  • Each node has only a limited number of children or no children ;

  • A node without a parent is called a root node ;

  • Each non root node has and only has one parent node ;

  • Except for the root node , Each sub node can be divided into several disjoint sub trees ;

  • There is no ring road in the tree (cycle)

  • Tree related terms

    • Degree of node : The number of subtrees a node contains is called the degree of the node ;
    • The degree of a tree : In a tree , The largest node degree is called the degree of the tree ;
    • Leaf node or terminal node : Zero degree nodes ;
    • Non terminal node or branch node : Nodes with degree not zero ;
    • Parent node or parent node : If a node has child nodes , This node is called the parent of its child ;
    • Child node or child node : The root node of the subtree that a node contains is called the child node of the node ;
    • Brother node : Nodes with the same parent are called siblings ;
    • Hierarchy of nodes : Starting from the root , The root for the first 1 layer , The child node of the root is the 2 layer , And so on ;
    • depth : For any node n,n From root to n Unique path length of , The depth of the root is 0;
    • Height : For any node n,n From n The longest path to a leaf , The height of all leaves is 0;
    • Cousin node : The parent nodes on the same layer are cousins of each other ;
    • The ancestor of node : From the root to all nodes on the branch through which the node passes ;
    • descendants : Any node in a subtree with a node as its root is called the descendant of the node .
    • The forest : from m(m>=0) A collection of trees that do not intersect each other is called a forest ;

Common trees

Binary tree (binary tree) It's a special form of trees . binary , seeing the name of a thing one thinks of its function , Each node of this tree has at most 2 A child node . Be careful , There are at most 2 individual , Maybe it's just 1 individual , Or no child nodes . Two child nodes of a binary tree node , One is called the left child (left child) , One is called the right child Son (right child). The order of the two child nodes is fixed , It's like a person's left hand is his left hand , one 's right hand It's the right hand , Cannot be reversed or confused .

Full binary tree : All non leaf nodes of a binary tree have left and right children , And all the leaf nodes are at the same level , So this tree is full of binary trees .

Perfect binary tree : To a n A binary tree of nodes , Number... In hierarchical order , Then all nodes are numbered from 1 To n. If all nodes of this tree and full binary trees of the same depth are numbered from 1 To n The node positions of are the same , Then this binary tree is a complete binary tree .

AVL Trees :AVL Tree is the first self balanced binary search tree . stay AVL The maximum height difference between two subtrees of any node in the tree is 1, So it's also known as the height balance tree . Adding and deleting may require one or more tree rotations to rebalance the tree .

Binary trees contain many special forms , Every form has its own function , But its main application is also in the two aspects of search operation and maintaining relative order .

Traversal of binary tree

From a broader perspective , Traversal of binary trees can be divided into two categories .

  • Depth-first traversal ( The former sequence traversal [--- The output order is the root node 、 The left subtree 、 Right subtree ---]、 In the sequence traversal [--- The output order is the left subtree 、 The root node 、 Right subtree ---]、 After the sequence traversal [--- The output order is the left subtree 、 Right subtree 、 The root node ---])
  • Breadth first traversal ( Sequence traversal [--- Sequence traversal , seeing the name of a thing one thinks of its function , It is a binary tree according to the hierarchical relationship from root node to leaf node , Traverse each node horizontally layer by layer .---])

A common collection of tree implementations

TreeMap、TreeSet

Pile up (Heap)

Pile up ( English :Heap) It is a special complete binary tree in computer science . If the following characteristics are satisfied , It's called a heap :“ Given any node in the heap P and C, if P yes C The parent node of , that P The value of will be less than or equal to ( Or greater than or equal to )C Value ”. If the value of the parent node is always less than or equal to the value of the child node , This heap is called the minimum heap (min heap); conversely , If the value of the parent node is always greater than or equal to the value of the child node , This heap is called the maximum heap (max heap). The top node in the heap , It's called the root node (root node), The root node itself does not have a parent node (parent node).

Advantages and disadvantages of heap

advantage : Insert , Delete fast , Access to the largest data items is fast

shortcoming : Slow access to other data items

Practical application of heap

Binary heap is the basis of heap sorting and priority queue , Pay attention to the practical application of some priority queues in the project

A common collection of heap implementations

no

chart (Graph)

chart ( English :graph) It's an abstract data type , The concepts of undirected graph and directed graph used to realize graph theory in Mathematics .

The data structure of a graph contains a finite element ( May be variable ) As a node set , And a disordered pair ( Corresponding undirected graph ) Or orderly to ( Corresponding digraph ) Set of as edges ( A directed graph is also called an arc ) Set . Nodes can be part of the graph structure , It can also be an external entity represented by an integer subscript or reference .

The data structure of the graph may also contain values associated with each edge (edge value), For example, a label or a value ( That's the weight ,weight; It means the cost 、 Capacity 、 Length etc. ).

Advantages and disadvantages of graph

advantage : Modeling the real world

shortcoming : Some algorithms are slow and complex

Common data structure of figure

Adjacency list : Nodes are stored as records or objects , And create a list for each node . These lists can store the rest of the information by node ; for example , If each edge is also an object , The edge is stored in the list of edge start points , And store the end point of the edge in the object itself .

Adjacency matrix : A two-dimensional matrix , Where rows and columns represent the start and end of the edge respectively . Values on vertices are stored externally . The value of the edge can be stored in the matrix .

Correlation matrix : A two-dimensional matrix , Lines represent vertices , The list shows the edge . The values in the matrix are used to identify the relationship between vertices and edges ( Starting point 、 It's the end 、 Don't wait on this side )

Common collection source code analysis

Common collections are basically implemented around the data structure ( Source level analysis ), Must master ArrayList、LinkedList、HashMap

ArrayList、LinkedList、Vector、HashSet、LinkedHashSet、TreeSet、HashMap、HashTable、TreeMap、LinkedHashMap AbstractQueue、BlockingQueue、Deque It's best to learn some

copyright notice
author[madreain],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270344145545.html

Random recommended