Data Structures and Algorithms (Java)

The paper

One of the most common problems encountered during programming is performance bottlenecks. A lot of time we think about how to scale horizontally, but we forget the most basic question is whether the system has really reached a bottleneck. Performance bottlenecks are usually represented by excessive resource consumption and insufficient performance of external processing systems. Or it may consume less resources but still not respond as fast as it needs to. The way to tune it is to look for code that is overusing resources and for code that is underusing resources but executing slowly. The basic decision height is compared with the car, usually do not understand the gearbox, engine principle but also can drive, the same person who does not understand data structure and algorithm can also program. Many people think that basic data structures and operations have been encapsulated in a high-level language, can directly call library functions, so is it necessary to learn data structures?

Data structure + algorithm = program

Usually in the program, when encountering a practical problem, make full use of the data structure, store the data and its relationship effectively in the computer, and then choose the appropriate algorithm strategy, and implement it efficiently with the program, which is the main way to improve the performance of the program.

• How to store data efficiently, what algorithmic complexity is generated by different data structures, and is there a better storage method to improve the efficiency of the algorithm?

If you don’t have this knowledge, how can you do this? If the original call, how to achieve efficient implementation of the program? And all application implementations rely on foundations, which are data structures and algorithms. Understanding this is the only way to be fearless of any technological change. All say base determines height!

Basic concepts

Data structure represents the storage and organization form of data in the computer, mainly describes the relationship between data elements and positions. Choosing proper data structure can improve the running efficiency (time complexity) and storage efficiency (space complexity) of computer programs.

Three levels of data structure:

1. Logical structure – Abstraction layer: Mainly describes the logical relationships between data elements

• Set structure (set) : All elements belong to the same population and have no relationship other than belonging to the same set. The collection structure does not emphasize any correlation between elements.
• Linear structure (table) : Data elements have a one-to-one context. A structure must have a unique first element and a unique tail element.
• Tree structure (tree) : One-to-many relationships between data elements
• Mesh structure (graph) : There is a many-to-many relationship between data elements in a graph or mesh structure

2. Physical structure – Storage layer: Mainly describes the location relationship between data elements

• Sequential structure: Sequential structure uses a group of contiguous storage units to store each logically adjacent element in sequence. Advantages: You only need to apply for the memory space for storing data. Subscript access and random access are supported. Disadvantages: Continuous space must be allocated statically, and the utilization of memory space is low. Insertion or deletion may require moving a large number of elements, which is inefficient

• Chain structure: Instead of using contiguous storage space to hold the elements of the structure, a chain storage structure constructs a node for each element. In addition to storing the data itself, a node also needs to store a pointer to the next node. Advantages: Not using continuous storage space leads to high memory space utilization, overcomes the disadvantage of the sequential storage structure to predict the number of elements, does not need to move a large number of elements when inserting or deleting elements. Disadvantages: Requires extra space to express logical relationships between data, does not support subscript and random access.

• Index structure: In addition to storage node information, additional index tables are created to mark node addresses. An index table consists of several index items. Advantage: is to use the node index number to determine the node storage address, retrieval speed block ‘disadvantage: added additional index table, will occupy more storage space.

• Hash structure: The storage address of a node is determined by the key value of the node. Hashing can be used for storage as well as lookup. Advantages: Hash is a development of array storage. Some elements of the storage array are used as the input of the mapping function, and the output of the mapping function is the location of the storage data. Compared with array, the data access speed of hash is higher than array disadvantages: Sorting is not supported, generally requires more space than linear table storage, and record keys cannot be repeated.

3. Operational structure – Implementation layer: It describes how to implement data structure

• Allocate resources, build structures, release resources
• Insert and delete
• Get and traverse
• Modify and sort

Data structure comparison

Common data structures:

Data structure selection:

O symbol

O time complexity is expressed in the algorithm, which is very useful in analyzing the complexity of the algorithm. Common ones are:

