LinkedList集合特点及源码分析
LinkedList是List接口的实现类
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
继承了AbstractSequentialList类，实现了List、Deque双端队列、Cloneable克隆、Serializable序列化接口
特点：底层是双向链表、查询慢，增删快，线程不安全
LinkedList源码分析
Node是LinkedList内部核心类，双向链表基本结构
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; } }
E ：节点的值
Node next：指向上一个节点的引用
Node prev：指向下一个节点的引用
成员变量
transient int size = 0;//记录LinkedList的大小 transient Node<E> first;//头部节点 transient Node<E> last;//尾部节点
构造函数
1.无参构造
public LinkedList() { }
2.集合类型构造函数
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
public boolean addAll(Collection<? extends E> c) { return addAll(size, c);//传入size=0 }
addAll方法是指定节点位置的后面插入集合
public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index);//检查元素是否合法 Object[] a = c.toArray();//把集合转成数组 int numNew = a.length;//获取数组大小 if (numNew == 0) return false; Node<E> pred, succ;//创建两个节点pred、succ //如果是在元素尾部添加就会满足index == size，或者初始化数组的时候 //第一种情况当构造方法创建的一个空的链表，首次添加的集合进来时候， pred、succ都为null //第二种情况当链表里面有节点，往尾部插入的时候，因为first指向前一个节点，last指向后一个节点，所以再添加一个节点时，succ指向后一个节点=null，pred指向前一个节点，也就是原来的尾部的节点last if (index == size) { succ = null; pred = last; } else {//情况三 这里是指定节点位置插入集合时才会满足这个条件，所以要先获取当前索引的节点 succ = node(index);//根据节点索引获取当前节点succ pred = succ.prev;//获取当前节点的前一个节点pred } //遍历数据将数据插入 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o;//类型转换 Node<E> newNode = new Node<>(pred, e, null);//生成一个新节点 e为当前值，pred指向前一个节点 //情况一是满足pred == null，创建了一个空链表 if (pred == null) first = newNode;//newNode当作第一个节点，再把当前节点赋值给头节点 else //否则就是在尾部添加一个节点， 把新节点作为前一个节点指向的下一个节点 //或者在指定位置插入时，把当前节点作为前一个节点指向的下一个节点 pred.next = newNode; //最后把newNode指向当前节点pred pred = newNode; } //当构造方法创建的一个空的链表时候，succ为空，pred已经是当前节点newNode了， //当链表里面有节点，往尾部插入的时候，最后一个节点就指向当前节点 if (succ == null) { last = pred; } else { // 非空链表插入情况 //在指定位置插入的时候，只需要变更当前节点的前后指向 pred.next = succ; succ.prev = pred; } size += numNew;// 链表大小+num modCount++; // 修改次数加1 return true; }
查询方法
linkFirst(E e)方法
private void linkFirst(E e) { final Node<E> f = first;//获取首节点 final Node<E> newNode = new Node<>(null, e, f);//生成头部节点 e为当前节点值 f为之前的首节点 first = newNode;//因为是头部插入 那么赋值给头部 if (f == null)//首节点为空 说明这里面是空的 last = newNode;//新节点也是 else//把之前首节点的上一个节点指向该节点 f.prev = newNode; size++;//节点数量+1 modCount++;//修改次数加1 }
linkLast(E e)方法
void linkLast(E e) { final Node<E> l = last;//获取尾部节点 final Node<E> newNode = new Node<>(l, e, null);//新增一个尾部节点 l指向之前的尾部节点 e为当前节点 last = newNode;////因为是尾部插入 那么赋值给尾部 if (l == null)//尾部节点为空 说明这里面是空的 first = newNode;//把当前新增节点作为头部节点 else////把之前尾部节点的下一个节点指向该节点 l.next = newNode; size++; modCount++; }
linkBefore(E e, Node succ) 方法
在某个节点钱面追加节点
void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev;//当前节点的上一个节点 final Node<E> newNode = new Node<>(pred, e, succ);//生成新的节点 succ.prev = newNode;//修改当前节点的上一个节点的指向为新节点 if (pred == null)//接着判断一个succ的前一个节点是否为空，如果为空的话，需要把新节点设置为为头结点 first = newNode; else//否则把前一个节点的下一个节点指向当前newNode pred.next = newNode; size++; modCount++; }
node(int index)方法
对查找节点进行了优化
Node<E> node(int 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; } }
getFirst()方法
public E getFirst() { final Node<E> f = first;//获取头部节点 if (f == null) throw new NoSuchElementException();//没有这样的元素 return f.item; }
getLast()方法
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
删除方法
unlinkFirst(Node f)方法
该方法是私有的
删除头部节点，并且修改下一个节点对头部的指向
private E unlinkFirst(Node<E> f) { final E element = f.item;//获取头部节点 final Node<E> next = f.next;//获取头部节点的下一个节点 f.item = null;//将头部节点置为null f.next = null;//头部节点的下一个节点置为null first = next;//将头部节点的下一个节点置为头部节点 if (next == null)//头部节点的下一个节点为null 那么代表后面没有节点了 last = null;//尾部节点为null else next.prev = null;//修改现在头部节点对上一个节点的指向 size--;//数量-1 modCount++;//操作+1 return element;//返回当前头部节点 }
unlinkLast(Node l)方法
同理
private E unlinkLast(Node<E> l) { final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
removeFirst()方法
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);//删除 }
removeLast()方法
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l);//同上 }
pop()方法
public E pop() { return removeFirst();//同上 }
poll()方法
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);//同上 }
其他
push(E e)方法
public void push(E e) { addFirst(e);//同上 }
总结：
- 插入、删除操作很快，只要修改前后指针就OK了，时间复杂度为O(1)
- 访问比较慢，必须得从第一个元素开始遍历，时间复杂度为O(n)
