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

Today, I will talk to you about the data structure that you need to understand in Java programming, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

Almost all the questions require the interviewer to have a deep understanding of the data structure. Whether you are a newcomer (fresh out of college or a programming class) or a workplace veteran with decades of experience.

Some interview questions explicitly refer to a certain data structure, such as, "given a binary tree." Others are implied in the interview questions, for example, "We want to record the number of books related to each author."

Even for some very basic work, it is necessary to learn data structures. So, let's start with some basic concepts.

What is a data structure?

In a nutshell, a data structure is a container that stores data in a particular layout. This "layout" determines that the data structure is efficient for some operations and inefficient for others. First of all, we need to understand a variety of data structures in order to select the most appropriate data structure when dealing with practical problems.

Why do we need data structures?

Data is the most critical entity in computer science, and data structure can store data in some organizational form, so the value of data structure is self-evident.

No matter how you solve any problem, you need to deal with the data-whether it's employee salaries, stock prices, shopping lists, or just a simple phone book problem.

Data needs to be stored in a specific format according to different scenarios. There are many data structures that can meet the needs of storing data in different formats.

Common data structures

First, list some of the most common data structures, which we will explain one by one:

Array

Stack

Queue

Linked list

Tree

Figure

Dictionary tree (this is an efficient tree structure, but worth explaining separately)

Hash table (hash table)

Array

Arrays are the simplest and most widely used data structures. Other data structures such as stacks, queues, and so on, evolve from arrays. The following figure shows a simple array of elements (1, 1, 2, 3 and 4). The array is 4 in length.

Each data element is associated with a positive value, which we call an index, which indicates the location of each element in the array. Most languages define the initial index as zero. Follow the official Wechat account of Java technology stack and reply to "interview" to get more interview questions carefully organized by bloggers.

Here are two types of arrays:

One-dimensional array (shown above)

Multidimensional array (array of arrays)

Basic operation of array

Insert-- inserts an element at the specified index location

Get-- returns the element at the specified index location

Delete-- deletes the element at the specified index location

Size-- gets the number of all elements in the array

Frequently asked questions about arrays in an interview

Find the second smallest element in the array

Find the first non-recurring integer in the array

Merge two ordered arrays

Rearrange positive and negative values in the array

Stack

Famous undo operations can be found in almost any application. But have you ever thought about how it works? The solution to this problem is to store the historical working state in memory (of course, it will be limited to a certain number) in the order in which the final state comes first. This cannot be done with an array. But with the stack, it becomes very convenient.

Think of the stack as a list of books stacked vertically. In order to get the book in the middle, you need to remove all the books placed on it. This is how LIFO (last in first out) works.

The following figure shows a stack that contains three data elements (1 ~ 2 and 3), of which the top 3 will be removed first:

Basic operation of stack

Push-- inserts an element at the top

Pop-- returns and removes the top elements of the stack

IsEmpty-- returns true if the stack is empty

Top-- returns the top element, but does not remove it

Frequently asked questions about stacks in the interview

Evaluate suffix expressions using stacks

Sort the elements of the stack

Determine whether the expression is balanced in parentheses

Queue

Like a stack, a queue is another linear data structure that sequentially stores elements. The biggest difference between a stack and a queue is that the stack is LIFO (last in, first out), while the queue is FIFO, that is, first in, first out.

A perfect practical example of a queue: a queue at a ticket booth. If a newcomer joins, he needs to line up at the end of the line, not at the head of the line-the person at the front of the line will get the ticket first and then leave the line.

The following figure shows a queue with four elements (1, 2, 3 and 4), of which the 1 at the top will be the first to be removed:

Remove advanced elements and insert new elements

Basic operation of the queue

Enqueue ()  --   inserts an element at the end of the queue

Dequeue ()  -removes elements from the queue header

IsEmpty ()-returns true if the queue is empty

Top ()  -returns the first element of the queue

Frequently asked questions about queues in an interview

Use queues to represent stacks

Reverse the first k elements of the queue

Use queues to generate binary numbers from 1 to n

Linked list

Linked lists are another important linear data structure, which may look a bit like an array at first glance, but differ in memory allocation, internal structure, and basic operations for data insertion and deletion. Follow the official Wechat account of Java technology stack and reply to "interview" to get more interview questions carefully organized by bloggers.