1. O(1): The lowest complexity, regardless of the size of the data, the time is the same, can be obtained after a calculation. The hash algorithm is a classic O(1).
2. O(n): linear, n represents the amount of data, equivalent increases, time also increases, common traversal calculation method
3. O (n squared): square, indicating that the time is n square times, when you see the loop nested loop, basically this algorithm is square, such as: bubble sort
4. O(log n): logarithm, usually a^xIs equal to n, so x is called log base A of n, which is x is equal to log_aN, where a is usually 2, for example, if the number increases by 8 times, the time is only increased by 3 times. Binary search is a logarithmic algorithm, eliminating half at a time
5. O(n log n): Linear logarithm, is n times log n, according to the above data increase 8 times, 8*3=24 times, merge sort is linear logarithm algorithm

Array

In Java, arrays are collections of the same data type, but only the same data type.

// Only the type and length are declaredData type [] Array name =newData type [array length];// Declare the type, initialize the assignment, size is determined by the number of elementsData type [] Array name = {array element1, array elements2. }Copy the code

Fixed size, cannot dynamically expand (initialization to large, waste; Insert fast, delete and find slow

Analog implementation

public class Array {
    private int[] intArray;

    private int elems;

    private int length;

    public Array(int max) {
        length = max;
        intArray = new int[max];
        elems = 0;
    }

    /** * add *@param value
     */
    public void add(int value){
        if(elems == length){
            System.out.println("error");
            return;
        }
        intArray[elems] = value;
        elems++;
    }


    /** * find *@param searchKey
     * @return* /
    public int find(int searchKey){
        int i;
        for(i = 0; i < elems; i++){
            if(intArray[i] == searchKey)
                break;
        }
        if(i == elems){
            return -1;
        }
        return i;
    }

    /** * delete *@param value
     * @return* /
    public boolean delete(int value){
        int i = find(value);
        if(i == -1) {return false;
        }
        for (int j = i; j < elems-1; j++) {
            // Move the data forward
            intArray[j] = intArray[j + 1];
        }
        elems--;
        return true;
    }

    /** * update *@param oldValue
     * @param newValue
     * @return* /
    public boolean update(int oldValue,int newValue){
        int i = find(oldValue);
        if(i == -1) {return false;
        }
        intArray[i] = newValue;
        return true;
    }

    /** * displays all */
    public void display(a){
        for(int i = 0 ; i < elems ; i++){
            System.out.print(intArray[i]+"");
        }
        System.out.print("\n");
    }


    /** * Bubble sort * maximum/minimum number of bubbles per run * Number of runs per run: Total number of runs - number of runs (bubbles) */
    public void bubbleSort(a){
        for(int i = 0; i < elems-1; i++){// Sort n-1 times
            System.out.println("The first"+(i+1) +"Trip.");
            for(int j = 0; j < elems-i-1; j++){// The number of runs (n- I) -1 is used to prevent the subscript from crossing the boundary
                if(intArray[j] > intArray[j+1]) {// Control whether to press big bubble or small bubble
                    int temp = intArray[j];
                    intArray[j] =  intArray[j+1];
                    intArray[j+1] = temp; } display(); }}}/*** * Select sort * Select a maximum/minimum number per run * Number of runs per run: Total number - Number of runs (selected) */
    public void selectSort(a){
        for(int i = 0; i < elems-1; i++) {// Sort n-1 times
            int min = i;
            for(int j = i+1; j < elems; j++){ // Select one number per run, -1 times
                if(intArray[j] < intArray[min]){ min = j; }}if(i ! = min ){inttemp = intArray[i]; intArray[i] = intArray[min]; intArray[min] = temp; } display(); }}/** * Insert sort * selects a number to be inserted per run * each run places the number to be inserted after a greater/smaller number */
    public void insertSort(a){
        int j;
        for(int i = 1; i < elems; i++){
            int temp = intArray[i];
            j = i;
            while (j > 0 && temp < intArray[j-1]){
                intArray[j] = intArray[j-1];
                j--;
            }
            intArray[j] = temp;
        }
        display();
    }

    public static void main(String[] args) {
        Array array = new Array(10);
        array.add(6);
        array.add(3);
        array.add(8);
        array.add(2);
        array.add(11);
        array.add(5);
        array.add(7);
        array.add(4);
        array.add(9);
        array.add(10);
// array.bubbleSort();
// array.selectSort();
        array.insertSort();
// array.display();
// System.out.println(array.find(4));
// System.out.println(array.delete(1));
// array.display();
/ / System. Out. Println (array. The update (2, 6));
// array.display();}}Copy the code

Stack

• Stack (stack) is also called stack or stack, stack as a data structure, it stores data in accordance with the principle of “first in, last out”, the first data is pushed into the bottom of the stack, the last data in the top of the stack
• Stack, a Java subclass of Vector, defines only the default constructor to create an empty Stack.
• A stack is a collection of elements that contains two basic operations: push, which pushes elements onto the stack, and POP, which removes the top element.
• Follow LIFO.
• Time complexity:
• Index:O(n)
• Search:O(n)
• Insert:O(1)
• Removed:O(1)

Stack()
Copy the code

Analog implementation

public class Stack {
    // Tip: You can usually use the stack to reverse string order. You can also use the stack to determine whether delimiters match, such as 
      
       .
      [b{c}]>

    /** Sequential stack based array implementation, linear implementation of continuous storage, need to initialize the capacity **/
    // Fix the data type
    //private int[] array;
    // Dynamic data type
    private Object[] objArray;

    private int maxSize;

    private int top;

    public Stack(a) {}public Stack(int maxSize) {
        if(maxSize > 0){
            objArray = new Object[maxSize];
            this.maxSize = maxSize;
            top = -1;
        }else{
            throw new RuntimeException("Error initializing size: maxSize="+ maxSize); }}/** * push *@param obj
     */
    public void objPush(Object obj){
        / / capacity
        grow();
        //++ indicates that the value is calculated first and then assigned, with a high priority; after ++ indicates that the value is assigned and then calculated, with a low priority
        objArray[++top] = obj;
    }

    /** * out of the stack *@return* /
    public Object objPop(a){
        Object obj = peekTop();
        // Declare that the original top stack can reclaim space (GC)
        objArray[top--] = null;
        return obj;
    }

    /** * check the top of the stack@return* /
    public Object peekTop(a){
        if(top ! = -1) {return objArray[top];
        }else{
            throw new RuntimeException("stack is null"); }}/** * Dynamic capacity expansion */
    public void grow(a){
        // << left shift operator, 1 means multiplied by 2 to the 1
        if(top == maxSize-1){
            maxSize = maxSize<<1; objArray = Arrays.copyOf(objArray,maxSize); }}/** Based on the chain storage, discontinuous storage nonlinear implementation **/
    private class Node<Object>{
        private Object data;

        private Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next; }}private Node nodeTop;

    private int size;

    public void nodePush(Object obj){
        // The top of the stack points to the new element, and the next of the new element points to the old top element
        nodeTop = new Node(obj,nodeTop);
        size++;
    }

    public Object nodePop(a){
        Node old = nodeTop;
        // Declare that the original top stack can reclaim space (GC)
        old.next = null;
        // The top of the stack points to the next element
        nodeTop = nodeTop.next;
        size--;
        return old.data;
    }

    @Override
    public String toString(a) {
        StringBuilder sb = new StringBuilder("[");
        for(Node<Object> node = nodeTop; node ! =null; node = node.next){
            sb.append(node.data.toString() + "");
        }
        return sb.toString()+"]";
    }

    public static void main(String[] args) {
// Stack stack = new Stack(1);
// stack.objPush("abc");
// stack.objPush(123);
// stack.objPush("de");
// stack.objPush("cd");
// stack.objPush("er");
// stack.objPush("hello");
// stack.objPush(666);
// stack.objPush(545);
// stack.objPush("word");
// while (stack.top ! = 1) {
// System.out.println(stack.objPop());
/ /}
// System.out.println(stack.peekTop());
        Stack stack = new Stack();
        stack.nodePush("111");
        stack.nodePush("222");
        stack.nodePush("aaa");
        stack.nodePush("bbb");
        System.out.println(stack);
        while (stack.size > 1) System.out.println(stack.nodePop()); System.out.println(stack); }}Copy the code

Queue

• A queue is a collection of elements that contains two basic operations: the enqueue operation is used to insert elements into the queue, and the dequeue operation is used to remove elements from the queue.
• Follow the first in, first out (FIFO) principle.
• Time complexity:
• Index:O(n)
• Search:O(n)
• Insert:O(1)
• Removed:O(1)
  

  

public class Queue {
    /*** * 1. Unidirectional Queue: Data can be inserted at one end and deleted at the other end. * 2. Bidirectional queue (Deque) : Each end can insert data and delete data operations. * * Unlike a stack, data in a queue does not always start at the 0 subscript of the array. * The alternative is to move the pointer to the head and tail of the queue. * To avoid the queue being full and unable to insert new data, we can loop the tail pointer back to the beginning of the array, also known as the "loop queue". * * /
    // Unidirectional circular queue, sequential storage structure implementation
    private Object[] objQueue;
    // Queue size
    private int maxSize;
    The top / /
    private int top;
    / / at the bottom of the
    private int bottom;
    // The actual element
    private int item;

    public Queue(int size) {
        maxSize = size;
        objQueue = new Object[maxSize];
        top = 0;
        bottom = -1;
        item = 0;
    }

    /** * join the team *@param obj
     */
    public void add(Object obj){
        if(item == maxSize){
            throw new RuntimeException(obj+" add error, queue is full");
        }
        // loop the queue, with the subscript controlling the position of the first and the last queue
        if(bottom == maxSize-1){
            bottom = -1;
        }
        objQueue[++bottom] = obj;
        item++;
    }

    /** ** out of *@return* /
    public Object out(a){
        if(item == 0) {throw new RuntimeException("queue is null");
        }
        Object obj = objQueue[top];
        // Declare that the original top stack can reclaim space (GC)
        objQueue[top] = null;
        top++;
        // reset the subscript
        if(top == maxSize){
            top = 0;
        }
        item--;
        return obj;
    }

    // Chain storage structure implementation
    private class NodeQueue<Object>{
        private Object data;

        private NodeQueue next;

        public NodeQueue(Object data, NodeQueue next) {
            this.data = data;
            this.next = next; }}// The queue header goes out
    private NodeQueue queueTop;
    // the end of the queue
    private NodeQueue queueBottom;
    // Queue size
    private int size;

    public Queue(a) {
        queueTop = null;
        queueBottom = null;
        size = 0;
    }

    /** * join the team *@param obj
     */
    public void addNodeQueue(Object obj){
        if(size == 0){
            queueTop = new NodeQueue(obj,null);
            // point to the same storage address
            queueBottom = queueTop;
        }else{
            NodeQueue<Object> nodeQueue = new NodeQueue(obj,null);
            // Make the next of the last node point to the new node
            queueBottom.next = nodeQueue;
            // use the new node as the tail node
            queueBottom = nodeQueue;
        }
        size ++;
    }

    /** ** out of line *@return* /
    public Object removeNodeQueue(a){
        if(size == 0) {throw new RuntimeException("queue is null");
        }
        NodeQueue nodeQueue = queueTop;
        queueTop = queueTop.next;
        // Next can reclaim space (GC)
        nodeQueue.next = null;
        size--;
        return nodeQueue.data;
    }


    @Override
    public String toString(a) {
        StringBuilder sb = new StringBuilder("{");
        for(NodeQueue nodeQueue = queueTop ; nodeQueue ! =null ; nodeQueue = nodeQueue.next){
            sb.append(nodeQueue.data.toString()+"");
        }
        return sb.toString()+"}";
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.addNodeQueue("123");
        queue.addNodeQueue("abc");
        queue.addNodeQueue("ddd"); System.out.println(queue); queue.removeNodeQueue(); System.out.println(queue); queue.removeNodeQueue(); queue.removeNodeQueue(); System.out.println(queue); }}Copy the code

Linked List

• A linked list is a linear collection of nodes. Each Node can point to other nodes with Pointers. It is a data structure that contains multiple nodes and can be used to represent sequences.
• Unidirectional linked list: A linked list in which the node points only to the next node and the last node points to null.
• Bidirectional linked list: where each node has two Pointers p and n, such that P points to the previous node and N points to the next node; The n pointer to the last node points to null.
• Circular list: A list in which each node points to the next node and the last node points to the first node.
• Time complexity:
  • Index:O(n)
  • Search:O(n)
  • Insert:O(1)
  • Removed:O(1)
    

    

public class LinkedList {
    /*** * lists typically consist of a series of nodes, each containing arbitrary instance data fields and one or two "links" to the location of the previous or next node */
    private Node head; / / head
    private Node tail; / / list the tail
    private int size; / / the number of nodes

    /** ** double - ended list */
    public class Node{
        private Object data;
        private Node prev; / / a
        private Node next; / / the next

        public Node(Object data) {
            this.data = data; }}public LinkedList(a) {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /** * Add data to the list header *@param object
     */
    public void addHead(Object object){
        Node node = new Node(object);
        if(size == 0){
            head = node;
            tail = node;
            size++;
        }else{ head.prev = node; node.next = head; head = node; size++; }}/**
     * 删除头
     */
    public void deleteHead(a){
        // The header points to the next, and a null prev indicates the head of the list
        if(size ! =0){
            head.prev = null; head = head.next; size--; }}/** * Add data to the end of the list *@param object
     */
    public void addTail(Object object){
        Node node = new Node(object);
        if(size == 0){
            head = node;
            tail = node;
            size++;
        }else{ node.prev = tail; tail.next = node; tail = node; size++; }}/** * delete the tail */
    public void deleteTail(a){
        // The tail points to the previous one, and a next value of null indicates the tail of the list
        if(size ! =0){
            tail.next = null; tail = tail.prev; size--; }}/** * Display data */
    public void display(a){
        Node node = head;
        while (size > 0){
            System.out.print("["+node.data+"- >"); node = node.next; size--; }}public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addHead("123");
// linkedList.addHead("abc");
// linkedList.addHead("%?" );
// linkedList.addTail("+_+");
// linkedList.addTail("hello");
        linkedList.addTail("word"); linkedList.deleteHead(); linkedList.deleteTail(); linkedList.display(); }}Copy the code

Binary Tree

Binary tree (consisting of a root node and two disjoint left and right subtrees called root nodes respectively) a binary tree is a tree data structure in which each node contains at most two nodes: the left and right children.

• Full binary tree: Each node in the tree contains only 0 or 2 nodes.
• Perfect Binary Tree: Each leaf node ina Binary Tree has two child nodes of the same height.
• Complete binary tree: Except the last layer, the number of nodes on each layer reaches the maximum value; Only a few nodes on the right are missing at the last layer.
  

  

  

  Red-black tree (five elements per node, color (if a node is red, its two sons are black), key value, left child, right byte, parent)

Heap

• Heap (also known as priority queue (queue + collation), Figure 1 maximum heap, Figure 2 Minimum heap)
• A heap is a special tree-based data structure that satisfies certain characteristics. The key values of all parent nodes in the heap meet the same sorting conditions. More precisely, heaps can be divided into maximum heap and minimum heap. In the maximum heap, the key value of the parent node is always greater than or equal to the value of the child node, and the maximum value of the whole heap is stored at the root node. In the minimum heap, the parent node’s key value is always less than or equal to that of its children, and the minimum value of the entire heap is stored at the root node.
• Time complexity:
  • Maximum/minimum access value:O(1)
  • Insert:O(log(n))
  • Remove Max/min:O(log(n))
    

    

Hashing

• Hashes can map data of arbitrary length to data of fixed length. A hash function returns the hash value, and if two different keys get the same hash value, this phenomenon is called a collision.
• Hash Map: A Hash Map is a data structure that establishes relationships between keys and values. A Hash Map can use Hash functions to convert keys into subscripts in buckets or slots to optimize the search speed for target values.
• To solve collision
  • Separate Chaining: In Chaining, each bucket is independent of each other and contains a list of indexes. The time complexity of the search operation is the sum of the bucket search time (fixed time) and the traversal time of the list.
  • Open Addressing: In Open Addressing, when a new value is inserted, it is determined whether the hash bucket corresponding to that value exists, and if so, the next possible location is chosen according to some algorithm until an address is found that is not yet occupied. The open address method also means that the position of an element is not always determined by its hash value.

Graph

• A graph is an abstract data type consisting of a many-to-many relationship between data elements and a set of basic operations.
  • Undirected Graph: An Undirected Graph has a symmetric adjacency matrix, so that if there is an edge from node U to node V, then there is an edge from v to u.
  • Directed Graph: The adjacent matrix of a Directed Graph is asymmetric, i.e. the presence of edges from u to V does not mean that edges from V to u must exist.

algorithm

The sorting

Quick sort

• Stability: no
• Time complexity:
  • Optimal time:O(nlog(n))
  • Worst time:O(n^2)
  • Average time:O(nlog(n))

Merge sort

• Merge sort is a typical divide-and-conquer algorithm, which continuously divides an array into two parts, sorts the left and right subarrays respectively, and then merges the two arrays into a new ordered array.
• Stability:
• Time complexity:
  • Optimal time:O(nlog(n))
  • Worst time:O(nlog(n))
  • Average time:O(nlog(n))

Bucket sort

• Bucket sort divides an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue sorting using bucket sort recursively).
• Time complexity:
  • Optimal time:Ω (n + k)
  • Worst time:O(n^2)
  • Average time:Θ (n + k)

