source | http://suo.im/6oo92L

8 Common data structures

Data structure is a special way to organize and store data , It enables us to operate on the stored data more efficiently . Data structure is widely used in computer science and software engineering .

Almost all developed programs or software systems use data structures . Besides , Data structure is the foundation of computer science and software engineering . When it comes to software engineering interviews , This is a key theme . therefore , As a developer , We must have a good understanding of the data structure .

In this paper , I will briefly explain what every programmer must know 8 Common data structures .

C/C++ Learning skirt of 【 712 two eight four Seven Zero Five 】, Whether you are Xiaobai or an advanced person , If you want to change your career or join it, you can learn about it and learn from it together ！ There are development tools in the skirt , A lot of dry goods and technical information sharing ！

# 1. Array

Arrays are fixed size structures , Can hold items of the same data type . It can be an array of integers , Array of floating-point numbers , String array or even array array （ For example, a two-dimensional array ）. Array indexed , This means random access .

Fig 1. Visualization of basic Terminology of Arrays

# Array operations

· Traverse ： Traverse all elements and print .

· Insert ： Insert one or more elements into the array .

· Delete ： Remove elements from array

· Search for ： Search for elements in an array . You can search for elements by their value or index

· to update ： Update the value of an existing element at the given index

# Application of array

· Used as the basis for building other data structures , For example, array list , Pile up , Hashtable , Vectors and matrices .

· For different sorting algorithms , For example, insert sort , Quick sort , Bubble sort and merge sort .

# 2. Linked list

A list is a sequential structure , It consists of a sequence of linked linear sequential items . therefore , You have to access the data in sequence , And no random access . Link lists provide a simple and flexible representation of dynamic sets .

Let's consider the following terms about linked lists . You can refer to the figure 2 To get a clear idea .

· The elements in the list are called nodes .

· Each node contains a key and a point to its successor （ be called next） The pointer to .

· be known as head The attribute of points to the first element of the list of links .

· The last element of the list is called the tail .

Fig 2. Visualization of basic Terminology of Linked Lists

Here are the various types of lists available .

· Single chain list — You can only traverse items in a positive direction .

· Double linked list - You can traverse items in both forward and backward directions . The node consists of an additional pointer called the previous one , Point to the previous node .

· Loop link list — Link list , The last pointer of the head points to the tail , The next pointer to the tail points to the head .

# List operation

· Search for ： Through a simple linear search, find the key in a given list as k The first element of , And return a pointer to the element

· Insert ： Insert a key in the list of links . Insertion can be done by 3 Do it in different ways ; Insert... At the beginning of the list , Insert... At the end of the list , Then insert... In the middle of the list .

· Delete ： Remove elements from the given list x. You cannot delete a node step by step . Delete by 3 Do it in different ways ; Remove... From the beginning of the list , Delete... From the end of the list , Then delete... From the middle of the list .

# The application of linked list

· For symbol table management in compiler design .

· For in use Alt Tab（ Use circular list to realize ） Switch between programs .

# 3. Stack

Stack is a kind of LIFO（ Last in, first out - The last placed element can be accessed first ） structure , This structure can be found in many programming languages . This structure is called " Stack ", Because it's like a real world stack - The stack of plates .

Image Source: pixabay

# Stack operation

Here's what you can do on the stack 2 A basic operation . Please refer to the picture 3, To better understand stack operations .

· Push push ： Insert an element at the top of the stack .

· Pop eject ： Delete the top element and return .

Fig 3. Visualization of basic Operations of Stacks

Besides , The following additional functions are provided for the stack , To check its condition .

· Peep peep ： Returns the top element of the stack without deleting it .

· isEmpty： Check if the stack is empty .

· isFull： Check if the stack is full .

# Application of stack

· For expression evaluation （ for example ： Shunting yard algorithm used to analyze and evaluate mathematical expressions ）.

· Used to implement function calls in recursive programming .

# 4. queue

A queue is a kind of FIFO（ fifo - First placed elements can be accessed first ） structure , This structure can be found in many programming languages . This structure is called " queue ", Because it's like a real-world queue - People are waiting in line .

Image Source: pixabay

# Queue operation

Here's what you can do on a queue 2 A basic operation . Please refer to the picture 4, To better understand stack operations .

· Enter the team ： Insert the element at the end of the queue .

· Out of the team ： Remove elements from the beginning of the queue .

Fig 4. Visualization of Basic Operations of Queues

# Application of queues

· For managing threads in multithreading .

· Used to implement queuing system （ for example ： Priority queue ）.

# 5. Hashtable

A hash table is a data structure , Used to store values with keys associated with each key . Besides , If we know the key associated with the value , Then it effectively supports searching . therefore , Whatever the size of the data , Insert and search are very effective .

When stored in a table , Direct addressing uses a one-to-one mapping between values and keys . however , When there are a lot of key value pairs , There are problems with this method . The table will have a lot of records , And it's huge , Consider the available memory on a typical computer , The table may be impractical or even impossible to store . To avoid this problem , We use hash tables . A detailed introduction to hash table can be found in python Introduction and advanced official account collection algorithm ebook

