以下目录只能预览本篇，请点击右侧目录栏（可滚动）进行内容跳转

• 简介
• 继承体系
• 源码分析
  • 属性
  • 主要内部类
  • 构造方法
  • 添加元素
  • 删除元素
  • 获取元素
  • 修改元素
  • 迭代器
• 栈
• 队列
• 总结
• LinkedList面试题
• Reference

简介

1. LinkedList基于双向链表适用于增删频繁且查询不频繁的场景
2. 线程不安全的且适用于单线程
3. 可以用LinkedList来实现栈和队列.

继承体系

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

1. LinkedList继承了AbstractSequentialList
2. LinkedList实现了List，（集合功能）
3. LinkedList实现了Deque （双端队列功能，模拟栈和队列）
4. LinkedList实现了Cloneable（克隆数组，实现为浅拷贝）
5. LinkedList实现了Serializable（序列化）

源码分析

属性

//集合元素个数
transient int size = 0;
//链表首节点
//判断一个节点是否是第一个节点的条件：
//(first == null && last == null) || (first.prev == null && first.item != null) 
transient Node<E> first;
//链表尾节点
//最后一个节点，判断是否是最后一个节点的条件: 
//(first == null && last == null) || (last.next == null && last.item != null)
transient Node<E> last;

主要内部类

典型的双链表结构。

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

构造方法

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

两个构造方法也很简单，可以看出是一个无界的队列。

添加元素

• 从双端队列角度，添加元素分为addFirst和addLast，内部调用linkFirst和linkLast

• 从集合角度，可以在任意位置添加元素add(int index, E element)

作为双端队列，只能支持在队头队尾添加结点。