Radix sort

• Radix sort is similar to bucket sort in that it splits an array into a finite number of buckets. However, instead of sorting each bucket individually, it directly merges the buckets.
• Time complexity:
  • Optimal time:Ω (nk)
  • Worst time:O(nk)
  • Average time:Θ (nk)

Graph algorithm

Depth-first search

• Depth-first algorithm is an algorithm that traverses child nodes first rather than backtracking.
• Time complexity:O(|V| + |E|)

Breadth-first search

• Breadth-first search is a graph traversal algorithm that preferentially traverses neighbor nodes rather than child nodes.
• Time complexity:O(|V| + |E|)

A topological sort

• Topological ordering is a linear ordering of nodes of a directed graph. If there is an edge from u to V, the subscript of U is considered to precede v.
• Time complexity:O(|V| + |E|)

Dijkstra algorithm

• Dijkstra algorithm is used to solve single-source shortest path problems in directed graphs.
• Time complexity:O(|V|^2)

Bellman – Ford algorithm

• 六四运动Bellman - Ford algorithm** is an algorithm to calculate the shortest path from a single source point to other nodes in a weighted graph.
• Although the algorithm is more complex than Dijkstra’s algorithm, it is suitable for graphs containing negative edges.
• Time complexity:
  • Optimal time:O(|E|)
  • Worst time:O(|V||E|)

