为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
数组和链表之间的区别在于,数组是基于索引的数据结构,每个元素都与一个索引相关联,而链表是使用引用的数据结构,每个节点都被引用到另一个节点。在数组大小是固定的,而在链表大小是不固定的。
其他回答
为什么是链表而不是数组?有些人已经说过,插入和删除的速度更快。
但也许我们不需要生活在两者的限制下,同时获得两者的优点……是吗?
对于数组删除,您可以使用'Deleted'字节来表示一行已被删除的事实,因此不再需要重新组织数组。为了减轻插入或快速更改数据的负担,可以使用链表。然后,在引用它们的时候,让你的逻辑先搜索一个,再搜索另一个。因此,将它们结合使用可以使您获得两者的最佳效果。
If you have a really large array, you could combine it with another, much smaller array or linked list where the smaller one hold thes 20, 50, 100 most recently used items. If the one needed is not in the shorter linked list or array, you go to the large array. If found there, you can then add it to the smaller linked list/array on the presumption that 'things most recently used are most likey to be re-used' ( and yes, possibly bumping the least recently used item from the list ). Which is true in many cases and solved a problem I had to tackle in an .ASP security permissions checking module, with ease, elegance, and impressive speed.
维基百科上有很好的章节介绍了它们的区别。
Linked lists have several advantages over arrays. Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller. On the other hand, arrays allow random access, while linked lists allow only sequential access to elements. Singly-linked lists, in fact, can only be traversed in one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays is also faster than on linked lists on many machines due to locality of reference and data caches. Linked lists receive almost no benefit from the cache. Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.
http://en.wikipedia.org/wiki/Linked_list
这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。
数组和链表之间的区别在于,数组是基于索引的数据结构,每个元素都与一个索引相关联,而链表是使用引用的数据结构,每个节点都被引用到另一个节点。在数组大小是固定的,而在链表大小是不固定的。
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.