据我所知,链表的概念是通过具有'next'和有时'previous'属性来遍历对象而相互连接的一堆对象。
我注意到在Java中,你可以创建一个LinkedList对象…但是,通过使用相同的方法(如.add(), .get()等)将其视为数组/列表/序列。
那么,LinkedList内部是一个类似数组的序列吗?
那么,LinkedList内部是一个类似数组的序列吗?
。它是一个私有嵌套类Entry
的一系列实例,它有next
、previous
和element
引用。注意,您可以通过查看JDK附带的源代码自己发现这一点。
这个内部结构不暴露的原因是它可以防止结构被破坏,例如包含一个循环。通过List
和Deque
接口的统一访问允许多态使用。
Java中的LinkedList就像您期望的那样工作。如果你使用官方的Collections LinkedList,那么它确实是一个,一堆对象通过'next'和'previous'相互连接。
是的,它有一个get(int index)
方法,这是令人惊讶的,因为它不是很有效,因为你需要从一开始就开始计数,找到index
条目,这不是LinkedLists擅长的。它存在的原因是因为LinkedList实现了List接口。这是你在所有列表中都可以做到的。
然而,当你的大部分访问都是通过get(int index)
方法时,你可能会尽量避免使用LinkedList,因为这显然是最低效的。你可能会更好地使用数组列表
LinkedList是一个实体链,其中每个实体都知道下一个实体,所以get(index)操作需要用counter遍历这个链。但是这个列表优化了按位置添加和删除(如果我需要将元素放入列表或从中间链表中删除元素,则性能更好)
据我所知,linkedlist就像你在第一段说的那样。每个对象都有两个引用,分别叫做它的前一个引用和它的下一个引用。不像数组是按顺序工作的(在C中,它是按顺序存储的)。我认为Java就是这样做的,这就是为什么我们不能重新调整数组的大小),列表通过引用工作。所以逻辑上它比array慢
可以使用链表实现像数组一样工作的对象。与数组相比,有些操作会更快,有些会更慢。例如,在链表中对接近末尾的元素调用get()
可能比在数组中要慢得多。但是,还是有可能的。
另一方面,从链表中间删除一个元素将比使用数组进行相应的操作要快。
不完全是。链表是由集合提供的,通过良好的设计,您可以创建双链表。现在它不像数组,因为这些对象没有索引,也不是容器中的元素,即列表。因此,你要通过定义下一步和前一步,并决定下一步是什么。它们都有相同的方法,因为它们都是集合。
那么,LinkedList内部是一个类似数组的序列吗?
NO是双链表的实现
在内部,它将使用所谓的'slab分配器'——这基本上是一个小数组的链表。每次添加对象时,它都会检查slab中是否有空间,如果有,就把对象放在那里。否则,它将分配一个新的slab,并将对象放在该slab的第一个元素中。
这种技术最小化了内存分配开销——如果您向链表中添加了很多项,那么将会有很多小的内存分配,这将花费很多时间,而slab分配器将会最小化