详解Java LinkedList

LinkedList简介

LinkedList是List接口的实现类，基于双向链表实现，继承自AbstractSequentialList类，同时也实现了Cloneable、Serializable接口。此外还实现了Queue和Deque接口，可以作为队列或双端队列使用。

LinkedList的插入删除时间复杂度：

• 在头部或尾部插入删除元素，只需要修改头节点或尾节点的指针即可完成，时间复杂度为O(1)；
  
• 在其他位置插入删除元素，需要遍历到指定位置，再修改指定节点的指针，平均要移动n/2个位置，时间复杂度为O(n)。
  

LinkedList没有像ArrayList有RandomAccess接口的标记，因为LinkedList基于链表实现，链表节点之间的内存地址不连续，只能通过指针来定位，因此无法实现快速随机访问。
常用方法

1. public class LinkedListTest {
2.     public static void main(String[] args) {
3.         LinkedList<Integer> linkedList = new LinkedList<>();
4.                 //添加元素
5.         linkedList.add(2);
6.         linkedList.addFirst(1);
7.         linkedList.add(3);
8.         linkedList.add(4);
9.         linkedList.addLast(5);
10.                 //获取元素
11.         System.out.println(linkedList.get(1));
12.         System.out.println(linkedList.getFirst());
13.         System.out.println(linkedList.getLast());
14.                 //创建双端队列
15.         Deque<String> deque = new LinkedList<>();
16.                 //元素入队
17.         deque.offer("a");
18.         deque.offer("b");
19.         deque.offer("c");
20.                 //获取队头元素，但不删除队头元素
21.         System.out.println(deque.peek());
22.                 //元素出队
23.         String a = deque.poll();
24.         System.out.println(a);
25.     }
26. }

复制代码

LinkedList核心源码分析

下面以JDK17的LinkedList代码进行分析。
类属性

1. public class LinkedList<E>
2.     extends AbstractSequentialList<E>
3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
4. {
5.         //LinkedList大小
6.     transient int size = 0;
8.     //首节点
9.     transient Node<E> first;
11.     //尾节点
12.     transient Node<E> last;
13. }

复制代码

LinkedList中的节点由Node定义：

1. private static class Node<E> {
2.         E item; //节点值
3.         Node<E> next; //后继节点
4.         Node<E> prev; //前驱节点
6.         Node(Node<E> prev, E element, Node<E> next) {
7.                 this.item = element;
8.                 this.next = next;
9.                 this.prev = prev;
10.         }
11. }

复制代码

构造方法

[code]//创建一个空链表对象public LinkedList() {}//传入一个集合，将集合中的元素存入链表public LinkedList(Collection