//从队头添加元素
public void addFirst(E e) {
    linkFirst(e);
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

//从队头添加元素 主要方法
private void linkFirst(E e) {
    //首节点
    final Node<E> f = first;
	//创建新节点，新节点的next是首节点
    /*
    	new Node<>(null, e, f);
    	等价于
    	node.prev = null;
    	node.val = e;
    	node.next = f;
    */
    final Node<E> newNode = new Node<>(null, e, f);
    //让新节点为新的首节点
    first = newNode;
    // 判断是不是第一个添加的元素
    //如果f为空，说明之前没有元素，所以把最后一个节点也赋值为新节点，first=last=newNode
    //如果f不为空，把f.prev指向newNode, 即newNode.next=f, f.prev=newNode
    if (f == null)		
        last = newNode;
    else
        f.prev = newNode;
    //元素个数加一
    size++;
    //修改次数加1，说明这是一个支持fail-fast的集合
    modCount++;
}

//从队尾添加元素
public void addLast(E e) {
    linkLast(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

//从队尾添加元素 主要方法
void linkLast(E e) {
    //尾节点
    final Node<E> l = last;
    //创建新节点 node.prev=l node.next=null 
    final Node<E> newNode = new Node<>(l, e, null);
    //让新节点为尾节点
    last = newNode;
    //判断是不是第一个添加的元素
    //如果是，将头节点置为新节点 即last=first=newNode
    //否则，将尾节点的next置为新节点 newNode.prev=l, l.next=newNode
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;//元素个数加1
    modCount++;//修改次数加1
}

//队列api  在队尾添加元素值为e的结点
public boolean offer(E e) {
    return add(e);
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

作为List，是要支持在中间添加元素的，主要是通过下面这个方法实现的。

// 在指定index位置处添加元素
public void add(int index, E element) {
    //检查索引是否越界
    checkPositionIndex(index);
	
   	//如果index 是队列尾结点之后的一个位置
    //直接添加到尾结点之后
    //否则调用linkBefore()方法在中间添加节点
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

//获取索引为index位置的结点
Node<E> node(int index) {
	// 所以根据index是在前半段还是后半段决定从前遍历还是从后遍历
	// 这样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;
    }
}	

// 在节点succ之前添加元素
void linkBefore(E e, Node<E> succ) {
    // succ是待添加结点的后置结点
    //找到待添加结点的前置结点 pred
    final Node<E> pred = succ.prev;
    //在其前置节点和后继节点之间创建一个新节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //后置结点的前置指针指向新结点
    succ.prev = newNode;
    //如果前置结点为null，说明是第一个添加的元素，修改first指针
    //否则前置结点的next为新结点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;//修改元素个数
    modCount++;//修改次数加1
}

在中间添加元素的方法也很简单，典型的双链表在中间添加元素的方法。

添加元素的三种方式大致如下图所示：

在队列首尾添加元素很高效，因为有首位指针，时间复杂度为O(1)。

在中间添加元素比较低效，首先要先找到插入位置的节点，再修改前后节点的指针，时间复杂度为O(n)。

//按迭代顺序将集合的元素追加到此列表的末尾
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;
    //如果插入的集合没有元素 直接return false
    if (numNew == 0)
        return false;
	//succ指向当前需要插入结点的位置，pred指向其前一个结点
    Node<E> pred, succ;
    //当插入位置为列表尾部
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        //若不是插入尾部，查询索引对应的元素node()
        succ = node(index);
        pred = succ.prev;
    }
	
    //遍历collection中的所有元素将其依次插入链表指定位置
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //创建元素相应新结点
        Node<E> newNode = new Node<>(pred, e, null);
        //如果插入位置是0
        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++;//修改次数加1
    return true;
}

删除元素

• 作为双端队列，删除元素也有两种方式，一种是队列首删除元素，一种是队列尾删除元素。
• 作为List，又要支持中间删除元素

分别如下：

//删除首结点 
public E removeFirst() {
    //获取首结点
    final Node<E> f = first;
    //首结点为空 抛出异常
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // 此时的f已经确定 f == first && f != null;
    //首结点的元素值
    final E element = f.item;
    //首结点的next指针
    final Node<E> next = f.next;
    //元素值和next指针置null 方便GC回收
    f.item = null;
    f.next = null; 
    //把首节点的next作为新的首节点
    first = next;
    //如果next为null 说明只有一个元素，删除了，把last也置为空
    //否则把next前置指针置null
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;//元素个数加1
    modCount++;//修改次数加1
    return element;//返回元素值
}

//删除尾结点
public E removeLast() {
    //获取尾结点并保证尾结点不为空，为空抛出异常
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // 此时的l保证了 l == last && l != null;
    //获取尾结点的元素值
    final E element = l.item;
    //尾结点的前置指针
    final Node<E> prev = l.prev;
    //元素值 和 前置指针 置null 方便GC回收
    l.item = null;
    l.prev = null; 
    // 让前置节点成为新的尾节点
    last = prev;
    //如果只有一个元素 把首结点也置为null
    //否则把前置节点的next置为空
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

删除中间结点分两种情况，结点是否为null

1. 从头到尾遍历整个链表，找到第一个结点值相同的结点， 如果是null使用==，否则使用equals
2. 断开结点连接

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

E unlink(Node<E> x) {
    //x的元素值
    final E element = x.item;
    //x的前置结点
    final Node<E> next = x.next;
    //x的后置结点
    final Node<E> prev = x.prev;

    //如果前置结点为null，说明是第一个添加的结点，令first指向x的后置节点
    if (prev == null) {
        first = next;
    } else {
        // 否则修改前置节点的next为x的后置节点
        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;
}

删除元素的三种方法都是典型的双链表删除元素的方法，大致流程如下图所示。

在队列首尾删除元素很高效，时间复杂度为O(1)。

在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为O(n)。

区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。

其他的删除方法：removeFirstOccurrence、removeLastOccurrence

//删除第一个匹配项
ublic boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

//删除最后一个匹配项 分为null和非null
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

获取元素

//获取指定位置的元素
public E get(int index) {
    //检查索引是否合法
    checkElementIndex(index);
    //返回指定索引的元素
    return node(index).item;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}


private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

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

修改元素

//修改指定位置的元素值
public E set(int index, E element) {
    //检查索引是否合法
    checkElementIndex(index);
    //获取指定位置的结点
    Node<E> x = node(index);
    //获取结点值 方便返回旧结点值
    E oldVal = x.item;
    //修改结点值
    x.item = element;
    return oldVal;//返回旧结点值
}

迭代器

//从给定的索引开始，获取此列表上的ListIterator。此方法返回的ListIterator支持add、remove和set方法。
public ListIterator<T> listIterator(int index){
    checkBoundsInclusive(index);
    return new LinkedListItr<T>(index);
}
//列表上的列表迭代器。这个类跟踪它在列表中的位置以及它所处的两个列表项。
private final class LinkedListItr<I> implements ListIterator<I>{

    private int konwnMod = modCount;
    private Entry<I> next;
    private Entry<I> previous;
    private Entry<I> lastReturned;
    private int position;

    //初始化迭代器
    public LinkedListItr(int index) {
        if(index == size){
            next = null;
            previous = (Entry<I>) last;
        }else{
            next = (Entry<I>)getEntry(index);
            previous = next.previous;
        }
        position = index;
    }

    //检查迭代器的一致性。
    private void checkMod(){
        if(konwnMod != modCount)
            throw new ConcurrentModificationException();
    }

    //返回下一个元素的下标
    public int nextIndex(){
        return position;
    }

    //返回前一个元素的下标
    public int previousIndex(){
        return position-1;
    }

    //如果通过下一个元素存在更多元素，则返回true。
    public boolean hasNext(){
        return (next != null);
    }

    //如果先前存在更多元素，则返回true。
    public boolean hasPrevious(){
        return (previous != null);
    }

    //返回下一个元素
    public I next(){
        checkMod();
        if(next == null)
            throw new NoSuchElementException();
        position++;
        lastReturned = previous = next;
        next = lastReturned.next;
        return lastReturned.data;
    }

    //返回前一个元素
    public I previous(){
        checkMod();
        if(previous == null)
            throw new NoSuchElementException();
        position--;
        lastReturned = next = previous;
        previous = lastReturned.previous;
        return lastReturned.data;
    }

    //从列表中删除最近返回的元素
    public void remove(){
        checkMod();
        if(lastReturned == null){
            throw new IllegalStateException();
        }
        if(lastReturned == previous){
            position--;
        }

        next = lastReturned.next;
        previous  = lastReturned.previous;
        removeEntry((Entry<T>)lastReturned);
        
        konwnMod++;
        lastReturned = null;
    }
    
    //在上一个和下一个之间添加元素，然后前进到下一个。
    public void add(I o){
        checkMod();
        modCount++;
        konwnMod++;
        size++;
        position++;
        Entry<I> e = new Entry<I>(o);
        e.previous = previous;
        e.next = next;

        if(previous != null)
            previous.next = e;
        else
            first = (Entry<T>)e;

        if(next != null){
            next.previous = e;
        }else{
            last = (Entry<T>) e;
        }
        previous = e;
        lastReturned = null;
    }

    //更改最近返回的元素的内容。
    public void set(I o){
        checkMod();
        if(lastReturned == null){
            throw new IllegalStateException();
        }
        lastReturned.data = o;
    }
}

栈

官方推荐使用Deque代替stack来实现栈

Deque<E> stack = new LinkedList<>()

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

栈的特性是LIFO(Last In First Out)，所以作为栈使用也很简单，添加删除元素都只操作队列首节点即可。

队列

常用操作:

//添加元素
public boolean offer(E e) {
    return add(e);
}

///返回第一个元素，并在队列中删除
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//获取队头元素
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

//------ 以下api不推荐直接用 因为会抛出异常

//@throws IndexOutOfBoundsException 
public boolean add(E e) {
    linkLast(e);
    return true;
}
//Throws: NoSuchElementException – if this list is empty
public E element() {
    return getFirst();
}
//Throws: NoSuchElementException – if this list is empty
public E remove() {
    return removeFirst();

区别： getFirst(),element(),peek(),peekFirst() 这四个获取头结点方法的区别在于对链表为空时的处理，是抛出异常还是返回null，其中getFirst() 和element() 方法将会在链表为空时，抛出异常

element()方法的内部就是使用getFirst()实现的。它们会在链表为空时，抛出NoSuchElementException

getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。

总结

1. LinkedList是一个以双链表实现的List；

2. LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；

3. LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；

4. LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；

5. LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；

6. LinkedList在功能上等于ArrayList + ArrayDeque；

7. 遍历效率(快-慢)：
   Iterator迭代 > for循环

LinkedList面试题

Arraylist 与 LinkedList 区别?

1. 是否保证线程安全：
   ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

2. 底层数据结构：
   Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

3. 插入和删除是否受元素位置的影响：

• ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。首尾插入O(1),中间插入O(n-i)

• LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插入和删除元素的话 时间复杂度近似为 O(n)

4. 是否支持快速随机访问：

LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

5. 内存空间占用：
   ArrayList的花费主要体现在在 list 列表的结尾会预留一定的容量空间，
   而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Reference

死磕 java集合之LinkedList源码分析

LinkedList源码分析