首先看一下LinkedList的声明
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
AbstractSequentialList 分析
官方文档的解释如下
This class provides a skeletal implementation of the <tt>List</tt> interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), <tt>AbstractList</tt> should be used in preference to this class.<p>
意思大概就是对于随机访问的数据或者数组,应优先使用AbstractSequentialList,即
E get(int index) E set(int index, E element)void add(int index, E element)E remove(int index)boolean addAll(int index, Collection<? extends E> c)
上面的这几个接口都是随机访问的
实现List<E>可以有list的特性
实现Deque,可以使用双端队列访问元素的方法,是一个双向链表
实现Cloneable,可以实现克隆对象的全部元素
实现java.io.Serializable,可以实现序列化
常量
// 元素个数transient int size = 0;// 指向头指针transient Node<E> first;// 指向末尾指针transient Node<E> last;
构造方法
// 无参构造方法,生成空的链表 public LinkedList() { } // 构建一个包含指定元素集合的列表,顺序有Collection的iterator返回 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
节点结构
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 * 先拿到当前头结点定义为f,定一个新的节点newNode,pre指向null,元素为e,next指向f * 在修改新的头节点为newNode * 判断拿到的头节点f是否为空,如果为空last为newNode,此时链表就一个元素newNode * 如果不为空,f的pre节点指向newNode新创建的节点 * size ++ * modCount 涉及修改数据结构都要修改的值,即修改统计数,用来实现fail-fast机制 */ 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 f.prev = newNode; size++; modCount++; }
末尾节点添加元素
/** * 末尾节点添加元素e * 获取当前尾部节点last为l * 定义新节点newNode,pre为l,元素为e,next为null * 定义现在last尾部节点为newNode * 如果刚才首次获取尾部节点l为null,头部节点改为newNode,此时链表就y一个元素 * 如果不为null,l的next节点就为我们的newNode * 元素个数添加 * 修改次数添加,和上面类似 */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
在非null元素succ之前插入元素
/** * 在非null元素succ之前插入元素e * 拿到succ的pre节点pred * 创建newNode节点保存我们要插入的数据,pre为刚才取得pred节点,元素为e,next为succ * 修改succ的pre节点为创建的newNode节点 * 判断如果pred拿出的为null,即pred就是头节点,first为newNode * 不为null,pred的next节点为新创建的newNode * 修改元素个数size * 修改次数添加 */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
取消链接非空的第一个节点
/** * 取消第一个节点f的链接 * 取出f节点元素element * 取出f的后置节点next * 然后把f的元素值置为null,next置为null,置为nullgc更快回收 * 链表的头节点定义为刚才取出的后置节点next * 判断next节点是否为空,如果为null,last也为null,链表为k空 * 不为null next的前置节点置为null * 元素个数减少1 * 修改次数添加 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
取消链接的最后一个节点
/** * 取消链接的最后一个非k空节点l * 取出l节点的元素element * 取出l节点的前置节点prev * l元素置为null,pre前置节点置为null * 链表的last置为f节点的pre节点prev * 判断如果pre节点为null,链表first头节点为null * 不为null,prev的后置节点置为null断开元素的链接 * 元素个数减少1 * 修改次数添加 */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
取消链接非空节点
/** * 取消链接非空节点x * 分别取到x节点的元素值element,前置节点prev,后置节点next * 如果元素x的前置节点为null,链表的first 指向next节点,如果不为null,prev节点的next执行元素x的next节点 * 如果元素x的后置节点为null,链表的last节点为x的prev前置节点,不为null,元素x后置节点的pre指向x的前置节点 * x元素值置为null * 元素减少1 * 修改次数添加 */ 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; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
获取链表的第一个元素
/** * 拿到first指向的元素 * 判断是否为null,为null抛出NoSuchElementException()list为空异常 * 不为null,返回f.item的元素本身 */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
获取链表的最后一个元素
/** * 根据last拿到链表的最后一个元素值 * 判断last是否为null,如果为null,返回list为空的异常 * 不为null,返回l.item元素本身 */ public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
删除链表中第一个元素并返回
/** * 拿到first第一个元素 * 如果为null,抛出list为empty的异常 * 不为null调用unlinkFirst(f)方法来取消元素的链接 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
删除链表中最后一个元素并返回
/** * 根据last获取链表的最后一个元素 * 如果为null,抛出list为empty的异常 * 不为null调用unlinkLast(l)方法,取消最后一个元素的链接 */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
指定元素添加到链表头部
/** * 直接调用linkFirst(e)方法添加 */ public void addFirst(E e) { linkFirst(e); }
指定元素添加到链表尾部
/** * 调用linkLast(e)方法尾部添加元素e */ public void addLast(E e) { linkLast(e); }
判断链表中是否包含元素
/** * 判断链表是否包含元素o * 调用indexOf(o)方法,indexOf方法见下面解析,返回元素的索引,找不到或者索引不存在返回-1 */ public boolean contains(Object o) { return indexOf(o) != -1; }
indexOf(Object o)
/** * 返回元素o在此链表中 【首次】出现的位置 * 如果list不包含元素o,返回-1 * 更正式的说,返回元素的索引,如果索引值不存在返回-1 */ 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; }
获取list元素个数
public int size() { return size; }
添加一个元素
/** * 添加一个元素e * 调用linkLast(e)在队列的尾部添加元素 * 返回true */ public boolean add(E e) { linkLast(e); return true; }
删除一个元素
/** * 如果元素o存在的话,移除首次出现的元素,即最小索引的元素, * 如果元素o为null,移除首次出现的null元素 * 如果元素o不在list中,不做任何改变 * 如果元素o匹配上,调用unlink(o)方法来删除元素 */ 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; }
addAll 方法添加指定的集合元素
public boolean addAll(Collection<? extends E> c) { // 从什么位置开始添加,此处从原list的末尾开始添加元素集合c return addAll(size, c); } /** * index: 开始添加元素的位置 * c: 要添加的元素集合 */ 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; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true;}
清空list,删除所有的元素
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
get(index)
/** * 返回指定位置的元素 * 检测index索引是否有效 * 返回index索引位置元素 */ public E get(int index) { checkElementIndex(index); return node(index).item; }
指定位置覆盖原先位置元素
/** * 检验index是否有效 * 获取index位置节点 * 替换node节点item */ public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
指定位置后面添加元素(原索引位置元素以及之后的元素右移,索引位置放置新元素)
/** * 校验index索引是否有效 * 判断如果index等于list数组元素数量,就调用linkLast(element) 尾部添加元素 * 不等于就调用linkBefore(elemetn,node(index))在元素之前插入 */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
移除元素
/** * 校验index索引是否有效 * 调用unlink(node)方法取消链接 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index); }
好了,LinkedList源码按摩就到此结束了,如有错误欢迎指出,共同进步,以便下次提供更好的按摩服务