Definition of data structures and algorithms

  • Data Structure

The way data is organized and stored in a computer.

  • Algorithm
    • Usually there is input
    • Usually produces output
    • It ends eventually, not in a loop

The method used to solve a problem (such as creating components recursively). Data structures are implemented by algorithms.

Linear structure

A collection of sequential data elements.

Array (Array)

The advantage of arrays is that elements can be quickly found when they are read from subscripts and modified.

When you insert a new element into an array. If the insertion is not at the end of the insertion, all existing elements are moved back one by one. The delete operation also causes the following elements to move forward one by one. So insert and delete operations are performance-intensive.

In JS arrays are dynamic, but in other static languages arrays are created with specified sizes. An array is a contiguous segment of memory. When you expand an array, you can only apply for a larger array. Clone the elements of the previous array. Therefore, the array expansion operation is time-consuming.

The Stack (Stack)

The stack structure is characterized by last in first out (LIFO). Example: function call stack.

Stacks can’t insert or delete data anywhere like arrays can,Elements can only be inserted or deleted at one end. Like taking a shuttlecock out of a shuttlecock box. The top of the stack is called the top, and the bottom is called the bottom. Adding elements is called pushing or pushing. Delete the element and call out the stack.

Stacks are usually implemented using arrays or linked lists.

Queue

Feature is first in first out (FIFO), and life in line for dinner, first in first out. Asynchronous queues.

  • Priority queue

All elements in a queue have priority. When inserting a new element, the priority of the inserted data is taken into account instead of being placed directly in the back end. Compare the priority with other data in the queue, and place the element in the correct position.

List (List)

Linked lists can also store multiple elements. Lists are created without a fixed size and can extend indefinitely. The elements in a linked list need not be contiguous Spaces in memory.

Linked lists are more efficient at inserting and deleting data than arrays. Elements read/modified by subscript perform worse than arrays.

Singly linked list

Each node in the linked list stores a reference to the next node in addition to the element. A linked list has a head node (head) that refers to the first node. The following image is from Baidu Baike:

Because unidirectional lists are unidirectional links, they can only be traversed from head to tail, or from tail to head.

Two-way linked list

A bidirectional list is where each node stores elements, references to the previous node, and references to the next node. A double-linked list has a tail as well as a head node. Next, which refers to the last node, is null.

Set (Set)

A collection is a data structure composed of an unordered set of non-repeating elements. Because there is no order, elements cannot be accessed by subscript. After ES6 is implemented — Set.

A dictionary (Map)

The element is stored as a key:value, a collection of key-value pairs.

A key corresponds to a value, or a mapping. Dict in Pyhton is an implementation of dictionaries, called a Map in Java. JS objects ({}) can also be used as dictionaries. In ES6, Map objects are added. The difference is that the key of the object is automatically converted to a string or Symbol. Map objects are not converted.

Hash table (Hash)

Hash tables also consist of key-value pairs. It is usually implemented using arrays. When you insert or delete an array all of the elements have to be displaced if there are other elements following it. If you look for elements by content, you can only traverse the search from beginning to end. But hash tables have some wrapping to make insertion, deletion, and lookup very fast. The data in the hash table is unordered and the key cannot be repeated.