Data Structures Reference

Table of Contents

Interviewcake.com – An awesome site.

A quick reference of the big O costs and core properties of every data structure.

Array

Stores things in order. Has quick lookups by index.

按顺序存储,按索引快速查找。

Dynamic Array

An array that automatically grows as you add more items.

当你添加更多元素时,长度会自动增长的数组。

Linked List

Also stores things in order. Faster insertions and deletions than arrays, but slower lookups (you have to "walk down" the whole list).

按顺序存储,与数组相比,插入和删除速度更快,但查找速度较慢(必须“遍历”整个列表)。

Queue

Like the line outside a busy restaurant. "First come, first served."

就像在繁忙的餐馆外面排队一样, “先到先得。”

Stack

Like a stack of dirty plates in the sink. The first one you take off the top is the last one you put down. i.e. "Last in, first out."

就像汉诺塔的叠盘,从顶部摘下的第一个是您放下的最后一个, “后进先出”。

Hash Table

Like an array, except instead of indices you can set arbitrary keys for each value.

像数组一样,不同之处在于除了索引以外,您可以为每个值设置任意键。

Tree

Good for storing hierarchies. Each node can have "child" nodes.

适合存储层次结构,每个节点可以具有“子”节点。

Binary Search Tree

Everything in the left subtree is smaller that the current node, everything in the right subtree is larger. O(lgn) lookups, but only if the tree is balanced!

左子树中的所有内容均小于当前节点,右子树中的所有内容均较大。

Graph

Good for storing networks, geography, social relationships, etc.

适用于存储网络,地理位置,社会关系等。

Trie

Stores a set of strings in a big tree of characters. Good for lookups by prefix. Somethings saves space.

将一组字符串存储在一棵大字符树中,适合通过前缀查找,可以节省空间。

Heap

A binary tree where the smallest value is always at the top. Use it to implement a priority queue.

一棵二叉树,其中最小值始终位于顶部,使用它来实现优先级队列。

Priority Queue

A queue where items are ordered by priority.

按优先级对项目进行排序的队列。

Bloom filter

A constant-space bitmap that lets you quickly check whether or not an item is in a set. Can give false positives.

一个常量空间的位图,可以让你快速检查一个项目是否在一个集合中。

LRU Cache

Lets you quickly identify which item hasn't been used for the longest amount of time.

使您可以快速识别未使用时间最长的项目。

Date: 2020-01-22 Wed 09:23

Author: Jack Liu

Created: 2020-02-08 Sat 21:26

Validate