任务一 分析电子商务网站栏目结构,网站无障碍建设报告,海口免费网站建设,担保公司网站建设方案LinkedList 是 Java 集合框架中常用的数据结构之一#xff0c;位于 java.util 包中。它实现了 List、Deque 和 Queue 接口#xff0c;是一个双向链表结构#xff0c;适合频繁的插入和删除操作。 1. LinkedList 的特点 数据结构#xff1a;基于双向链表实现#xff0c;每个…LinkedList 是 Java 集合框架中常用的数据结构之一位于 java.util 包中。它实现了 List、Deque 和 Queue 接口是一个双向链表结构适合频繁的插入和删除操作。 1. LinkedList 的特点 数据结构基于双向链表实现每个节点包含 数据部分存储值。前驱指针指向前一个节点。后继指针指向后一个节点。 实现接口 List支持按索引随机访问、插入和删除操作。Deque支持双端队列操作。Queue支持队列操作。 操作特性 插入和删除效率高在头部或尾部插入和删除操作的时间复杂度为 O ( 1 ) O(1) O(1)。随机访问效率低需要遍历链表查找元素时间复杂度为 O ( n ) O(n) O(n)。 2. LinkedList 的构造方法
LinkedList 提供了以下两种构造方法 无参构造 LinkedListInteger list new LinkedList();创建一个空的链表。 带集合参数的构造 ListInteger arrayList Arrays.asList(1, 2, 3);
LinkedListInteger list new LinkedList(arrayList);使用另一个集合初始化链表。 3. 常用方法
LinkedList 继承了 List 和 Deque 的所有方法。以下是常用方法的分类及示例
3.1 添加元素
尾部添加list.add(10); // 在尾部添加元素指定位置添加list.add(1, 20); // 在索引 1 处插入元素 20头部添加list.addFirst(5); // 在头部添加元素尾部添加list.addLast(15); // 在尾部添加元素3.2 删除元素
删除头部元素list.removeFirst(); // 删除并返回头部元素删除尾部元素list.removeLast(); // 删除并返回尾部元素删除指定位置元素list.remove(2); // 删除索引 2 处的元素删除指定值list.remove(Integer.valueOf(10)); // 删除第一个匹配值为 10 的元素3.3 获取元素
头部或尾部元素list.getFirst(); // 返回头部元素
list.getLast(); // 返回尾部元素指定位置元素list.get(2); // 返回索引 2 处的元素3.4 检查元素
是否包含某个元素list.contains(20); // 检查链表是否包含值为 20 的元素是否为空list.isEmpty(); // 检查链表是否为空3.5 迭代元素
普通 for 循环for (int i 0; i list.size(); i) {System.out.println(list.get(i));
}增强 for 循环for (Integer num : list) {System.out.println(num);
}使用迭代器IteratorInteger iterator list.iterator();
while (iterator.hasNext()) {System.out.println(iterator.next());
}3.6 双端队列操作
LinkedList 实现了 Deque 接口支持双端队列的操作。
入队头部或尾部list.offerFirst(1); // 在头部添加元素
list.offerLast(2); // 在尾部添加元素出队头部或尾部list.pollFirst(); // 删除并返回头部元素
list.pollLast(); // 删除并返回尾部元素3.7 栈操作
LinkedList 也可以用作栈支持栈的基本操作。
压栈list.push(10); // 将元素压入栈顶头部出栈list.pop(); // 弹出栈顶元素头部4. 示例代码
以下是一个综合使用 LinkedList 的示例
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedListInteger list new LinkedList();// 添加元素list.add(10);list.add(20);list.add(30);list.addFirst(5);list.addLast(40);System.out.println(链表内容: list);// 删除元素list.removeFirst();list.removeLast();list.remove(Integer.valueOf(20));System.out.println(删除元素后的链表: list);// 获取元素System.out.println(头部元素: list.getFirst());System.out.println(尾部元素: list.getLast());// 检查元素System.out.println(是否包含 30: list.contains(30));// 使用栈操作list.push(50); // 压栈System.out.println(压栈后的链表: list);list.pop(); // 出栈System.out.println(出栈后的链表: list);// 使用队列操作list.offerFirst(5); // 入队头部list.offerLast(60); // 入队尾部System.out.println(使用队列操作后的链表: list);// 遍历元素System.out.println(遍历链表:);for (Integer num : list) {System.out.println(num);}}
}输出
链表内容: [5, 10, 20, 30, 40]
删除元素后的链表: [10, 30]
头部元素: 10
尾部元素: 30
是否包含 30: true
压栈后的链表: [50, 10, 30]
出栈后的链表: [10, 30]
使用队列操作后的链表: [5, 10, 30, 60]
遍历链表:
5
10
30
605. LinkedList 的时间复杂度
操作时间复杂度原因插入头部/尾部 O ( 1 ) O(1) O(1)双向链表操作直接修改指针即可删除头部/尾部 O ( 1 ) O(1) O(1)双向链表操作直接修改指针即可按索引访问元素 O ( n ) O(n) O(n)需要从头部或尾部遍历到指定位置查找某个元素 O ( n ) O(n) O(n)遍历整个链表插入/删除中间位置 O ( n ) O(n) O(n)需要先遍历找到位置然后修改指针 6. LinkedList 的优缺点
优点
适合频繁插入和删除操作。实现了多种接口List、Deque、Queue功能强大。支持双端操作头部和尾部操作都高效。
缺点
随机访问性能差需要遍历链表时间复杂度为 O ( n ) O(n) O(n)。占用额外的内存空间指针存储前驱和后继节点。 7. 总结 适用场景 数据插入和删除频繁的场景如队列、栈操作。数据大小较小链表的额外内存开销可以接受。 不适用场景 随机访问频繁的场景推荐使用 ArrayList 。
通过合理选择数据结构可以根据具体需求提高程序性能和代码效率。
