为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

除了插入和删除方便之外,链表的内存表示方式也不同于数组。对于链表中的元素数量没有限制,而在数组中,您必须指定元素的总数。 看看这篇文章。

其他回答

链表

它更可取的时候,它涉及到插入!基本上它所做的就是处理指针

1 -> 3 -> 4

插入(2)

1... 3... 4 ... 2

最后

1 -> 2 -> 3 -> 4

一个箭头指向3点,另一个箭头指向2点

简单!

但是来自Array

| | 1 | 3 | 4

插入(2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

任何人都可以想象出其中的不同! 对于4个索引,我们执行3个步骤

如果数组长度是一百万呢?数组有效吗? 答案是否定的!:)

删除也是一样! 在链表中,我们可以简单地使用指针并将对象类中的元素和next置空! 但对于数组,我们需要执行shiftLeft()

希望有帮助!:)

这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。

A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.

例如,在Java环境中,使用Eclipse调试器,调试ArrayList将显示一个非常容易理解的结构:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

另一方面,查看LinkedList的内容并找到特定的对象变成了一个展开树的噩梦,更不用说过滤LinkedList内部信息所需的认知开销:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。

It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.