LinkedList

概述1. 类2. 属性3. 方法无参构造有参构造add() addLast() linkLast()addFirst() linkFirst()addAll()remove() unlink()indexOf()

概述

LinkedList 是 List 的一个实现, 底层使用双向链表, 支持 O(1) 获取头节点和尾节点

底层使用双向链表, 因此插入, 删除速度较快, 查询较慢。

双向链表每次插入删除节点时注意判断头尾节点，头结点的 prev 为空， 尾节点的 next 为空

1. 类

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { ...... }

继承实现关系图

继承 AbstractSequentialList 抽象类, 实现了相关的 Collection 和 List的方法实现了 List 接口实现了 Clone 接口, 重写了clone()方法实现了 Deque 队列接口, 可以把LinkedList 当做双端队列来操作实现了 Serializable 接口, 可以序列化

2. 属性

// LinkedList 包含的元素数量 transient int size = 0; // 头结点 transient Node<E> first; // 尾节点 transient Node<E> last;

三个属性都被标记成 transient 是因为序列化和反序列化都需要遍历整个链表. 该类写了 writeObject() 和 readObject() 两个方法来自定义实现序列化。

静态内部类 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. 方法

无参构造

public LinkedList() { }

有参构造

public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

add() addLast() linkLast()

public boolean add(E e) { // 尾插法, 单独封装出来 linkLast(e); return true; } public void addLast(E e) { linkLast(e); } // 双向链表尾插法 void linkLast(E e) { final Node<E> l = last; // 新节点构造, 直接设置 prev , next 和 item final Node<E> newNode = new Node<>(l, e, null); // 改变尾节点指针指向 last = newNode; // 判断上一节点是否为空 if (l == null) // 空表明该节点是头结点 first = newNode; else // 非空设置上一节点的 next 指向新节点 l.next = newNode; // 元素数量自增 size++; modCount++; }

addFirst() linkFirst()

public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; // 构建新节点 final Node<E> newNode = new Node<>(null, e, f); // 设置头结点 first = newNode; // 判断下一个节点是否为空 if (f == null) // 为空则表明该节点就是尾节点 last = newNode; else // 非空则设置下一节点的 pre 等于新节点 f.prev = newNode; size++; modCount++; }

addAll()

注意索引范围检查, 插入位置判断, 头尾节点的判断修改，以及添加完后与之前的节点连接。

public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { // 检查index >= 0 && index <= size checkPositionIndex(index); // 取出 Collection 中的元素 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; // 如果要插入的地方是尾部, 则pred上一个节点就是尾节点last if (index == size) { succ = null; pred = last; } else { // 如果不是, 则pred节点应该是index节点的上一个节点 succ = node(index); pred = succ.prev; } for (Object o : a) { // 转为泛型 @SuppressWarnings("unchecked") E e = (E) o; // 构建新节点, 设置prev 节点和 item Node<E> newNode = new Node<>(pred, e, null); // 判断上一个节点是否为空 if (pred == null) // 是空则表明该节点就是头结点 first = newNode; else // 非空则设置上一个节点的 next 指向新节点 pred.next = newNode; // 循环 新节点成为pred pred = newNode; } // 从尾部插入, 尾节点就是最后的pred节点 if (succ == null) { last = pred; } else { // 不是从尾部开始插入, 那么最后一个插入的节点应该与剩下的节点连接起来 pred.next = succ; succ.prev = pred; } // 元素数量增加 size += numNew; modCount++; return true; }

remove() unlink()

循环遍历查找删除, 注意 o.equals() 方法的空指针异常, unlink() 时注意头尾节点的判断以及前后节点指针的修改

public boolean remove(Object o) { // 判空 防止空指针 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; // 如果删除的是头结点, 那么重设头结点为next if (prev == null) { first = next; } else { // 如果删除的不是头结点, 那么修改上个节点的next指向 prev.next = next; x.prev = null; } // 删除的是尾节点 那么重设尾节点 if (next == null) { last = prev; } else { // 如果不是, 那么重设下一个节点的pre next.prev = prev; x.next = null; } // 引用释放, 以便gc回收 x.item = null; size--; modCount++; return element; }

indexOf()

循环遍历查找, 注意先判空, 防止调用 o.equals() 空指针

public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }