数据结构 向量和数组_数据结构和数组

Firstly, what is a data structure?

首先，什么是数据结构？

It is a collection of values that can have relationships among them and functions applied to them. Each data structure is good and specialized for its own particular issue as well as storing and finding particular data — fast.

它是值的集合，这些值之间可以具有相互关系以及应用于它们的功能。 每个数据结构都很好，并且专门针对自己的特定问题以及快速存储和查找特定数据。

There is a vast list of data structures that can be found here: All data structures.

在这里可以找到大量的数据结构：所有数据结构。

However, there are only a few main ones that you really need to know that are used 90% of the time. They are:

但是，您真正需要知道的是90％的时间都使用了几个主要的东西。 他们是：

• Arrays
  数组
• Stacks
  堆栈
• Queues
  Queue列
• Linked Lists
  链表
• Trees
  树木
• Tries
  尝试
• Graphs
  图表
• Hash Tables
  哈希表

Please bear in mind that each language has its own data structures, an example of a table can be found here. But if the language you are using does not contain the specific data structure, do not worry, as you can build one. For example, if Javascript doesn’t have Stacks — you can build one.

请记住，每种语言都有自己的数据结构，可以在此处找到表的示例。 但是，如果您使用的语言不包含特定的数据结构，请不要担心，因为您可以构建一个。 例如，如果Javascript没有堆栈-您可以构建一个。

Arrays

数组

Arrays organize data sequentially. So, they are stored one after another in memory. Arrays are one of the most commonly used data structures and have one of the smallest footprints of any data structure.

数组按顺序组织数据。 因此，它们一个接一个地存储在内存中。 数组是最常用的数据结构之一，在任何数据结构中的占用空间均最小。

Having come from a coding Bootcamp background, I knew what arrays were and how to use them, but having learned the basics of Big O Notation, which can be found in my previous blog here, I have realized that simple inbuilt methods actually have a variety of different Big O Notations.

来自Bootcamp的编码背景，我知道什么是数组以及如何使用它们，但是了解了Big O Notation的基础知识(可以在我以前的博客中找到) ，我已经意识到，简单的内置方法实际上有各种各样的方法不同的大O符号。

Take this simple array below and the two inbuilt methods of pop() and unshift():

请看下面的这个简单数组以及pop()和unshift()的两个内置方法：

What would you expect their Big O to be? Previously, I never would have thought about this, thinking… well .pop() takes the last element of the array and unshift just inserts an element at the beginning. Simple…

您希望他们的Big O是什么？ 以前，我从没想过，想想……好吧.pop()接受数组的最后一个元素，而unshift只是在开始处插入一个元素。 简单…

However, now you need to look at HOW the method works.

但是，现在您需要查看该方法的工作原理。

Why? Well pop() is simple. No matter what the length of the input, the method simply returns the last element. Therefore it is constant.

为什么？ pop()很简单。 不管输入的长度是多少，该方法都会简单地返回最后一个元素。 因此，它是恒定的。

However, unshift adds an element to an array. But? That simply just puts an element at the beginning every time, so surely that is constant as well?

但是，unshift将元素添加到数组。 但？ 只是每次都只是将一个元素放在开头，因此确定它也是恒定的吗？

That is partly correct, however, the index of the array needs to change. Therefore:

这是部分正确的，但是，数组的索引需要更改。 因此：

Unshift needs to loop through the array and assign each element a new index. As we know from the previous blog, a simple loop function is O(n) or linear time.

Unshift需要遍历数组并为每个元素分配一个新索引。 从上一篇博客中我们知道，一个简单的循环函数是O(n)或线性时间。

This is an example that should then make you think about if a different type of data structure would better suit adding a new element.

这是一个示例，然后应让您考虑是否其他类型的数据结构更适合添加新元素。

This should give you a basic understanding of why looking something up in the array is fast O(1) and adding something into the array is slower O(n).

这应该使您对为什么在数组中查找某些内容的速度快O(1)而在数组中添加某些内容的速度慢O(n)有了基本的了解。

Let’s use an array to solve a simple question of reversing a string.

让我们使用数组来解决一个简单的反转字符串的问题。

Here, we are using the .split() method. According to MDN ‘the split() method divides a string into an ordered list of substrings, puts these substrings into an array, and returns the array.’

在这里，我们使用.split()方法。 根据MDN的说法，“ split()方法将字符串分成子字符串的有序列表，然后将这些子字符串放入数组中，然后返回该数组。”

We then use the .join() method. Which ‘creates and returns a new string by concatenating all of the elements in an array (or an array-like object), separated by commas or a specified separator string. If the array has only one item, then that item will be returned without using the separator.’

然后，我们使用.join()方法。 通过连接数组(或类似数组的对象)中的所有元素(用逗号或指定的分隔符字符串分隔)，创建并返回新字符串。 如果数组只有一个项目，则该项目将不使用分隔符而返回。

This was just a basic example of using the array data structure to achieve a specific output. We put the string into an array which then allowed us to achieve the desired outcome.

这只是使用数组数据结构实现特定输出的一个基本示例。 我们将字符串放入一个数组中，然后使我们能够实现所需的结果。

Arrays are great for fast lookups, accessing which index you want to look up, or adding onto the end of an array or taking an element off the end of an array, it is also ordered in memory. However, it is slow for inserts and deletes and finally, if you are using a static array then it is a fixed size.

数组非常适合快速查找，访问要查找的索引，添加到数组的末尾或将元素从数组的末尾移开，它也可以在内存中排序。 但是，插入和删除速度很慢，最后，如果您使用的是静态数组，则它的大小是固定的。