链接列表与向量 [英] Linked List vs Vector

问题描述

在过去的几天里，我一直在为我的第一次电话面试准备软件开发工作。在研究问题时，我提出了这篇文章。

每一件事情都很棒，直到我到了这段话，

你什么时候使用链表和矢量？

从经验和研究这两个非常不同的数据结构，一个链表是一个动态数组，一个向量是空间中的2d点。我可以看到两者之间的唯一关联是，如果您使用向量作为链表，说 myVector（我的值，指向邻居的指针）

想法？

解决方案

矢量是的.wikipedia.org / wiki / Dynamic_array。它是用于 C ++中的动态数组数据结构的名称。如果您有Java经验，您可以使用名称 ArrayList 了解它们。 （Java还有一个名为Vector的旧集合类，由于设计的问题而不被使用。）

向量适用于随机读取和插入，在后面删除（采取摊销的常数时间），但不利于前面或任何其他位置的插入和删除（线性时间，因为项目必须移动）。向量通常在存储器中连续布置，因此遍历一个是有效的，因为CPU存储器缓存被有效地使用。

链接列表对于在前面或后面（常量时间）插入和删除项目都是有好处的，但对于其他方面来说不是特别好：例如，删除一个项目列表中间的任意索引需要线性时间，因为您必须首先找到该节点。另一方面，一旦找到一个特定的节点，你可以删除它，或者在一段时间之后插入一个新的项目，你不能使用一个向量。链接列表也很容易实现，这使得它们成为流行的数据结构。

Over the past few days I have been preparing for my very first phone interview for a software development job. In researching questions I have come up with this article.

Every thing was great until I got to this passage,

"When would you use a linked list vs. a vector? "

Now from experience and research these are two very different data structures, a linked list being a dynamic array and a vector being a 2d point in space. The only correlation I can see between the two is if you use a vector as a linked list, say myVector(my value, pointer to neighbor)

Thoughts?

解决方案

Vector is another name for dynamic arrays. It is the name used for the dynamic array data structure in C++. If you have experience in Java you may know them with the name ArrayList. (Java also has an old collection class called Vector that is not used nowadays because of problems in how it was designed.)

Vectors are good for random read access and insertion and deletion in the back (takes amortized constant time), but bad for insertions and deletions in the front or any other position (linear time, as items have to be moved). Vectors are usually laid out contiguously in memory, so traversing one is efficient because the CPU memory cache gets used effectively.

Linked lists on the other hand are good for inserting and deleting items in the front or back (constant time), but not particularly good for much else: For example deleting an item at an arbitrary index in the middle of the list takes linear time because you must first find the node. On the other hand, once you have found a particular node you can delete it or insert a new item after it in constant time, something you cannot do with a vector. Linked lists are also very simple to implement, which makes them a popular data structure.

这篇关于链接列表与向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！