为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
为什么有人想要使用链表而不是数组?
这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。
其他回答
Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.
数组Vs链表:
由于内存碎片,阵列内存分配有时会失败。 在数组中缓存更好,因为所有元素都分配了连续的内存空间。 编码比数组更复杂。 与数组不同,在链表上没有大小限制 在链表中插入/删除更快,在数组中访问更快。 从多线程的角度来看,链表更好。
我也认为链表比数组更好。 因为我们在链表中做遍历,而不是在数组中
除了插入和删除方便之外,链表的内存表示方式也不同于数组。对于链表中的元素数量没有限制,而在数组中,您必须指定元素的总数。 看看这篇文章。
使用链接列表的人必须阅读。人们会再次爱上数组的。 它谈到了 无序执行,硬件预取,内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html