我注意到在Java中,您可以创建LinkedList对象...但使用与数组/列表/序列相同的方法(如.add()、.get()等)对待它。
那么,LinkedList在内部是类似于数组的序列吗?
在Java中,LinkedList的工作方式和你期望的一样。如果你使用官方的Collections LinkedList,那么它确实是一个一堆对象通过'下一个'和有时'前一个'相互连接的数据结构。
是的,它有一个get(int index)
方法,这令人惊讶,因为这不是LinkedList擅长的操作方式。要查找第index
个元素,你需要从开头开始计数,并逐步遍历列表,这并不高效。它存在的原因是LinkedList实现了List接口,所有类型的列表都可以使用该接口。
然而,当你经常通过get(int index)
方法访问LinkedList时,你应该尽量避免使用它,因为这会导致效率低下。你可能最好使用ArrayList。
LinkedList是一个实体链,每个实体都知道下一个实体, 所以get(index)操作需要使用计数器在这个链上进行迭代。 但是这个列表针对按位置添加和删除进行了优化(在需要将元素放入列表或从中间删除元素的情况下,链表的表现更好)。
可以使用链表来实现像数组一样工作的对象。与数组相比,某些操作将更快,而某些操作将更慢。例如,对于接近末尾的元素调用get()
可能会比使用数组慢得多。但是,这仍然是可能的。
另一方面,从链表中间删除一个元素将比使用数组执行相应操作更快。
不完全是。链表由集合提供,并且通过良好的设计,您可以创建双向链表。现在它不像数组,因为这些对象将没有索引,并且不是容器内的元素,即列表。因此,您需要定义下一个和上一个,并指定下一步操作。它们都具有相同的方法,因为它们再次像我说的那样是集合。
在内部,它将使用所谓的“slab分配器”--这基本上是一系列小数组的链表。每次添加一个对象时,它会检查slab中是否有空间,如果有,则将对象放在那里。否则,它会分配一个新的slab并将对象放在slab的第一个元素中。
这种技术最小化了内存分配开销--如果您向链接列表添加大量项目,那将是许多小内存分配,这需要很长时间,而slab分配器可以将其最小化。
java.util.LinkedList
的源代码,您可以在JDK安装目录下的文件src.zip
中找到。 - Jesper