目录
1. 是什么
底层由双向链表实现的顺序表
有序、可以重复
2. 如何使用
public class LinkedListTest { public static void main(String[] args) { LinkedList<String> list = new LinkedList<>(); list.add("1"); list.add("2"); list.addFirst("3"); list.addLast("4"); System.out.println(list); list.remove(0); list.remove("2"); list.remove(); list.removeFirst(); list.removeLast(); } } 3. 原理分析
3.1. uml
可以看出LinkedList是个List、双端队列、可序列化、可克隆
3.2. 构造方法
由头节点、尾节点、长度构成
public class LinkedList<E> extends AbstractSequentialList<E>//提供了List的骨架实现 implements List<E>/*List接口*/, Deque<E>/*双端队列*/, Cloneable, java.io.Serializable { //属性 transient int size = 0;//长度 transient Node<E> first;//头节点 transient Node<E> last;//尾节点 //构造方法 public LinkedList() { } } 3.2.1. 队列的节点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; } } 结构如下图：
3.3. add方法
- O（1）
public boolean add(E e) { //调用linkLast方法 linkLast(e); return true; } 3.3.1. 插入到链表尾部
- linkLast
void linkLast(E e) { //保存尾节点 final Node<E> l = last; //构造新的节点，prev指向last节点 final Node<E> newNode = new Node<>(l, e, null); //把尾节点更新为新的节点 last = newNode; //如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点 if (l == null) first = newNode; else //否则更新尾节点的next为新的节点 l.next = newNode; size++; modCount++; } 3.3.2. 构造新节点【prev指向尾节点，next为null】
//保存尾节点 final Node<E> l = last; //构造新的节点，prev指向last节点 final Node<E> newNode = new Node<>(l, e, null); 3.3.3. 更新尾节点
//如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点 if (l == null) first = newNode; else //否则更新尾节点的next为新的节点 l.next = newNode; 3.3.4. 更新size
size++; 3.4. addLast方法
- O（1）
public void addLast(E e) { //调用linkLast linkLast(e); } - linkLast
参考add方法
3.5. addFirst方法
- O（1）
public void addFirst(E e) { //简单的调用linkFirst linkFirst(e); } 3.5.1. 头部插入节点
- linkFirst
private void linkFirst(E e) { //先保存原头节点 final Node<E> f = first; //新建节点，next指向原头节点 final Node<E> newNode = new Node<>(null, e, f); //更新头节点为新的节点 first = newNode; //如果原头节点为空，那么是第一个元素，更新last节点为新的节点 if (f == null) last = newNode; else //否则更新原头节点的prev为新的节点 f.prev = newNode; size++; modCount++; } 3.5.2. 构造新节点【prev指向null，next指向头节点】
//先保存原头节点 final Node<E> f = first; //新建节点，next指向原头节点 final Node<E> newNode = new Node<>(null, e, f); 3.5.3. 更新头节点
//如果原头节点为空，那么是第一个元素，更新last节点为新的节点 if (f == null) last = newNode; else //否则更新原头节点的prev为新的节点 f.prev = newNode; 3.5.4. 更新size
size++; 3.6. remove方法【根据下标删除】
-
O（N）
-
修改这个元素的前后元素的next和prev指针
public E remove(int index) { //检查是否越界 checkElementIndex(index); //根据下标找到相应的节点，并把这个节点删除 return unlink(node(index)); } 3.6.1. 遍历找到这个位置的元素
- node
Node<E> node(int index) { // assert isElementIndex(index); //索引在链表左半部分 if (index < (size >> 1)) { //从头节点往右找 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; //索引在链表右半部分 } else { //从尾节点往左找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 3.6.2. 更新该节点前后节点的指针
E unlink(Node<E> x) { // assert x != null; //首先保存当前节点的prev，next，和item值 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //更新prev if (prev == null) { //前一个节点为空（说明当前节点是头节点），那么把first指向当前节点的下一个节点即可 first = next; } else { //前一个节点的next指向当前节点的下一个节点 prev.next = next; //help gc x.prev = null; } //更新next if (next == null) { //后一个节点为空（说明当前节点是尾节点），那么把last指向当前节点的上一个节点即可 last = prev; } else { //后一个节点的prev指向当前节点的上一个节点 next.prev = prev; //help gc x.next = null; } //help gc x.item = null; size--;//更新size modCount++; return element; } 3.7. remove方法【按照元素删除】
- O（N）
public boolean remove(Object o) { //==null if (o == null) { //遍历找到node for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } //equals } else { //遍历找到node for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } 3.7.1. 遍历找到这个元素
for (Node<E> x = first; x != null; x = x.next) { //... } 3.7.2. 更新该节点前后节点的指针
3.8. remove方法【无参】
- O（1）
public E remove() { //简单调用removeFirst return removeFirst(); } 3.8.1. 删除头部节点
- removeFirst
public E removeFirst() { //头节点 final Node<E> f = first; if (f == null) //为null直接抛出异常 throw new NoSuchElementException(); //调用unlinkFirst从链表删除头节点 return unlinkFirst(f); } 3.8.2. 把原来头节点的next节点更新为头节点
- unlinkFirst
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; //保存item，next final E element = f.item; final Node<E> next = f.next; // help GC f.item = null; f.next = null; //first直接指向头节点的next first = next; //如果头节点的next为空，说明链表中只有一个节点 if (next == null) //更新last指向null last = null; else //否则更新头节点的next节点的prev指针 next.prev = null; size--; modCount++; return element; } 3.9. removeLast方法
- O（1）
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } 3.9.1. 把原来尾节点的prev节点更新为尾节点
- unlinkLast
private E unlinkLast(Node<E> l) { // assert l == last && l != null; //保存尾节点的item值和prev final E element = l.item; final Node<E> prev = l.prev; // help GC l.item = null; l.prev = null; //更新last为原尾节点的prev last = prev; //只有一个元素 if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
