本文主要是介绍LinkedList源码分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 一、LinkedList源码
  • 1、概述
  • 2、数据结构
• 二、源码分析
  • 1、继承结构
  • 2、属性
  • 3、构造器
    • addAll(Collection):boolean——在尾部批量插入
    • addAll(int, Collection):boolean——批量插入
    • checkPositionIndex(int):void——判断下标合理性
    • node(int):Node方法——返回原链表中index的节点
  • 4、List接口
    • 4.1 add(E):boolean方法
    • linkLast(E):void——在尾部插入节点
    • 4.2 add(int, E):void——指定位置插入节点
    • linkBefore(E, Node):void——在指定节点前插入节点
    • 4.3 get(int):E——查找
    • 4.4 remove(int):E——删除指定位置元素
    • unlink(E):E——删除指定元素的节点
    • 4.5 clear():void——清除链表
    • 4.6 indexOf(Object):int——查找元素，返回下标
  • 5、Duque接口
    • 5.1 addFirst(E):void——在链表头插入指定元素
    • 5.2 addLast(E):void——在链表尾插入指定元素
• 三、总结
  • 1、LinkedList和ArrayList的差别

一、LinkedList源码

1、概述

（1）LinkedList底层维护了一个双向链表

（2）LinkedList中维护了两个属性first和last分别指向首节点和尾节点

（3）每个节点（Node对象）里又维护了prev（指向前一节点），next（指向后一节点），item（用于保存数据）三个属性，从而实现双链表

（4）因此元素的添加和删除效率较高

2、数据结构

LinedList底层是一个双链表：相较于数组更耗费空间，但删除和插入节点很快

二、源码分析

1、继承结构

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

（1）继承

（2）接口

• List接口：LinkedList类再次实现List接口并没有实际用处
• Serializable接口：实现该序列化接口，表明该类可以被序列化
• Cloneable接口：可以使用Object.Clone方法，该方法可以克隆
• 与ArrayList类相比，LinkedList还实现了Deque接口：该接口主要声明了队头队尾的一系列方法

2、属性

transient int size = 0;//记录节点个数

transient Node<E> first;//first引用指向头节点

transient Node<E> last;//last引用指向尾节点

底层存储节点数据的Node内部类——节点为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、构造器

（1）无参构造器——空链表

public LinkedList() {
}

（2）LinkedList(Collection<? extends E>)——有参构造器

public LinkedList(Collection<? extends E> c) {
    this();//调用无参构造器
    addAll(c);//批量插入方法
}

addAll(Collection):boolean——在尾部批量插入

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//调用插入方法——addAll(int, Collection)
}

addAll(int, Collection):boolean——批量插入

public boolean addAll(int index, Collection<? extends E> c) {//传入节点个数和初始化参数
    checkPositionIndex(index);//检查下标合理性

    Object[] a = c.toArray();//将c集合转换为Object数组a
    int numNew = a.length;//记录数组长度
    if (numNew == 0)//数组长度为0
        return false;//返回false，初始化失败

    Node<E> pred, succ;//声明该节点的前驱节点和后继节点
    if (index == size) {//如果下标等于节点个数，即从尾部加入
        succ = null;//后继节点置空
        pred = last;//前驱节点指向老链表的last节点
    } else {//从指定位置添加节点
        succ = node(index);//后继节点指向原index处节点
        pred = succ.prev;//前驱节点指向原index处节点的前驱节点
    }

    for (Object o : a) {//遍历存放c集合的数组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;//newNode指向后继节点
        succ.prev = pred;//后继节点指向newNode
    }

    size += numNew;//元素长度更新
    modCount++;//操作次数++
    return true;//插入成功
}

checkPositionIndex(int):void——判断下标合理性

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))//若下标不合理，则抛出异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {//下标大于等于0且小于等于size返回true
    return index >= 0 && index <= size;
}

node(int):Node方法——返回原链表中index的节点

Node<E> node(int index) {//二分法查找法
    // assert isElementIndex(index);

    if (index < (size >> 1)) {//index小于size的二分之一，从头节点开始查找
        Node<E> x = first;//新建x指向first节点
        for (int i = 0; i < index; i++)//找到原链表中下标为index的节点
            x = x.next;
        return x;//返回原链表中下标为index的节点
    } else {//下标在后半部分，从尾节点开始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

4、List接口

4.1 add(E):boolean方法

将元素添加到链表尾部

public boolean add(E e) {
    linkLast(e);//尾部插入节点
    return true;
}

linkLast(E):void——在尾部插入节点

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);//新节点的前驱节点为原链表尾节点，新节点的后继节点指向空，新节点的元素为e
    last = newNode;//尾节点更新
    if (l == null)//前驱节点为空
        first = newNode;//首节点更新
    else
        l.next = newNode;//前驱节点指向新节点
    size++;//链表长度++
    modCount++;//操作次数++
}

4.2 add(int, E):void——指定位置插入节点

public void add(int index, E element) {
    checkPositionIndex(index);//下标合理性检测

    if (index == size)//下标等于节点个数，尾部插入
        linkLast(element);//调用尾部插入方法
    else//指定位置插入
        linkBefore(element, node(index));
}

linkBefore(E, Node):void——在指定节点前插入节点

void linkBefore(E e, Node<E> succ) {//传入新节点元素e和原链表该下标的节点
    // assert succ != null;
    final Node<E> pred = succ.prev;//前驱节点指向index前节点
    final Node<E> newNode = new Node<>(pred, e, succ);//新建节点
    succ.prev = newNode;//后继节点的前驱节点指向新节点
    if (pred == null)//前驱节点为空
        first = newNode;//首节点更新
    else//不为空
        pred.next = newNode;//前驱节点的后节点指向新节点
    size++;
    modCount++;
}

4.3 get(int):E——查找

public E get(int index) {
    checkElementIndex(index);//下标合理性检测
    return node(index).item;//调用node返回index节点属性item，即节点元素数据
}

4.4 remove(int):E——删除指定位置元素

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
    //node(index)：返回节点
}

unlink(E):E——删除指定元素的节点

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;//x的前驱节点置空
    }

    if (next == null) {//后继为空
        last = prev;
    } else {
        next.prev = prev;//后节点的前驱节点指向前节点
        x.next = null;//x的后继节点置空
    }

    x.item = null;//x元素置空
    size--;//size--
    modCount++;//操作次数++
    return element;//返回删除的元素
}

4.5 clear():void——清除链表

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;//next指向x后节点
        x.item = null;//节点元素置空
        x.next = null;//x的后继节点置空
        x.prev = null;//x的前驱节点置空
        x = next;//更新x
    }
    first = last = null;//首节点尾节点置空
    size = 0;//size更新
    modCount++;//操作参数++
}

4.6 indexOf(Object):int——查找元素，返回下标

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

5、Duque接口

该接口主要声明了队头队尾的一系列方法

5.1 addFirst(E):void——在链表头插入指定元素

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
        f.prev = newNode;
    size++;
    modCount++;
}

5.2 addLast(E):void——在链表尾插入指定元素

public void addLast(E e) {
    linkLast(e);
}

三、总结

1、LinkedList和ArrayList的差别

（1）LinkedList内部使用链表实现，相比于ArrayList更加耗费空间

（2）LinkedList插入，删除节点不用大量copy原来的元素，效率更高

（3）LinkedList查找元素使用遍历，效率一般

（4）LinkedList同时是双向队列的实现

这篇关于LinkedList源码分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！