为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
维基百科上有很好的章节介绍了它们的区别。
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)。
编辑:澄清一下,我在这里指的是无序意义上的“合并”,而不是归并排序。也许"串联"这个词更合适。
除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。
但坦率地说,我从未使用过链表。每当我需要快速插入和删除时,我也需要快速查找,所以我使用HashSet或Dictionary。
根据你的语言,可以考虑以下一些缺点和优点:
C编程语言:当使用链表(通常是通过结构指针)时,必须特别注意不要泄漏内存。正如前面提到的,链表很容易洗牌,因为我们所做的只是改变指针,但是我们会记得释放所有的东西吗?
Java: Java具有自动垃圾收集功能,因此内存泄漏不会成为问题,但是对于高级程序员来说,隐藏了链表的实现细节。从列表中间删除节点等方法的过程比该语言的一些用户所期望的要复杂得多。