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

This article mainly introduces "how to master Java data structure". In daily operation, I believe many people have doubts about how to master Java data structure. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "how to master Java data structure"! Next, please follow the editor to study!

One: show the use of various data structures through some source code:

1. Sequence table

Concept and structure:

A sequential table is a linear structure in which data elements are stored successively in a storage unit with a continuous physical address, usually using an array. Complete the addition, deletion, query and modification of data on the array

Public interface ISequence {/ / insert val boolean add (int pos,Object data) in pos location; / / find the keyword key to find the subscript that returns key, but not null; int search (Object key); / / find whether the keyword key is in the order table (this conflicts with search) boolean contains (Object key); / / get the value of pos location Object getPos (int pos) / delete the keyword key Object remove (Object key) that appears for the first time; / / get the length of the sequence table int size (); / print the sequence table void display (); / / empty the sequence table to prevent memory leaks void clear ();}

two。 Linked list

Concept: a linked list is a non-continuous, non-sequential storage structure on the physical storage structure, and the logical order of data elements is realized through the referenced link order in the linked list.

Types of linked lists:

Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more used as a sub-structure of other data structures, such as hash bucket, adjacency table of graph, and so on.

Lead cyclic single linked list: the structure is simpler than headless unidirectional non-cyclic linked list.

No lead two-way circular linked list: in Java's collection framework library, the underlying implementation of LinkedList is not leading two-way circular linked list.

/ 1. Implement public interface ILinked {/ / head insertion void addFirst (int data); / tail insertion void addLast (int data) in headless unidirectional acyclic linked list; / / insert anywhere, the first data node is 0 subscript boolean addindex (int index,int data); / / find whether to include the keyword key in the single linked list boolean contains (int key) / delete the node int remove (int key) whose keyword is key for the first time; / / delete all nodes with the value of key void removeAllKey (int key); / / get the length of the single linked list int getLength (); void display (); void clear () } / / 2. Lead the circular single linked list to implement public interface ICLinked {/ / head insertion void addFirst (int data); / tail insertion void addLast (int data); / / insert anywhere, the first data node is 0 subscript boolean addindex (int index,int data); / / find whether to include the keyword key in the single linked list boolean contains (int key) / delete the node int remove (int key) whose keyword is key for the first time; / / delete all nodes with the value of key (int key); / / get the length of the single linked list int getLength (); void display (); void clear ();} / 3. Implement public interface IDoubleLinked {/ / insert void addFirst (int data) without leading two-way linked list; / / insert void addLast (int data) / / insert anywhere, the first data node is 0 subscript boolean addindex (int index,int data); / / find whether to include the keyword key in the single linked list boolean contains (int key); / / delete the node int remove (int key) where the keyword is key for the first time; / / delete all nodes whose value is key (int key); / / get the length of the single linked list int getLength () Void display (); void clear ();}

3. Stack

The concept and structure of stack

Stack: a special linear table that only allows inserting and deleting elements at a fixed end. One end of the data insertion and deletion operation is called the top of the stack and the other end is called the bottom of the stack. The data elements in the stack follow the principle of last-in, first-out LIFO (Last In First Out). Stack pressing: the insertion operation of the stack is called entering the stack / pressing the stack / entering the stack, and the input data is at the top of the stack.

Out-of-stack: the delete operation of the stack is called off-stack. The output data is also at the top of the stack.

Generally, the implementation of stack can be implemented by array or linked list, which is better than the structure of array. Because the cost of inserting data at the end of the array is relatively small.

Interface MyStack {/ / determines whether the stack is empty boolean empty (); / / returns the top element of the stack without leaving the stack int peek (); / / returns the top element of the stack and leaves the stack int pop (); / / pushes the item into the stack void push (int item); / / returns the number of elements int size ();}

4. Queue

The concept and structure of queues

Queue: a special linear table that only allows inserting data at one end and deleting data at the other end. The queue has first-in-first-out FIFO (First In First Out) in the queue: the end of the insert operation is called the end of the queue and the end of the delete operation is called the head of the queue.

Implementation of queues

Queues can also be implemented in the structure of arrays and linked lists, and it is better to use the structure of linked lists, because if you use the structure of an array, it will be less efficient to put data out of the queue on the head of the array.

Interface IMyQueue {/ / determines whether the queue is empty boolean empty (); / / returns the first element of the queue, but does not leave the queue int peek (); / / returns the first element of the queue and leaves the queue int poll (); / / puts item into the queue void add (int item); / / returns the number of elements int size ();}

5: binary tree

A binary tree is a finite set of nodes that is either empty or consists of a root node plus two binary trees called the left subtree and the right subtree.

1) the characteristics of binary tree:

Each node has at most two subtrees, that is, the binary tree does not exist with a degree greater than 2.

The subtrees of a binary tree can be divided into left and right, and the order of the subtrees cannot be reversed.

2) Special binary tree:

Full binary tree: a binary tree that is a full binary tree if the number of nodes in each layer reaches the maximum. That is to say, if the number of layers of a binary tree is K and the total number of nodes is (2 ^ k)-1, then it is a full binary tree.

Complete binary tree: a complete binary tree is a very efficient data structure, and a complete binary tree is derived from a full binary tree. For a binary tree with depth K, a binary tree with n nodes is called a complete binary tree if and only if each node corresponds to the nodes numbered from 1 to n in the full binary tree with depth K. It should be noted that the full binary tree is a special kind of complete binary tree.

3) the storage structure of binary tree

Binary trees can generally be stored in two structures, a sequential structure and a chained structure.

1. The binary tree sequence is physically an array and logically a binary tree.

Linked storage: the linked storage structure of a binary tree means that a binary tree is represented by a linked list, that is,

Chains are used to indicate the logical relationship of elements. The usual method is that each node in the linked list consists of three fields.

The data field and the left and right pointer domain are used to give the location of the left and right children of the node, respectively.

The storage address of the link point of the

Class Node {data field in int value; / / node Node leftChild; / / save left child node Node rightChild; / / save right child node}

(1) the sequential storage structure of binary tree: generally, it is a complete binary tree.

Introduce the concept of heap: (using the storage structure of the array to store a complete binary tree)

The concept and structure of reactor

If there is a set of keys K = {K0 ~ K1, K2, … , kn-1}, stores all its elements in an one-dimensional array in the order of a complete binary tree, and satisfies: Ki = K2i+2) I = 0primel 2 … Is called a small (or large) heap The largest heap of the root node is called the maximum heap or the large root heap, and the smallest heap of the root node is called the smallest heap or the small root heap.

Nature of the heap:

The value of a node in the heap is always no greater than or less than the value of its parent node; the heap is always a complete binary tree.

(2) the chain storage structure of binary tree.

/ / number of nodes int getSize (Node root); / number of leaf nodes int getLeafSize (Node root); / / number of nodes in layer k int getKLevelSize (Node root, int k); / / search, look for value in the root, left subtree and right subtree of the binary tree. If found, return nodes, otherwise return nullNode find (Node root, int value) At this point, the study on "how to master Java data structure" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.