This album is based on B station “JavaScript data Structures and algorithms” video organized study notes, the author of this article has the notes, source code, test environment hosted on GitHub, welcome students Star and Fork.

It is recommended that you follow the order of the directory structure to learn, from the shallow to the deep, step by step, easy to figure out the data structure and algorithm.

What is a data structure?

Definition of data structures

  • define

    • “A data structure is a data object and the relationships that exist between an instance of that object and the data elements that make up that instance. These connections can be given by defining the related functions.” — Data Structures, Algorithms and Applications
    • “A Data structure is a physical implementation of an ADT.” — Data Structure and Algorithm Analysis
    • “A data structure is a way of storing and organizing data in a computer. Often, carefully selected data structures lead to the most efficient algorithm.” — Chinese Wikipedia

  • Know it from your point of view

    In a computer, the way data is stored and organized.

Data structure in life

We know that there is a huge amount of data in computers, how to organize and store it in an efficient way?

A large library contains a large number of books, we should not only put them in, but also be able to take them out at the right time.

Book placement to make two related operations easy to achieve:

  • Operation 1: How to insert new books?
  • Action 2: How do I find a given book?

Various ways of placing books:

  • Method 1: Put it anywhere

    • Operation 1: Place where there is space.
    • Operation 2: Looking for a book, tired to death.

  • Method 2: Arrange the titles in alphabetical order

    • Operation 1: New book “True Story of Ah Q”, according to the alphabetical order to find the position, insert.
    • Operation 2: Binary search.

  • Method 3: Divide your bookshelf into sections and store them by category, in alphabetical order

    • Operation 1: first set the category, binary search to determine the position, move out of the vacancy.
    • Operation 2: first set the category, and then binary search.

Conclusion:

  • The efficiency of the problem solving approach depends on how the data is organized.
  • The amount of data stored in a computer is larger than the amount of books in a library, more data.
  • In what ways can we store and organize our data to make it easier to use?
  • This is where the data structure comes in.

Common data structures

  • Array (Aarray)
  • Heap (Heap)
  • The stack (Queue)
  • Linked List
  • Graph (Graph)
  • Hash table
  • Queue
  • A Tree (Tree)

Note: Data structures are algorithmic and language-independent. All common programming languages use these common data structures directly or indirectly.

What is an algorithm?

The definition of Algorithm

  • A finite set of instructions in which the description of each instruction is independent of the language.
  • Receive some input (in some cases no input is required).
  • Produce output.
  • It must terminate after a finite number of steps.

Common understanding of algorithms

  • The word Algorithm is a logical way to solve a problem.
  • The realization of data structure is inseparable from algorithm.

Algorithm of case

If there is an elevated line between Shanghai and Hangzhou, the length of which is 1,000,000 meters, and one day one meter of the elevated line fails, please come up with an algorithm that can quickly locate the problem everywhere.

  • Linear search

    • Starting from the starting point in Shanghai, one meter of investigation will eventually be able to find the faulty line segment.
    • But if the line segment is on the other side, we have to do 1,000,000 checks, which is the worst case, on average 500,000 checks.

  • Binary search

    • Start the investigation from the middle position to see whether the problem is from Shanghai to the middle position or from the middle to Hangzhou.
    • After looking for the corresponding problem, then separated from the middle, and re-locked the general route.
    • Worst-case scenario, how many times does it take to complete the screening? The worst-case scenario is that it takes 20 to find out what’s wrong.
    • How do you figure that out? Log (1000000, 2), the logarithm of base 2 of 1000000 is ≈ 20.

Conclusion: You’ll find that there are many ways to solve a problem, but the efficiency of a good algorithm is vastly different from that of a bad algorithm.