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) 过程，因为内部索引访问只是 [第一个成员的地址] + [偏移量].

追加对象(在数组末尾插入)是相对较快的分摊 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-链接.这个优势允许两个链表之间尾部共享.尾部共享使使用链表作为写时复制数据结构变得容易.

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