文章目录

前言
初识LinkedList
源码解析
- 添加元素
- 删除元素
- 更改元素
- 查询元素
- 内部类
LinkedList 和 ArrayList 的对比

前言

上篇文里讲解了ArrayList ，它是基于List 接口来实现的，今天讲解Java集合类中另一个跟List相关的集合类，叫做LinkedList 。

初识LinkedList

LinkedList 是基于双向链表实现的，也就是说，链表中任何一个存储单元都可以通过向前或者向后的指针获取到前面或者后面的存储单元。在 LinkedList 的源码中，其存储单元用一个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;
    }
}

可以看到，Node 中包含了三个成员，分别是存储数据的

item

，指向前一个存储单元的节点

prev

和指向后一个存储单元的节点

next

，用图片来表示就是这样：

Java集合类：LinkedList前言初识LinkedList源码解析LinkedList 和 ArrayList 的对比

源码解析

依照惯例，深入源码前先看下类中的成员变量

transient int size = 0;				//链表长度

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;			//指向头一个节点

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;				//指向最后一个节点

知道变量后就是对具体方法的解析了。之前就说过，对一个集合类我们都是最关注的就是它的增删改查元素操作，了解了这些操作的源码也就基本了解容器的核心思想了。

先看添加元素的方法源码。

添加元素

LinkedList 中包含了不少插入元素的方法，就使用来说，我们一般调用下面这三个方法：

transient int size = 0;			//链表长度

//普通插入方法，直接添加元素到尾部
public boolean add(E e) {
    linkLast(e);
    return true;
}
//在指定位置添加元素
public void add(int index, E element) {
	//判断index是否在范围内
    checkPositionIndex(index);
	//如果指定位置是尾部，就直接添加到尾部
    if (index == size)
    linkLast(element);
    //否则插入到指定位置
    else
    linkBefore(element, node(index));
}
//添加一整个集合
public boolean addAll(Collection<? extends E> c) {
   return addAll(size, c);
}

三个方法的代码比较简单，其核心逻辑是调用其他的方法来实现，我们可以看到源码中调用了几个方法：

linkLast(e)

、

linkBefore(e)

、

addAll(e)

，下面他们的源码：

//插入到头部
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
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 获取指定节点 succ 前面指向的节点
    final Node<E> pred = succ.prev;
    //新建一个节点，向前指针指向pred，向后指向 succ 节点，数据为 e
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    //如果 succ 前面的节点为空，直接把新节点作为链表的头结点
    if (pred == null)
    first = newNode;
    else
    pred.next = newNode;
    size++;
    modCount++;
 }
 //添加一个集合对象
 public boolean addAll(Collection<? extends E> c) {
     return addAll(size, 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;
            //创建新节点，前指针指向 pred
            Node<E> newNode = new Node<>(pred, e, null);
            //如果 pred 为空，说明新建的这个是头节点
            if (pred == null)
                first = newNode;
            else
            	//新建节点为pred 后指针指向的节点
                pred.next = newNode;
            //pred 后移一位
            pred = newNode;
        }
		//如果 succ 为空，说明要插入的位置就是尾部，现在 pred 已经到最后了
        if (succ == null) {
            last = pred;
        } else {
        //否则 pred 指向后面的元素
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

几个方法的逻辑并不复杂，基本都是通过改变要插入位置的节点的指针指向来插入元素，这样一来插入元素的复杂度就为O(1)，性能是比较好的。

删除元素

LinkedList 中删除元素的方法也是比较多的，我们只介绍常用的几个

//删除头部节点
public E remove() {
    return removeFirst();
}
//删除第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
    throw new NoSuchElementException();
    return unlinkFirst(f);
}
//删除最后的元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
    throw new NoSuchElementException();
    return unlinkLast(l);
}
//删除指定位置节点
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
//删除包含指定元素的节点
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;
    }

源码中可以看出，删除方法中调用了几个方法，例如

unlinkFirst

，

unlink

，

unlinkLast

，跟添加元素的方法相似，这几个方法也是通过修改对应节点的前后节点指向来操作元素位置，并把对应位置的节点置为null。

//删除头节点，并返回该节点的数据
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，置为null,方便GC回收
    //把头节点后面的节点变成第一个节点
    first = next;
    //如果next为空，说明删除的节点是链表唯一的节点
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
//删除尾部节点并返回数据
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;
}
//删除指定的节点，返回数据    
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;
}

更改元素

更改元素的方法比较简单，开放的方法只有一个，那就是

set

public E set(int index, E element) {
    checkElementIndex(index);
    //获取对应位置节点
    Node<E> x = node(index);
    //更改数据
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
 }

查询元素

因为实现了 List 接口，LinkedList 的查询方法也是比较丰富的，最直接的就是使用 get()

//获取对应索引的元素，调用的node的遍历操作
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

还有重写了List 接口中的

indexOf

，

lastIndexOf

等，

//返回指定元素第一次出现的位置
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;
}
//查询最后一次出现的位置
public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

值得说明的是，LinkedList 的查询方法都是通过遍历链表的方式进行的，如果链表的数据过长，那么查找某个元素所需的时间将会耗费很多，从这点上看，LinkedList 查询的效率是比较差的。

内部类

关键的增删改查方法就说到这儿了，从原理上其实并不复杂，本质上都是针对节点的前后节点指向操作。除了这些方法外，LinkedList 中还提供了几个内部类，其中就包括了可以逆向输出元素的迭代器

DescendingIterator

，这是Jdk1.6之后加进来的

public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}
/**
 * Adapter to provide descending iterators via ListItr.previous
 */
 //逆向遍历元素，其实就是从最后一个一直往前遍历
private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

以及一个类似Iterator 接口的类

ListItr

，可以帮我们对List进行遍历，增删改查等，其实就跟 LinkedList 的内部操作元素方法差不多，这里展示部分的源码

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    ..........
}

还有Jdk1.8之后加的一个特殊类

LLSpliterator

，大概用途是将元素分割成多份，开启多个线程去做遍历，以提高效率。我大概看了一下，具体的内部实现还是挺有东西的，因为用的不多，我对于这个内部类也不是特别了解，就不多班门弄斧了，顺便也贴下部分代码吧，

@Override
public Spliterator<E> spliterator() {
    return new LLSpliterator<E>(this, -1, 0);
}

/** A customized variant of Spliterators.IteratorSpliterator */
static final class LLSpliterator<E> implements Spliterator<E> {
    static final int BATCH_UNIT = 1 << 10;  // batch array size increment
    static final int MAX_BATCH = 1 << 25;  // max batch array size;
    final LinkedList<E> list; // null OK unless traversed
    Node<E> current;      // current node; null until initialized
    int est;              // size estimate; -1 until first needed
    int expectedModCount; // initialized when est set
    int batch;            // batch size for splits

    LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
        this.list = list;
        this.est = est;
        this.expectedModCount = expectedModCount;
    }

    final int getEst() {
        int s; // force initialization
        final LinkedList<E> lst;
        if ((s = est) < 0) {
            if ((lst = list) == null)
                s = est = 0;
            else {
                expectedModCount = lst.modCount;
                current = lst.first;
                s = est = lst.size;
            }
        }
        return s;
    }
    ........
 }

LinkedList 和 ArrayList 的对比

源码方面的学习就到这里了，最后说一个老生常谈的问题，那就是关于LinkedList 和 ArrayList 两者之间的比较，这也是比较常见的面试题，大概也就这么几点：

结构

LinkedList 是双向链表结构，ArrayList 是基于数组

添加、删除效率

LinkedList 中添加/删除元素只会影响周围的两个节点，开销较低；
ArrayList 添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；

占用内存

LinkedList 的节点不仅要维护数据，还有维护前后两个节点，一般情况下，耗用内存高于ArrayList

查询速度

ArrayList 基于数组，查询的时候直接根据索引找到元素，时间复杂度为O(1)；
LinkedList查询时只能做顺序遍历，要么从头结点开始遍历，要么从尾节点开始遍历，比起按索引搜索元素慢多了，因此查询效率不高；

线程安全

两者的方法都没有做同步，是非线程安全的，如有需要，可用 Collections.synchronizedList 来包住容器实例。

Java集合类：LinkedList前言初识LinkedList源码解析LinkedList 和 ArrayList 的对比

文章目录

前言

初识LinkedList

源码解析

添加元素

删除元素

更改元素

查询元素

内部类

LinkedList 和 ArrayList 的对比

继续阅读

interface可以多继承吗

Java集合类面试题总结Java集合类面试题

ArrayList初见

集合初始化大小汇总

LinkedHashSet详解LinkedHashSet详解

ArrayList源码剖析1. 属性2. 构造器3. get 方法4. add 方法5. set 方法6. remove方法7. grow 方法8. size 方法9. indexOf 方法10. Vector 类

Java集合汇总(全)

JDK源码【集合框架】Java集合框架概述

【源码】LinkedHashMap源码剖析

迭代器的并发修改异常

java集合类源码解析(1)---类关系简介

Java集合类框架学习 4.2 —— HashMap(JDK1.7)

Java集合类框架学习 4.3 —— HashMap(JDK1.8)

Java集合类框架学习 4.1 —— HashMap(JDK1.6)

java--HashSet详解