Shulou(Shulou.com)06/01 Report--

Editor to share with you what are the commonly used Java data structure knowledge points, I hope you will gain something after reading this article, let's discuss it together!

1. Data structure classification

Java data structures can be divided into two categories according to their linearity and nonlinearity:

① linear data structures: arrays, linked lists, stacks, queues

② nonlinear data structure: tree, heap, hash table, graph

two。 Linear data structure 2.1 array

An array is a data structure that stores elements in contiguous memory space and requires the elements to be of the same type.

/ / define an array of length 5, arrayint [] array = new int [5]; / / assign values to the elements of the array, array [0] = 4; [1] = 3; [2] = 2; [3] = 1; [4] = 0

Direct assignment:

/ one 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 improved array with flexible length on the basis of general array combined with expansion mechanism.

/ / define a variable array List changeable_array = new ArrayList (); / / add elements to the tail of the variable 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 successor node. The node is the basic unit of the linked list, and the storage address of this data structure in memory space is discontiguous.

/ / define the value of the linked list class class ListNode {/ / node int val; / / reference ListNode next; ListNode (int x) {this of the successor node. Val = x;}}

Build objects of multiple linked list classes and build references between these node instances that point to:

The node value of the ① node head is 2, and the subsequent node is the node N2 with the value 1.

The node value of the ② node N2 is 1, and the subsequent node is the node N3 with the value 0.

③ the head node of the linked list is head and the tail node is N3.

/ / instantiate the node ListNode head = new ListNode (2); ListNode N2 = new ListNode (1); ListNode n3 = new ListNode (0); / / build the reference between the three nodes pointing to head.next = n2mitn2.Next = n3102.4 stack

Stack is an abstract data structure characterized by "last-in, first-out", which can be implemented by arrays or linked lists.

/ / define a stack that uses StackStack stack = new Stack (), a subclass of Java's Vector class

Stack operation push ():

/ / element 0 stacks stack.push (0); / / element 1 stacks stack.push (1)

Unstack operation pop ():

/ / element 1 out of stack stack.pop (); / / element 0 out of stack stack.pop ()

You can use Stack, ArrayDeque, and LinkedList to implement the stack in Java, but in general, it is not recommended to use the Vector class and its subclass Stack

LinkedList is generally used to implement the stack:

LinkedList stack = new LinkedList ()

Stack operation addLast ():

/ / element 0 stacks stack.addLast (0); / / element 1 stacks stack.addLast (1)

Unstack operation removeLast ():

/ / element 1 out of stack stack.removeLast (); / / element 0 into stack stack.removeLast (); 2.5 queue

Queue is an abstract data structure, characterized by "first-in, first-out", which can be implemented by linked lists.

The LinkedList class implements the Queue interface, so you can use LinkedList as a Queue.

Queue queue = new LinkedList ()

Join the queue operation offer ():

/ / element 0 join the team queue.offer (0); / / element 1 join the team queue.offer (1)

The dequeue operation poll (), and the return value of this function is the dequeued element:

/ / element 0 out of team queue.poll (); / / element 1 out of team queue.poll ()

Element (): returns the first element

Peek (): returns the first element

Difference: when the queue element is empty, the element () method throws a NoSuchElementException exception, and the peek () method only returns null.

Queue.offer ("a"); queue.offer ("b"); queue.offer ("c"); queue.offer ("d"); queue.offer ("e"); queue.element (); / / output aqueue.peek (); / / output a3. Nonlinear data structure 3.1 tree

Tree is a kind of 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 left, and right child node right.

Class TreeNode {int val; TreeNode left; TreeNode right; TreeNode (int x) {this.val = x;}}

Instantiate each node of the binary tree:

/ / Root node rootTreeNode 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 references between the nodes of the binary tree point to:

/ / the left child node of the root node is N2, its value is 1root.left = N2 / the right child node of the root node is n3, its value is 2root.right = n3, the left child node of node N2 is n4, its value is 3n2.left = n4ram / node N2, the right child node of node N2 is n5, its value is 4n2.right = n5transfer3.2

A graph is a nonlinear data structure, which consists of vertex and edge. Each edge connects two vertices.

Graphs are divided into directed graphs and undirected graphs.

Take the 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) the representation of graph: adjacency matrix (the adjacency matrix of undirected graph is an oblique diagonal symmetric matrix)

⭐ adjacency matrix is suitable for storing dense graphs, that is, more vertices and fewer edges.

/ / storing vertices of the graph int [] vertices = {1,2,3,4,5} / store the edges of the graph int [] [] edges = {{0,1,1,1}, {1,0,0,1,0}, {1,0,0,0,1}, {1,0,0,0,1}, {1,0,1,1,0}; int [] vertices = {1,2,3,4,5}

(2) the representation of graph: adjacency table

⭐ adjacency table is suitable for storing sparse graphs, that is, there are many vertices and few edges.

/ / storing vertices of a graph int [] vertices = {1,2,3,4,5}; / / storing a set of edges List edges = new ArrayList (); / / edge [I] represents a set of edges corresponding to vertices I of a graph List edge_1 = new ArrayList (Arrays.asList (1,2,3,4)); List edge_2 = new ArrayList (Arrays.asList (0,3)); List edge_3 = new ArrayList (Arrays.asList (0,4)) List edge_4 = new ArrayList (Arrays.asList (0,1,4)); List 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 nonlinear data structure, which essentially maps keys (key) to values (value) through Hash functions.

/ / initialize hash table Map dict = new HashMap ()

Add key-value pairs:

Dict.put ("python", 101); dict.put ("c", 102); dict.put ("java", 103)

Use the key key to find the corresponding value value:

Dict.get ("python"); / / 101dict.get ("c"); / / 102dict.get ("java"); / / 103

Design a simple Hash function to build the programming language = > numbered mapping, and build a hash table (assuming 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)]; / / pythonnames [hash (101)]; / / cnames [hash (101)]; / / java3.4 heap

The main results are as follows: (1) Heap is a data structure based on complete binary tree, which can be implemented by array.

Complete binary tree: a binary tree with n nodes in depth 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 have the same position in the binary tree, the binary tree is called a complete binary tree.

(2) the sorting algorithm based on heap principle is called heap sorting.

(3) the data structure based on heap is called priority queue.

(4) the heap is divided into big top heap and small top heap: ① big top heap: the value of any node is not greater than that 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 that 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 the priority queue Queue heap = new PriorityQueue ()

Element in the heap add ():

/ / elements in the heap heap.add (0); heap.add (4); heap.add (2); heap.add (6); heap.add (8)

Element out of the heap poll ():

/ / element out of the heap (from small to large) heap.poll (); / /-> 0heap.poll (); / /-> 2heap.poll (); / /-> 4heap.poll (); / /-> 6heap.poll () / /-> 8 after reading this article, I believe you have a certain understanding of "what are the common knowledge points of Java data structure". If you want to know more about it, please follow the industry information channel. Thank you for your reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.