C++中的动态数组VS链表

Question

当我们有动态数组列表时,为什么我们需要一个链表？

我研究过静态列表和链表.我有动态数组列表的知识.但我无法找到任何人之间的确切区别请帮助我回答这个问题

Answer 1

动态数组是一个数组,可根据内容的数量向上或向下调整自身大小.

优点:

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

• 追加对象(在数组末尾插入)是相对快速摊销的O(1).与在数组末尾删除对象相同的性​​能特征.注意:在数组末尾附近追加和删除对象也称为push和pop.

坏处:

• 在动态数组中随机插入或移除对象是非常慢的O(n/2),因为它必须每次移动(平均)一半的数组.特别差的是在阵列开始附近插入和移除,因为它必须复制整个阵列.

• 插入或移除时不可预测的性能需要调整大小

• 有一些未使用的空间,因为动态数组实现通常会分配超过必要的内存(因为调整大小是一个非常慢的操作)

Linked List是一个具有一般结构的对象[head, [tail]],head是数据,tail是另一个Linked List.链表有很多版本:奇异LL,双LL,圆LL等.

优点:

• 快速O(1)在列表中的任何位置插入和删除,因为链接列表中的插入只会破坏列表,插入并修复它(不需要复制尾部)

• 链表是一个持久的数据结构,很难用简短的句子来解释,参见:wiki-link.这个优点允许两个链表之间的尾部共享.尾部共享使链接列表易于使用作为写时复制数据结构.

坏处:

• 慢O(n)索引访问(随机访问),因为通过索引访问链表意味着您必须递归循环遍历列表.

• 糟糕的地方,用于链表的内存散落在乱七八糟的地方.与之相反,在内存中使用连续地址的数组.数组(稍微)受益于处理器缓存,因为它们彼此接近

其他:

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

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

这取自这个问题的最佳答案

我对这个答案深信不疑.