# hash function

Called hash function （h） The special function of is used to overcome the above problems in direct addressing .

In a direct interview , With a key k The value of is stored in the slot k in . Use hash function , We can calculate the table that each value points to （ slot ） The index of . The value computed by the hash function of a given key is called the hash value , It represents the index of the table to which the value is mapped .

· h： hash function

· k： The key whose hash value should be determined

· m： The size of the hash table （ Number of slots available ）. One is not close to 2 The prime of the exact power of is m A good choice for .

Fig 5. Representation of a Hash Function

· 1→1→1

· 5→5→5

· 23→23→3

· 63→63→3

From the last two examples given above , We can see , When the hash function generates the same index for multiple keys , There will be conflict . We can choose the appropriate hash function h And uses technologies such as linking and open addressing to resolve conflicts .

# Application of hash table

· For database indexing .

· Used to implement associative arrays .

· Used to implement " Set up " data structure .

# 6. Trees

A tree is a hierarchy , Data is organized hierarchically and linked together . This structure is different from the link list , And in the list of links , Projects are linked in linear order .

In the past few decades , Various types of trees have been developed , To suit certain applications and meet certain limitations . Some examples are binary search trees ,B Trees , Red and black trees , Unfold the tree ,AVL Trees and n Metatree .

# Binary search tree

seeing the name of a thing one thinks of its function , Binary search tree （BST） It's a binary tree , The data is organized in a hierarchical structure . This data structure stores values in sort order , We will study these values in detail in this course .

Each node in the binary search tree contains the following attributes .

· key： Values stored in nodes .

· left： A pointer to the left child .

· Right ： A pointer to the right child .

· p： A pointer to the parent node .

Binary search trees have unique properties , It can be distinguished from other trees . This property is called binary-search-tree attribute .

Make x Search for a node in the binary tree .

· If y yes x A node in the left subtree , be y.key≤x.key

· If y yes x The nodes in the right subtree of , be y.key≥x.key

Fig 6. Visualization of Basic Terminology of Trees.

# The application of tree

· Binary tree ： For implementing expression parsers and expression solvers .

· Binary search tree ： Used in many search applications that continuously input and output data .

· Pile up ： from JVM（Java virtual machine ） Used to store Java object .

· Trap： For wireless networks .

# 7. Pile up

Heap is a special case of binary tree , Where the values of the parent and its children are compared , And arrange them accordingly .

Let's see how to represent a heap . The heap can be represented by trees and arrays . chart 7 and 8 Shows how we use binary trees and arrays to represent binary heaps .

Fig 7. Binary Tree Representation of a Heap

Fig 8. Array Representation of a Heap

Piles can have 2 Types .

· The smallest pile - The parent key is less than or equal to the child key . This is called min-heap attribute . The root will contain the minimum value of the heap .

· The maximum number of piles - The parent key is greater than or equal to the child key . This is called max-heap attribute . The root will contain the maximum value of the heap .

# Application of heap

· Used to implement priority queues , Because priority values can be sorted according to heap properties .

· Can be in O（log n） Use heap to implement queue function in time .

· Used to find... In a given array k Minimum （ Or maximum ） Value .

· For heap sort algorithm .

# 8. chart

A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices .

The order of a graph is the number of vertices in the graph . The size of a graph is the number of sides in the graph .

If two nodes are connected to each other through the same side , They are called adjacent nodes .

# Directed graph

If graphics G All edges of have directions indicating what is the starting vertex and what is the ending vertex , It is called a directed graph .

We said （u,v） From the top u To enter or leave a vertex u, Then incident or enter the vertex v.

Self ring ： From the vertex to its edge .

# Undirected graph

If the figure G All the edges of are directionless , It is called undirected graph . It can travel between two vertices in two ways .

If the vertex is not connected to any other node in the graph , The vertex is called an isolated .

Fig 9. Visualization of Terminology of Graphs

# The application of graph

· For social media networks . Every user is a vertex , And an edge is created when the user connects .

· Web pages and links used to represent search engines . Web pages on the Internet are linked to each other through hyperlinks . Every page is a vertex , The hyperlink between two pages is one side . be used for Google Page rank in .

· Used to represent GPS Location and route in . Position is the vertex , The route connecting the location is the side . Used to calculate the shortest path between two positions .

# reference

[1] Introduction to the algorithm , The third edition , author ： Thomas ·H· Komen （Thomas H. Cormen）, Charles ·E· Rayson （Charles E. Leiserson）, Ronald ·L· Livingster （Ronald L. Rivest） And Clifford · Stan （Clifford Stein）.

[2] come from Wikipedia List of data structures for

( This article is translated from Vijini Mallawaarachchi The article 《8 Common Data Structures every Programmer must know》, Reference resources ：https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42)

If you are right about C/C++ Interested in , Want to learn programming , Xiaobian recommends one C/C++ Technology exchange group 【 Click to enter 】！

** It's about **： Introduction to programming 、 Game programming 、 Network programming 、Windows Programming 、Linux Programming 、Qt Interface development 、 Hackers and so on ......