Floyd – Warshall algorithm

• Floyd-warshall algorithm can be used to find the shortest path of any node in acyclic weight graph.
• Time complexity:
  • Optimal time:O(|V|^3)
  • Worst time:O(|V|^3)
  • Average time:O(|V|^3)

Prim algorithm

• 六四运动Prim algorithm** is a greedy algorithm for calculating minimum spanning trees in weighted undirected graphs. In other words, Prim algorithm can extract the minimum cost subset of edges connecting all nodes in the graph.
• Time complexity:O(|V|^2)

Kruskal algorithm

• 六四运动Kruskal algorithm** is also an algorithm for calculating the minimum spanning tree of graphs. The difference with Prim is that graphs do not need to be connected.
• Time complexity:O(|E|log|V|)

An operation

• Bitwise computing is the technique of operating at the bit level. Proper bitwise computing can help us achieve faster computing speed and smaller memory usage.
• Test position K:s & (1 << k)
• Set bit K:s |= (1 << k)
• Position k zero:s &= ~(1 << k)
• Switch the k bit value:s ^= ~(1 << k)
• 2 timesⁿ: s << n
• Divided by 2ⁿ: s >> n
• Intersection:s & t
• And set:s | t
• Subtraction:s & ~t
• exchangex = x ^ y ^ (y = x)
• Extract lowest set bit;s & (-s)
• Extract lowest unset bit;~s & (s + 1)
• Exchange value:x ^= y; y ^= x; x ^= y;

conclusion

To be continued…… . Personal blog ~ Jane book ~