A linked list is like a chain of nodes, in which each node contains data and pointers to subsequent nodes. The linked list also contains a header pointer that points to the first element of the linked list, but when the list is empty, it points to null or has no specific content.

Linked lists are generally used to implement file systems, hash tables, and adjacency tables.

This is a display of the internal structure of the linked list:

Linked lists include the following types:

Single linked list (unidirectional)

Two-way linked list (two-way)

Basic operation of linked list:

InsertAtEnd-inserts the specified element at the end of the linked list

InsertAtHead-inserts the specified element at the beginning / header of the link list

Delete  -removes the specified element from the linked list

DeleteAtHead-deletes the first element of the linked list

Search  -returns the specified element from the linked list

IsEmpty-returns true if the linked list is empty

Frequently asked questions about linked lists in an interview

Reverse linked list

Detect loops in linked lists

Returns the penultimate node of the linked list

Delete duplicates in the linked list

Figure

The figure is a group of nodes connected to each other in the form of a network. Nodes are also called vertices. A pair of nodes (x edge y) are called edges, indicating that vertex x is connected to vertex y. Edges can contain weights / costs, showing the cost from vertex x to y.

Types of graphs

Undirected graph

Directed graph

In programming languages, diagrams can be represented in two forms:

Adjacency matrix

Adjacency table

Common graph traversal algorithm

Breadth first search

Depth first search

Frequently asked questions about diagrams in the interview

Achieve breadth and depth first search

Check whether the graph is a tree

Calculate the number of edges of a graph

Find the shortest path between two vertices

Tree

The tree structure is a hierarchical data structure consisting of vertices (nodes) and the edges that connect them. A tree is similar to a graph, but an important feature that distinguishes a tree from a graph is that there is no loop in the tree.

Tree structure is widely used in artificial intelligence and complex algorithms, and it can provide an effective storage mechanism to solve problems.

This is a schematic diagram of a simple tree, as well as the basic terms used in tree data structures:

Root-root node

Parent-parent node

Child-Child Node

Leaf-leaf node

Sibling-sibling node

The following are the main types of tree structures:

N-ary tree

Balanced tree

Binary tree

Binary search tree

AVL tree

Red and black tree

2-3 tree

Among them, binary tree and binary search tree are the most commonly used trees.

Frequently asked questions about the tree structure in the interview:

Find the height of the binary tree

Find the k-th maximum in the binary search tree

Find the node with a distance k from the root node

Find the ancestor node of a given node in the binary tree

Dictionary tree (Trie)

Dictionary tree, also known as "prefix tree", is a special tree data structure, which is very effective in solving string-related problems. It can provide fast retrieval, mainly used to search words in dictionaries, automatically provide suggestions in search engines, and even be used for IP routing.

Here is an example of storing three words "top", "so" and "their" in a dictionary tree:

These words are stored from top to bottom, where the green nodes "p", "s" and "r" represent the bottom of "top", "thus" and "theirs", respectively.

Frequently asked questions about Dictionary Tree in interview

Calculate the total number of words in the dictionary tree

Print all words stored in the dictionary tree

Sort the elements of an array using a dictionary tree

Use a dictionary tree to form words from a dictionary

Build T9 dictionary (dictionary tree + DFS)

Hash table

Hashing is a process used to uniquely identify objects and store each object in some pre-calculated unique index called "key". Therefore, objects are stored in the form of key-value pairs, and the collection of these key-value pairs is called a dictionary. You can use the key to search for each object. There are many different data structures based on hash method, but the most commonly used data structure is hash table.

Hash tables are usually implemented using arrays.

The performance of hash data structures depends on the following three factors:

Hash function

The size of the hash table

Collision treatment method

The following figure shows how to map hash key-value pairs in an array. The index of the array is calculated by the hash function.

Frequently asked questions about hash structure in the interview:

Find symmetric key-value pairs in the array

Trace the full path of traversal

Find whether the array is a subset of another array

Check whether the given array is disjoint

After reading the above, do you have any further understanding of the data structures you need to understand in Java programming? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

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.