一、引言
在Java的集合框架中,LinkedList类是一个双向链表实现的List接口。与ArrayList不同,LinkedList在插入和删除元素时具有更高的效率,因为不需要像ArrayList那样在内部数组中进行大量的元素移动。LinkedList还提供额外的操作,如addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast()等,这些操作使得在链表的头部和尾部进行插入和删除操作变得非常简单。
二、LinkedList类的基本用法
01、创建LinkedList对象
创建一个类型为String的LinkedList对象。
LinkedList<String> list = new LinkedList<>();
02、添加元素
使用add()方法向LinkedList中添加元素。该方法默认将元素添加到链表的尾部。例如:
list.add("元素1");
list.add("元素2");
list.add("元素3");
还可以使用addFirst()和addLast()方法将元素添加到链表的头部和尾部:
list.addFirst("头部元素");
list.addLast("尾部元素");
03、访问元素
使用get()方法通过索引访问LinkedList中的元素。例如:
String element = list.get(1); // 获取索引为1的元素,即"元素2"
还可以使用getFirst()和getLast()方法获取链表的第一个和最后一个元素:
String firstElement = list.getFirst(); // 获取第一个元素
String lastElement = list.getLast(); // 获取最后一个元素
04、删除元素
使用remove()方法通过索引删除LinkedList中的元素。例如:
list.remove(1); // 删除索引为1的元素,即"元素2"
还可以使用removeFirst()和removeLast()方法删除链表的第一个和最后一个元素:
list.removeFirst(); // 删除第一个元素
list.removeLast(); // 删除最后一个元素
remove()方法还有一个重载版本,接受一个元素作为参数,并删除链表中第一个与该元素相等的元素(如果存在的话):
list.remove("元素1"); // 删除第一个值为"元素1"的元素
遍历LinkedList
使用for-each循环或迭代器来遍历LinkedList中的元素。例如:
// 使用for-each循环遍历
for (String element : list) {
System.out.println(element);
}
// 使用迭代器遍历
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
三、内部结构与实现原理
LinkedList的核心在于内部维护一个双向链表结构。链表中的每个元素(或称为节点)都由三个部分组成:所存储的数据、指向下一个节点的引用(next)和指向前一个节点的引用(prev)。这种设计允许高效地进行插入和删除操作,而无需移动其他元素,与基于数组实现的ArrayList相比,在这些操作上有显著优势。
四、节点类(Node)
在LinkedList内部,存在一个名为Node的静态内部类,封装链表节点的具体实现。每个Node对象包含如下属性:
属性 | 描述 |
E item | 存储的数据元素。 |
Node<E> next | 指向链表中下一个节点的引用。 |
Node<E> prev | 指向前一个节点的引用。 |
五、特性概览
特性 | 描述 |
动态大小 | 链表的长度可以在运行时动态改变,无需预先分配固定大小的内存。 |
增删高效 | 由于直接通过节点引用调整链表结构,插入和删除操作的时间复杂度为O(1)。 |
查询较慢 | 相比于数组,链表查询某个元素需要从头或尾开始遍历,时间复杂度为O(n)。 |
双向遍历 | 支持正向和反向遍历,这得益于每个节点都有前后指针。 |
多用途 | 作为List使用时支持索引访问,作为Deque时提供首尾操作方法,如addFirst, addLast, peekFirst, peekLast等。 |
六、注意事项
事项 | 描述 |
线程安全性 | LinkedList不是线程安全的。在多线程环境下,若需保证线程安全,可使用Collections.synchronizedList(new LinkedList<...>())将其转换为线程安全的列表。 |
内存占用 | 每个节点除了存储数据外,还需额外空间存储前后节点的引用,相较于数组实现,链表在内存使用上可能更不经济。 |
七、总结
LinkedList是Java集合框架中的一个重要类,提供基于双向链表的数据结构。与ArrayList相比,LinkedList在插入和删除元素时具有更高的效率,特别是在链表的头部和尾部进行操作时。在实际开发中,可以根据具体的需求选择合适的集合类来存储和操作数据。