简介

LinkedList是一个实现了List接口和Deque接口的双向链表。
智齿搞笑的插入和删除。
实现了Deque接口焗油队列的特性。
非线程安全，可以调用静态类Collections类中的synchronizedList方法实现线程安全。

List list=Collections.synchronizedList(new 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类代表双向链表的节点Node。
这个类分为前驱结点prev、后继节点next和北街店三个属性。

LinkedList源码分析

构造方法

空参构造

    public LinkedList() {}

用已有的集合创建链表的构造方法

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

add方法

add(E e)方法：将元素添加到链表尾部

public boolean add(E e) {linkLast(e);//这里就只调用了这一个方法return true;}

   /*** 链接使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;elsel.next = newNode;//指向后继元素也就是指向下一个元素size++;modCount++;}

add(int index,E e)：在指定位置添加元素

public void add(int index, E element) {checkPositionIndex(index); //检查索引是否处于[0-size]之间if (index == size)//添加在链表尾部linkLast(element);else//添加在链表中间linkBefore(element, node(index));}

linkBefore方法需要给定两个参数，一个插入节点的值，一个指定的node。

addAll(Collection c )：将集合插入到链表尾部

public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}

addAll(int index, Collection c)： 将集合从指定位置开始插入

public boolean addAll(int index, Collection<? extends E> c) {//1:检查index范围是否在size之内checkPositionIndex(index);//2:toArray()方法把集合的数据存到对象数组中Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;//3：得到插入位置的前驱节点和后继节点Node<E> pred, succ;//如果插入位置为尾部，前驱节点为last，后继节点为nullif (index == size) {succ = null;pred = last;}//否则，调用node()方法得到后继节点，再得到前驱节点else {succ = node(index);pred = succ.prev;}// 4：遍历数据将数据插入for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;//创建新节点Node<E> newNode = new Node<>(pred, e, null);//如果插入位置在链表头部if (pred == null)first = newNode;elsepred.next = newNode;pred = newNode;}//如果插入位置在尾部，重置last节点if (succ == null) {last = pred;}//否则，将插入的链表与先前链表连接起来else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}    

1. 检查index范围是否在size之内
2. toArray()方法把集合的数据存到对象数组中
3. 得到插入位置的前驱和后继节点
4. 遍历数据，将数据插入到指定位置

addFirst(E e)： 将元素添加到链表头部

 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;//如果链表为空，last节点也指向该节点if (f == null)last = newNode;//否则，将头节点的前驱指针指向新节点，也就是指向前一个元素elsef.prev = newNode;size++;modCount++;}

addLast(E e)： 将元素添加到链表尾部，与 add(E e) 方法一样

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

根据位置获取数据

get(int index)： 根据指定索引返回数据

public E get(int index) {//检查index范围是否在size之内checkElementIndex(index);//调用Node(index)去找到index对应的node然后返回它的值return node(index).item;}

获取头节点（index=0）数据方法:

public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}
public E element() {return getFirst();}
public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}public E peekFirst() {final Node<E> f = first;return (f == null) ? null : f.item;}

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

获取尾节点（index=-1）数据方法:

 public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}public E peekLast() {final Node<E> l = last;return (l == null) ? null : l.item;}

**区别：**getLast() 方法在链表为空时，会抛异常，peekLast()会返回null。

根据对象得到索引的方法

int indexOf(Object o)： 从头遍历找

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

int lastIndexOf(Object o)： 从尾遍历找

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

检查链表是否包含某对象

contains(Object o)： 检查对象o是否存在于链表中

 public boolean contains(Object o) {return indexOf(o) != -1;}

删除的方法

remove() ,removeFirst(),pop(): 删除头节点

public E pop() {return removeFirst();}
public E remove() {return removeFirst();}
public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}

removeLast(),pollLast(): 删除尾节点

public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}
public E pollLast() {final Node<E> l = last;return (l == null) ? null : unlinkLast(l);}

区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。
remove(Object o): 删除指定元素

public boolean remove(Object o) {//如果删除对象为nullif (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;}

当删除指定对象时，只需调用remove(Object o)方法，该方法一次智慧删除一个匹配的对象，删除成功返回true

unlink(Node x) 方法：

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

remove(int index)：删除指定位置的元素

public E remove(int index) {//检查index范围checkElementIndex(index);//将节点删除return unlink(node(index));}

相关面试题

ArrayList与LinkedList的区别

1. 是否线程安全：都是线程不同步不安全的。
2. 底层数据结构：ArrayList底层是Object[] elementData 数组； LinkedList底层使用的是双向链表（JKD1.7之前是循环链表）
3. 插入和删除是否受元素位置的影响：
   1.ArrayList底层数组，插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList会默认将制定的元素追加到此列表的末尾，此时时间复杂度O(1)。但是如果要在指定位置 i 插入和删除元素的话 add(int index, E element) 时间复杂度O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的（n-i）个元素都要执行向后/向前移一位的操作。
   2.LinkedList底层链表，对于插入和删除元素时间复杂度不受元素位置的影响，近似O（1），如果是要在指定位置 i 插入和删除元素的话，时间复杂度近似O（n），因为需要先移动到指定位置在插入。
   3.是否支持快速随机访问：LinkedList不支持搞笑的随机元素访问，ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象的方法。
   4.内存占用空间：ArrayList的空间浪费主要体现在list列表的结尾会渔鸥一定的空间容量，而LinkedList的空间花费则提现在它的没一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。