C ++中的动态数组VS链表 [英] Dynamic array VS linked list in C++

问题描述

为什么拥有动态数组列表时需要链接列表?

Why we need a linked list when we have dynamic array list?

我研究了静态列表和链接列表.我了解动态数组列表.但我无法找出两者之间的确切区别 有人请帮助我回答此问题

I have studied static list and linked list. I have knowledge of dynamic array list. but I couldn't find out the exact difference between that Anyone please help me to answer this

推荐答案

动态数组是根据内容的数量自行调整大小的数组.

Dynamic array is an array that resizes itself up or down depending on the number of content.

优势:

• 通过索引访问和分配是非常快速的O(1)过程，因为内部索引访问只是[address of first member] + [offset].

附加对象(插入数组的末尾)是相对较快摊销的O(1).与删除数组末尾的对象相同的性​​能特征.注意:在数组末尾附近添加和删除对象也称为推入和弹出.

appending object (inserting at the end of array) is relatively fast amortized O(1). Same performance characteristic as removing objects at the end of the array. Note: appending and removing objects near the end of array is also known as push and pop.

缺点:

• 在动态数组中的任意位置插入或删除对象的速度非常慢O(n/2)，因为它每次都必须(平均)移动数组的一半.尤其糟糕的是在数组开始附近插入和删除，因为它必须复制整个数组.

• inserting or removing objects in a random position in a dynamic array is very slow O(n/2), as it must shift (on average) half of the array every time. Especially poor is insertion and removal near the start of the array, as it must copy the whole array.

插入或移除需要调整大小时的性能无法预测

Unpredictable performance when insertion or removal requires resizing

有一些未使用的空间，因为动态数组实现通常会分配比必要数量更多的内存(因为调整大小是非常缓慢的操作)

There is a bit of unused space, since dynamic array implementation usually allocates more memory than necessary (since resize is a very slow operation)

链表是具有[head, [tail]]的常规结构的对象，head是数据，而tail是另一个链表.链表的版本很多:单数LL，双倍LL，循环LL等.

Linked List is an object that have a general structure of [head, [tail]], head is the data, and tail is another Linked List. There are many versions of linked list: singular LL, double LL, circular LL, etc.

优势:

• 快速O(1)插入和删除列表中的任何位置，因为在链接列表中插入仅破坏列表，然后将其修复在一起(无需复制尾部)

• fast O(1) insertion and removal at any position in the list, as insertion in linked list is only breaking the list, inserting, and repairing it back together (no need to copy the tails)

链接列表是一个持久的数据结构，用一句话很难解释，请参见: wiki -link .此优势允许两个链接列表之间的 tail共享.通过尾部共享，可以轻松地将链表用作写时复制数据结构.

Linked list is a persistent data structure, rather hard to explain in short sentence, see: wiki-link . This advantage allow tail sharing between two linked list. Tail sharing makes it easy to use linked list as copy-on-write data structure.

缺点:

• O(n)索引访问缓慢(随机访问)，因为按索引访问链接列表意味着您必须递归地遍历列表.

• Slow O(n) index access (random access), since accessing linked list by index means you have to recursively loop over the list.

位置不佳，用于链接列表的内存零乱地散落着.与之相反，在内存中使用连续地址的数组.阵列(略微)受益于处理器缓存，因为它们彼此靠近

poor locality, the memory used for linked list is scattered around in a mess. In contrast with, arrays which uses a contiguous addresses in memory. Arrays (slightly) benefits from processor caching since they are all near each other

其他:

• 由于链接列表的性质，您必须进行递归思考.不习惯递归函数的程序员在编写链表算法时可能会遇到一些困难(或更糟糕的是，他们可能尝试使用索引).

简而言之，当您要使用需要随机访问的算法时，忘记链接列表.当您要使用需要大量插入和删除的算法时，请不要理会数组.

Simply put, when you want to use algorithms that requires random access, forget linked list. When you want to use algorithms that requires heavy insertion and removal, forget arrays.

此摘录来自此问题

我对这个答案深信不疑.

I am convinced by this answer.

这篇关于C ++中的动态数组VS链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！