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

问题描述

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

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,

你什么时候会使用链表和向量?"

现在根据经验和研究，这是两种截然不同的数据结构，链表是动态数组，向量是空间中的二维点.我能看到两者之间的唯一相关性是，如果您使用向量作为链表，例如 myVector(my value, pointer to neighbor)

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)

想法?

推荐答案

Vector 是动态数组的另一个名称.它是用于 C++ 中的动态数组数据结构 的名称.如果您有 Java 方面的经验，您可能知道它们的名称 ArrayList.(Java 还有一个名为 Vector 的旧集合类，由于其设计方式存在问题，现在已不再使用.)

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.)

向量有利于后面的随机读取和插入和删除(需要分摊常数时间)，但不利于前面或任何其他位置的插入和删除(线性时间，因为项目必须移动).向量通常在内存中连续排列，因此遍历一个是有效的，因为 CPU 内存缓存得到了有效利用.

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屋！