详解Java LinkedList
LinkedList简介LinkedList是List接口的实现类，基于双向链表实现，继承自AbstractSequentialList类，同时也实现了Cloneable、Serializable接口。此外还实现了Queue和Deque接口，可以作为队列或双端队列使用。
https://img2023.cnblogs.com/blog/1669883/202311/1669883-20231101135439274-1399626466.png
LinkedList的插入删除时间复杂度：
[*]在头部或尾部插入删除元素，只需要修改头节点或尾节点的指针即可完成，时间复杂度为O(1)；
[*]在其他位置插入删除元素，需要遍历到指定位置，再修改指定节点的指针，平均要移动n/2个位置，时间复杂度为O(n)。
LinkedList没有像ArrayList有RandomAccess接口的标记，因为LinkedList基于链表实现，链表节点之间的内存地址不连续，只能通过指针来定位，因此无法实现快速随机访问。
常用方法
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
//添加元素
linkedList.add(2);
linkedList.addFirst(1);
linkedList.add(3);
linkedList.add(4);
linkedList.addLast(5);
//获取元素
System.out.println(linkedList.get(1));
System.out.println(linkedList.getFirst());
System.out.println(linkedList.getLast());
//创建双端队列
Deque<String> deque = new LinkedList<>();
//元素入队
deque.offer("a");
deque.offer("b");
deque.offer("c");
//获取队头元素，但不删除队头元素
System.out.println(deque.peek());
//元素出队
String a = deque.poll();
System.out.println(a);
}
}LinkedList核心源码分析
下面以JDK17的LinkedList代码进行分析。
类属性
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//LinkedList大小
transient int size = 0;
//首节点
transient Node<E> first;
//尾节点
transient Node<E> last;
}LinkedList中的节点由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;
}
}构造方法
//创建一个空链表对象public LinkedList() {}//传入一个集合，将集合中的元素存入链表public LinkedList(Collection
页:
[1]