LinkedList
是 Java 中的一个双向链表实现的类,它实现了 List
接口,同时也实现了 Deque
接口,因此可以用作列表、队列或双端队列。下面是关于 LinkedList
的基本介绍和细节讨论:
基本介绍:
-
LinkedList
是一个双向链表实现,每个节点包含了当前元素的值、指向前一个节点的引用和指向下一个节点的引用。 -
它实现了
List
接口,因此具备了列表的功能,支持随机访问、添加、删除等操作。 -
由于是链表实现,它在插入和删除元素时的性能通常比数组实现的
ArrayList
更好。 -
它同时也实现了
Deque
接口,因此支持队列和双端队列的操作。
细节讨论:
-
LinkedList
允许元素为null
。 -
由于是链表结构,它在随机访问时的性能较差,需要遍历链表来找到对应索引的元素。
-
插入和删除元素的性能较好,因为只需要改变节点的引用即可,而不需要像数组那样进行元素的移动。
-
LinkedList
内部使用双向链表结构,因此在插入和删除元素时不需要像ArrayList
那样进行数组元素的移动。 -
LinkedList
不适合大量随机访问的场景,适合在插入和删除元素频繁的情况下使用。 -
LinkedList
在使用迭代器遍历时,性能可能会比ArrayList
稍差,因为它需要在链表中移动节点。 -
LinkedList
的内存消耗会稍微大于ArrayList
,因为每个节点需要保存额外的前后节点的引用。
适用场景:
-
当需要频繁地在列表的任意位置插入或删除元素时,可以考虑使用
LinkedList
。 -
当需要实现队列或双端队列时,
LinkedList
是一个不错的选择,因为它实现了Deque
接口。 -
不适合需要频繁随机访问元素的场景,因为它的随机访问性能较差。
总之,LinkedList
是一种适合特定场景的数据结构,特别适用于需要频繁插入和删除元素的情况。在选择使用时,应根据具体的应用场景和性能需求进行权衡。
双向列表的代码:
public class LinkListExpandCode {
public static void main(String[] args) {
Node ret1 = new Node("ret1");
Node ret2 = new Node("ret2");
Node ret3 = new Node("ret3");
ret1.next = ret2;
ret2.next = ret3;
ret3.pre = ret2;
ret2.pre = ret1;
Node first = ret1;
Node last = ret3;
//从头遍历
while (true){
if(first == null){
break;
}
System.out.println(first);
first = first.next;
}
//从尾遍历
while (true){
if(last == null){
break;
}
System.out.println(last);
last = last.pre;
}
//插入对象
Node ret = new Node("ret");
ret.next = ret3;
ret.pre = ret2;
ret2.next = ret;
ret3.pre = ret;
//遍历
//遍历之前先将first恢复原位,因为之前从头开始遍历的时候first到尾部了
first = ret1;//first恢复原位
//从头遍历
while (true){
if(first == null){
break;
}
System.out.println(first);
first = first.next;
}
//删除对象
ret2.next = ret3;
ret3.pre = ret2;
//从头遍历
first = ret1;//first恢复原位
while (true){
if(first == null){
break;
}
System.out.println(first);
first = first.next;
}
}
}
class Node{
//模拟双向列表
private Object name;
public Node pre;//注意这里的类型是Node类型,因为在main方法中pre和next要作为引用指向别的结点
public Node next;
public Node(Object name) {
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"name=" + name +
'}';
}
}
LinkList的源码:
public class LinkListCRUD {
public static void main(String[] args) {
/*
*
* 源码(以增为例):
第一步
public LinkedList() {
}
第二步
public boolean add(E e) {
linkLast(e);
return true;
}
第三步
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//Node类
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
*
* */
LinkedList linkedList = new LinkedList();
//增
linkedList.add("ret1");
linkedList.add("ret2");
linkedList.add("ret3");
System.out.println(linkedList);
//删
linkedList.remove("ret2");
System.out.println(linkedList);
//改
linkedList.set(1,"ret2");
System.out.println(linkedList);
//查
System.out.println(linkedList.contains("ret2"));
System.out.println(linkedList.get(1));
}
}
Java中LinkList和ArrayList的比较与选择:
LinkedList
和 ArrayList
都是 Java 中常用的集合类,它们分别基于链表和动态数组的数据结构实现,各有优劣。下面是它们的比较与选择的一些方面:
性能比较:
-
随机访问:
ArrayList
在随机访问时性能优于LinkedList
,因为ArrayList
底层使用数组,可以通过索引直接访问元素,而LinkedList
需要遍历链表才能访问指定索引的元素。 -
插入和删除:
LinkedList
在插入和删除元素时性能优于ArrayList
,因为链表插入和删除只需要改变节点的引用,而不需要移动元素。而ArrayList
在插入和删除时需要移动元素来保持连续性。
内存消耗:
-
LinkedList
需要额外的空间存储前后节点的引用,因此内存消耗稍高于ArrayList
。 -
ArrayList
需要预分配数组空间,当元素个数增加时可能需要进行扩容,扩容时需要重新分配数组并复制元素,可能会导致内存重新分配的开销。
迭代性能:
- 在使用迭代器遍历集合时,
ArrayList
的性能通常优于LinkedList
,因为ArrayList
在数组中连续存储元素,迭代时可以更高效地访问。
适用场景:
-
如果需要频繁进行随机访问操作,使用
ArrayList
更合适,例如需要根据索引获取元素或进行快速遍历。 -
如果需要频繁进行插入和删除操作,特别是在中间位置进行插入和删除,使用
LinkedList
更合适,因为链表插入和删除操作性能更好。
综合考虑:
-
如果对集合的操作类型不确定,或者需要在不同操作间取得平衡,可以根据实际场景进行选择。
-
如果对性能要求不高,且操作类型多样,可以优先选择
ArrayList
,因为它在大多数情况下都表现得很好。 -
如果需要根据不同操作类型进行优化,也可以根据操作的频率和性质来选择使用
ArrayList
或LinkedList
。文章来源:https://www.toymoban.com/news/detail-674012.html
综合来说,选择使用 ArrayList
还是 LinkedList
取决于具体的使用场景和操作类型。如果可能,可以根据实际需求进行性能测试和评估,以便选择最适合的集合类。文章来源地址https://www.toymoban.com/news/detail-674012.html
到了这里,关于Java中LinkList的基本介绍和细节讨论。双向链表的代码和LinkList的源码。LinkList和ArrayList的比较与选择。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!