1. Data structure classification
Java data structures can be divided into two categories according to linearity and nonlinearity:
① Linear data structure: array, linked list, stack, queue
② Nonlinear data structure: tree, heap, hash table, graph
2. Linear data structure
2.1 array
Array is a data structure that stores elements in continuous memory space, and requires the same type of elements.
// Define an array with an array length of 5 int[] array = new int[5]; // Assign values to the elements of the array array[0] = 4; array[1] = 3; array[2] = 2; array[3] = 1; array[4] = 0;
Direct assignment:
// A way
int[] array = {4, 3, 2, 1, 0};
// Another way
int[] array = new int[]{4, 3, 2, 1, 0};
2.2 variable array
Variable array is an array with flexible length, which is improved on the basis of general array and capacity expansion mechanism.
// Define a mutable array List<Integer> changeable_array = new ArrayList<>(); // Adds an element to the tail of a mutable array array.add(4); array.add(3); array.add(2); array.add(1); array.add(0);
2.3 linked list
A linked list can be defined as a class that contains two member variables: the value val of the node and the reference next of the subsequent node. Node is the basic unit of the linked list. The storage address of this data structure in the memory space is discontinuous.
// Define linked list class
class ListNode {
// Value of node
int val;
// Reference of successor node
ListNode next;
ListNode(int x){
this. val = x;
}
}
Build objects of multiple linked list classes, and build references between these node instances to:
① The node value of node head is 2, and its successor node is node n2 with the value of 1.
② The node value of node n2 is 1, and its successor node is node n3 with value 0.
③ The head node of the linked list is head and the tail node is n3.
// Instantiation node ListNode head = new ListNode(2); ListNode n2 = new ListNode(1); ListNode n3 = new ListNode(0); // Build reference points between three nodes head.next = n2; n2.next = n3;
Stack 2.4
Stack is an abstract data structure characterized by "last in first out", which can be realized by array or linked list.
// Define a Stack and use the subclass Stack of Java's Vector class Stack<Integer> stack = new Stack<>();
Stack push():
// Stack element 0 stack.push(0); // Stack element 1 stack.push(1);
Stack out operation (POP):
// Element 1 out of stack stack.pop(); // Element 0 out of stack stack.pop();
Stack, ArrayDeque and LinkedList can be used to implement stack in Java, but generally, Vector class and its subclass stack are not recommended. See the following for specific reasons:
https://blog.csdn.net/cartoon_/article/details/87992743
LinkedList is generally used to implement stack:
LinkedList<Integer> stack = new LinkedList<>();
Stack operation addLast():
// Stack element 0 stack.addLast(0); // Stack element 1 stack.addLast(1);
Stack out operation removeLast():
// Element 1 out of stack stack.removeLast(); // Stack element 0 stack.removeLast();
2.5 queue
Queue is an abstract data structure characterized by "first in first out", which can be realized by linked list.
The LinkedList class implements the Queue interface, so you can use LinkedList as a Queue.
Queue<Integer> queue = new LinkedList<>();
Queue operation offer():
// Element 0 enlisted queue.offer(0); // Element 1 join the team queue.offer(1);
Out of queue operation poll(), the return value of this function is the out of queue element:
// Element 0 out of line queue.poll(); // Element 1 out of the team queue.poll();
element(): returns the first element
peek(): returns the first element
Difference: when the queue element is empty, the element() method will throw a NoSuchElementException exception, and the peek() method will only return null.
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
queue.element(); //Output a
queue.peek(); //Output a
3. Nonlinear data structure
3.1 tree
Tree is a nonlinear data structure, which can be divided into binary tree and multi tree.
A binary tree can be defined as a class that contains three member variables: node value val, left child node and right child node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
this.val = x;
}
}
Instantiation of each node of binary tree:
// Root node root TreeNode root = new TreeNode(0); TreeNode n2 = new TreeNode(1); TreeNode n3 = new TreeNode(2); TreeNode n4 = new TreeNode(3); TreeNode n5 = new TreeNode(4);
The reference between the nodes of the binary tree points to:
// The left child node of the root node is n2, and its value is 1 root.left = n2; // The right child node of the root node is n3, and its value is 2 root.right = n3; // The left child node of node n2 is n4, and its value is 3 n2.left = n4; // The right child node of node n2 is n5, and its value is 4 n2.right = n5;
3.2 drawings
Graph is a nonlinear data structure, which is composed of vertices and edges. Each edge is connected with two vertices.
Graphs are divided into directed graphs and undirected graphs.
Take undirected graph as an example:
① Vertex set: vertices = {1, 2, 3, 4, 5}
② Edge set: edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}
(1) Representation of graph: adjacency matrix (adjacency matrix of undirected graph is a diagonal symmetric matrix)
⭐ Adjacency matrix is suitable for densely stored graphs, that is, there are more vertices and fewer edges.
// Storing vertices of a graph
int[] vertices = {1, 2, 3, 4, 5};
// Storing edges of Graphs
int[][] edges = {{0, 1, 1, 1, 1},
{1, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{1, 1, 0, 0, 1},
{1, 0, 1, 1, 0}};
int[] vertices = {1, 2, 3, 4, 5};
(2) Representation of graph: adjacency table
⭐ Adjacency table is suitable for storing sparse graphs, that is, more vertices and fewer edges.
// Storing vertices of a graph
int[] vertices = {1, 2, 3, 4, 5};
// Collection of storage edges
List<List<Integer>> edges = new ArrayList<>();
// edge[i] represents the set of edges corresponding to the vertex i of the graph
List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));
List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));
List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));
List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));
edges.add(edge_1);
edges.add(edge_2);
edges.add(edge_3);
edges.add(edge_4);
edges.add(edge_5);
3.3 hash table
Hash table is a non-linear data structure. Its essence is to complete the mapping from key to value through hash function.
// Initialize hash table Map<String, Integer> dict = new HashMap<>();
Add key value pair:
dict.put("python", 101);
dict.put("c", 102);
dict.put("java", 103);
Find the corresponding value by pressing key:
dict.get("python"); // 101
dict.get("c"); // 102
dict.get("java"); // 103
Design a simple Hash function, build the mapping of programming language = = > number, and build a Hash table (assuming that low collision rate and high robustness are not considered):
String[] program_lang = {"python", "c", "java"};
int hash(int idx){
int index = (idx -1 % 100);
return index;
}
names[hash(101)]; // python
names[hash(101)]; // c
names[hash(101)]; // java
3.4 reactor
(1) Heap is a data structure based on complete binary tree, which can be realized by array.
Complete binary tree: a binary tree with n nodes with a depth of k. the nodes in the tree are numbered from top to bottom and from left to right. If the node numbered i (1 ≤ i ≤ n) and the node numbered i in the full binary tree are in the same position in the binary tree, the binary tree is called complete binary tree.
(2) The sorting algorithm based on the principle of heap is called heap sorting.
(3) The data structure based on heap implementation is called priority queue.
(4) Heap is divided into large top heap and small top heap: ① large top heap: the value of any node is not greater than the value of its parent node, that is, the root node is the largest, and any child node is less than or equal to the parent node. ② Small top heap: the value of any node is not less than the value of its parent node, that is, the root node is the smallest, and any child node is greater than or equal to the parent node.
// Initialize the small top heap and operate as a priority queue Queue<Integer> heap = new PriorityQueue<>();
Element heap add():
// Element heap heap.add(0); heap.add(4); heap.add(2); heap.add(6); heap.add(8);
Element out of heap poll():
// Element out of heap (from small to large) heap.poll(); // -> 0 heap.poll(); // -> 2 heap.poll(); // -> 4 heap.poll(); // -> 6 heap.poll(); // -> 8
The supporting diagram on LeetCode is clearly explained. When learning, refer to: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/