LinkedList源码分析

此源码分析JDK版本为1.7,只是简单分析,算是个人看源码的一点小总结,随意性比较强,专业的还需百度。
先简单介绍一下LinkedList,LinkedList为直线型的链表结构,时间复杂度为O(n)。ArrayList内部存储为数组,LinkedList内部存储为节点Node。以下所有表达LinkedList的内容统称为链表。

简介

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

属性

//链表大小
transient int size = 0;
//链表头部节点
transient Node<E> first;
//链表尾部节点
transient Node<E> last;

构造方法

//无初始化集合构造方法
public LinkedList() {
}
//初始化集合构造方法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

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;
    }
}

方法

//将值放置第一个节点(私有),此方法可发现增加效率比ArrayList高很多,无需移动其他节点
private void linkFirst(E e) {
    //将链表第一个节点地址赋予f
    final Node<E> f = first;
    //创建节点对象
    final Node<E> newNode = new Node<>(null, e, f);
    //将新的节点对象地址赋予first
    first = newNode;
    //如果f为空,则说明之前链表没有节点
    if (f == null)
        //最后一个节点即第一个节点
        last = newNode;
    else
        //f不为空,则f的上一个节点为第一个节点(节点f由第一个变为第二个)
        f.prev = newNode;
    //大小+1
    size++;
    //修改次数+1
    modCount++;
}
//将值放置最后一个节点(default,该类及同包可使用),add()会调用该方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
void linkLast(E e) {
    //将链表第一个节点地址赋予l
    final Node<E> l = last;
    //创建节点对象
    final Node<E> newNode = new Node<>(l, e, null);
    //将新的节点对象地址赋予last 
    last = newNode;
    //如果l为空,则说明之前链表没有节点
    if (l == null)
        //第一个节点即最后一个节点
        first = newNode;
    else
        //l不为空,则l的下一个节点为最后一个节点(节点l由倒数第一个变为倒数第二个)
        l.next = newNode;
    //大小+1
    size++;
    //修改次数+1
    modCount++;
}
//在succ节点前加入e(default,该类及同包可使用),add()方法会调用该方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
void linkBefore(E e, Node<E> succ) {
    //succ不能为null(方法声明为default,则说明不为null的话,succ一定存在于该链表)
    // assert succ != null;
    //succ的上一个节点赋予pred
    final Node<E> pred = succ.prev;
    //创建节点对象(上个节点:pred,当前节点:e,下一个节点:succ)
    final Node<E> newNode = new Node<>(pred, e, succ);
    //将新的节点对象赋予为succ的上一个节点
    succ.prev = newNode;
    //pred为null则说明succ为第一个节点
    if (pred == null)
        //将新的节点对象作为第一个节点
        first = newNode;
    else
        //pred不为null则说明不是第一个对象,将新的节点对象作为pred的下一个对象
        pred.next = newNode;
    //大小+1
    size++;
    //修改次数+1
    modCount++;
}
//删除第一个节点(私有),remove(),removeFirst()会调用此方法, 此方法可发现移出效率比ArrayList高很多,无需移动其他节点
private E unlinkFirst(Node<E> f) {
    //f不能为null并且f必须是第一个节点
    // assert f == first && f != null;
    //获取当前节点f的值
    final E element = f.item;
    //获取当前节点f的下一个节点
    final Node<E> next = f.next;
    //将当前节点f置null
    f.item = null;
    //将f下个节点置null
    f.next = null; // help GC
    //将next赋予第一个节点
    first = next;
    //如果next为null则说明该链表只有f一个节点
    if (next == null)
        //将last置null
        last = null;
    else
        //如果next不为null则说明该链表不止一个节点,将next的上一个节点置null(此时next为第一个节点)
        next.prev = null;
    //大小-1
    size--;
    //修改次数+1
    modCount++;
    return element;
}
//删除最后一个节点(私有),此方法可发现移出效率比ArrayList高很多,无需移动其他节点
private E unlinkLast(Node<E> l) {
    //l不能为null并且l必须是最后一个节点
    // assert l == last && l != null;
    //获取当前节点l的值
    final E element = l.item;
    //获取当前节点l的上一个节点
    final Node<E> prev = l.prev;
    //将当前节点l的值置null
    l.item = null;
    //将l下个节点置null
    l.prev = null; // help GC
    //将prev赋予最后一个节点
    last = prev;
    //如果prev为null则说明该链表只有f一个节点
    if (prev == null)
        //将first 置null
        first = null;
    else
        //如果prev不为null则说明该链表不止一个节点,将prev的下一个节点置null(此时prev为最后一个节点)
        prev.next = null;
    //大小-1
    size--;
    modCount++;
    //修改次数+1
    return element;
}
//移出x节点(default,该类及同包可使用),remove(index/o)会调用此方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
E unlink(Node<E> x) {
    //x不能为null(方法声明为default,则说明不为null的话,succ一定存在于该链表)
    // assert x != null;
    //将节点x的值赋予element
    final E element = x.item;
    //将节点x的下个节点赋予next
    final Node<E> next = x.next;
    //将节点x的上个节点赋予prev
    final Node<E> prev = x.prev;

    //当prev为null,说明x节点为第一个节点
    if (prev == null) {
        //将next赋予为第一个节点
        first = next;
    } else {
        //当prev不为null,说明x节点为中间节点,将下个节点赋予为上个节点的下个节点
        prev.next = next;
        //x节点的下个节点置null
        x.prev = null;
    }

    //当next为null,说明x节点为最后一个节点
    if (next == null) {
        //将prev赋予为最后一个节点
        last = prev;
    } else {
        //当next不为null,说明x节点为中间节点,将上个节点赋予为上个节点的上个节点
        next.prev = prev;
        //x节点的上个节点置null
        x.next = null;
    }

    //x节点的值置null
    x.item = null;
    //大小-1
    size--;
    //修改次数+
    modCount++;
    return element;
}
//获取第一个节点的值
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
//获取最后一个节点的值
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
//移除第一个节点的值
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    //调用unlinkFirst()方法
    return unlinkFirst(f);
}
//移除最后一个节点值
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    //调用unlinkLast()方法
    return unlinkLast(l);
}
//将值放置第一个节点
public void addFirst(E e) {
    //调用linkFirst()方法
    linkFirst(e);
}
//将值放置最后一个节点
public void addLast(E e) {
    //调用linkLast()方法
    linkLast(e);
}
//获取元素的第一个下标
public int indexOf(Object o) {
    int index = 0;
    //如果o为null,则遍历所有节点查询(说明LinkedList是支持null值的)
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            //因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该后++)
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            //因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该后++)
            index++;
        }
    }
    //无该值
    return -1;
}
//获取元素的最后一个下标
public int lastIndexOf(Object o) {
    int index = size;
    //如果o为null,则遍历所有节点查询(说明LinkedList是支持null值的)
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            //因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该先--)
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            //因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该先--)
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
//是否包含值
public boolean contains(Object o) {
    //indexOf()方法解析可发现此方法会遍历所有,因此应当尽可能少使用
    return indexOf(o) != -1;
}
//返回链表大小
public int size() {
    return size;
}
//增加值
public boolean add(E e) {
    //默认在最后增加节点()
    linkLast(e);
    return true;
}
//删除值
public boolean remove(Object o) {
    //如果值为null,则删除第一个值为null的节点
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                //调用unlink()方法
                unlink(x);
                return true;
            }
        }
    } else {
    //如果值不为null,则删除第一个值为o的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                //调用unlink()方法
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//参数是否为现有元素的索引
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
//是否是迭代器或添加操作的有效位置的索引
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
//检查是否为现有元素的索引
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查是否为迭代器或添加操作的有效位置的索引(最大现有元素下标+1)
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//根据下标获取节点 (类似二分查询法)
Node<E> node(int index) {
    //应当保证是有值下标,但是并没有保证
    // assert isElementIndex(index);

    //如果index小于size的一半,则通过x.next
    if (index < (size >> 1)) {
        //从first开始next
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //如果index大于等于size,则通过x.prev
        //从last开始next
        Node<E> x = prev;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//在index之后加入集合
public boolean addAll(int index, Collection<? extends E> c) {
    //检查下标是否为添加操作的有效位置的索引
    checkPositionIndex(index);

    //转换为数组
    Object[] a = c.toArray();
    //数组a的长度
    int numNew = a.length;
    //如果数组长度为0则返回false
    if (numNew == 0)
        return false;

    //新建pred(上一个节点)、succ(下一个节点)
    Node<E> pred, succ;
    //如果index和链表长度相同,则说明要在最后的位置加入节点
    if (index == size) {
        //下一个节点为null
        succ = null;
        //上一个节点为链表最后一个节点
        pred = last;
    } else {
        //如果index和链表长度不相同,则说明要在中间位置加入节点
        //将当前下标节点赋予succ节点(下一个节点)
        succ = node(index);
        //将当前下标节点的上一个节点赋予pred节点(上一个节点)
        pred = succ.prev;
    }

    //遍历数组a
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //新建一个对象(当前节点:pred,上一个节点:e,下一个节点:null)
        Node<E> newNode = new Node<>(pred, e, null);
        //如果pred为null则说明要在第一个节点前加入此节点
        if (pred == null)
            //将新节点赋予first
            first = newNode;
        else
            //如果pred不为null则说明要在中间位置加入此节点
            //将新节点赋予上个节点的下个节点
            pred.next = newNode;
        //将当前节点赋予上个节点
        pred = newNode;
    }

    //如果index下标的节点为null,则index是链表大小(上方判断)
    if (succ == null) {
        //将上一个节点赋予last
        last = pred;
    } else {
        //如果index下标的节点不为null,则将该节点赋予为上个节点的下个节点
        pred.next = succ;
        //将上个节点赋予index下标的上个节点
        succ.prev = pred;
    }

    //size + 数组长度
    size += numNew;
    //修改次数+1
    modCount++;
    return true;
}
//在最后加入集合
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
//清空链表
public void clear() {
    //清除节点之间的所有链接是“不必要的”,但如果丢弃的节点居住在一代以上,即使有一个可到达的迭代器,也肯定会释放内存,这有助于一代GC。
    // 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
    //遍历去除强引用,使gc下次回收
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    //去除强引用,使gc下次回收
    first = last = null;
    //大小置
    size = 0;
    //修改次数+1
    modCount++;
}
//根据下标获得值
public E get(int index) {
    //检查下标是否为有值下标
    checkElementIndex(index);
    //node(index)查询节点,然后返回值
    return node(index).item;
}
//在下标处设置值
public E set(int index, E element) {
    //检查下标是否为有值下标
    checkElementIndex(index);
    //根绝小标获取节点
    Node<E> x = node(index);
    //旧值
    E oldVal = x.item;
    //新值
    x.item = element;
    //返回旧值
    return oldVal;
}
//在下标处添加值
public void add(int index, E element) {
    //检查下标是否为添加操作的有效位置的索引
    checkPositionIndex(index);

    //如果下标等于链表大小,则说明加入在最后
    if (index == size)
        //将值加入在最后
        linkLast(element);
    else
        //如果下标不等于链表大小则说明要在该下标之前加入
        linkBefore(element, node(index));
}
//移除下标对应的节点
public E remove(int index) {
    //检查下标是否为有值下标
    checkElementIndex(index);
    //移除该节点
    return unlink(node(index));
}
//返回第一个节点,但不删除,如果为null则返回null
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
//返回第一个节点,如果为null则返回null,与peek()无区别
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
//返回最后一个节点的值
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
//返回第一个节点的值(如果为空链则异常,与getFirst()无区别)
public E element() {
    //调用getFirst()
    return getFirst();
}
//查询第一个节点的值并删除(简而言之:出栈)
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//查询第一个节点的值并删除(简而言之:出栈,与pollFirst()无区别)
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//查询最后一个节点的值并删除
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
//查询最后一个节点的值并删除
public E remove() {
    return removeFirst();
}
//添加到最后一个节点(不知道与add(o)有什么区别)
public boolean offer(E e) {
    return add(e);
}
//添加到第一个节点(与addFirst(o)无区别)
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
//添加到最后一个节点(与addLast(o)无区别)
 public boolean offerLast(E e) {
    addLast(e);
    return true;
}
//添加到第一个节点(简而言之:入栈)
public void push(E e) {
    addFirst(e);
}
//返回值并删除第一个节点(简而言之:出栈)
public E pop() {
    return removeFirst();
}
//删除第一个值为o的节点
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}
//删除最后一个值为o的节点
public boolean removeLastOccurrence(Object o) {
    //判断o是否为null
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                //删除该节点
                unlink(x);
                return true;
            }
        }
    } else {
        //如果o不为null
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                //删除该节点
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//获取迭代器
public ListIterator<E> listIterator(int index) {
    //检查是否为迭代器或添加操作的有效位置的索引
    checkPositionIndex(index);
    返回迭代器
    return new ListItr(index);
}
//转换为数组(与ArrayList不同,ArrayList是通过JNI调用本地方法,LinkedList是自己转换)
public Object[] toArray() {
    //新建一个链表大小的数组
    Object[] result = new Object[size];
    int i = 0;
    //遍历并放入数组中
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}
//将链表的值放入数组a中
public <T> T[] toArray(T[] a) {
    //如果a数组的大小小于链表大小
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    //将数组a的地址赋予result
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        //将链表的数据放入result中
        result[i++] = x.item;

    //如果数组a的长度是大于链表大小的,则将a[size]置为null(之前的操作并不会遍历到size下标)
    if (a.length > size)
        a[size] = null;
    //返回数组a(操作result即操作a吗,因为a的地址赋予给了result)
    return a;
}

总结

1.LinkedList允许存在重复的值
2.LinkedList允许存在多个null值
3.remove(o)只会删除第一个o值
4.indexOf(o)只会返回第一值为o的下标
5.尽量减少使用查询的行为,因为查询行为是遍历所有,时间复杂度为O(n)
6.查询少,修改多的地方可使用 例:栈(完美)
7.虽说LinkedList更适合修改场景,但是每次修改是都会通过node(index)进行查询,所以效率还是会有所降低,不过不可避免
8.通过add(),remove()方法可发现修改场景为:node(查询节点,然后增加一个节点即可)
9.add(),addLast(),offer(),offerLast()是一样的

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,681评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,710评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,623评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,202评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,232评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,368评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,795评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,461评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,647评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,476评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,525评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,226评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,785评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,857评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,090评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,647评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,215评论 2 341

推荐阅读更多精彩内容