深入理解LinkedList_linkedlist 左右哪边是头

什么是LinkedList

概念：

LinkedList是基于链表实现的，所以先讲解一下什么是链表。链表是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。
理解：
LinkedList是一个双向链表，也就是说list中的每个元素，在存储自身值之外，还 额外存储了其前一个和后一个元素的地址，所以 也就可以很方便地根据当前元素获取到其前后的元素链表的尾部元素的后一个节点是链表的头节点；而链表的头结点前一个节点则是则是链表的尾节点（是不是有点像贪吃蛇最后 头吃到自己尾巴的样子，脑补下）既然是一个双向链表，那么必然有一个基本的存储单元。
相比于ArrayList，LinkedList他有不同之处，ArrayList直接继承AbstractList，而LinkedList继承自AbstractSequentialList,然后再继承自AbstractList.另外，LinkedList还实现了Dequeue接口，双端队列。

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

类的结构示意图

 一个结点

内部结构 

 

 从上图可以看出,LinkedList内部是一个双端链表结构，有两个变量，first指向链表头部，last指向链表尾部。

源码分析

LinkedList内部成员变量

    //链表大小
    transient int size = 0;
 
    /**
     * 指向第一个结点
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
 
    /**
     * 指向最后一个结点
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

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

构造方法

LinkedList有两个构造方法,一个用于构造一个空的链表，一个用已有的集合创建链表。

    public LinkedList() {
    }
 
    public LinkedList(Collection<? extends E> c) {
        this();   //此方法为无参构造
        addAll(c);   //将集合c添加到链表中
    }
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);   //调用addAll方法，含有两个参数，size和c
    }

List接口的添加操作

add(E e)

add(E e)用于将元素添加到链表尾部

public boolean add(E e) {
        linkLast(e);
        return true;
    }
 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++;   //操作次数自增
    }

LinkLast其实是一个尾插法，但是需要注意链表为空时头结点的处理。

add(int index,E e)

该方法用于在指定位置添加元素

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

node(int index)方法

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

从上面看出node(int index)方法将根据index是靠近头部还是尾部选择不同的遍历方向

linkBefore()方法

 void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;//找到succ结点的前驱
        final Node<E> newNode = new Node<>(pred, e, succ);//创建新的结点
        succ.prev = newNode;//succ结点的前驱指向新节点
        if (pred == null)
            first = newNode;  //判断前驱是否为null,是的话newNode就是头结点
        else   //不是的话前驱结点的next指向新节点
            pred.next = newNode;
        size++;   //长度自增
        modCount++;
    }

 linkBefore()方法在第二个参数结点之前插入一个新结点

addAll()方法 

addAll有两个重装方法，一个参数的方法表示将集合元素添加到链表尾部，而两个参数的方法指定了开始插入的位置。

//将集合插入链表尾部，即开始索引位置为size 
public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
 
 public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);   //检查index是否越界
 
        Object[] a = c.toArray();    //集合c转换为数组
        int numNew = a.length;    //计算数组长度
        if (numNew == 0)   //判断数组长度是否为0
            return false;
 
        Node<E> pred, succ;   //定义前驱结点和后继结点
        if (index == size) {   //如果index是末尾的话
            succ = null;   //后继结点为null
            pred = last;   //前驱结点作为尾结点
        } else {     
            succ = node(index);   //用node方法得到后继结点
            pred = succ.prev;   //得到前驱结点
        }
 
        //遍历数据
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;  //强转为E类型
            //创建新的结点
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)   //前驱为null.新结点为头结点
                first = newNode;
            else    //否则新结点为前驱结点的next
                pred.next = newNode; 
            pred = newNode;  //前驱结点后移
        }
 
        if (succ == null) {   //后继结点为null，前驱就为尾结点
            last = pred;
        } else {   //目前的pred.next指向succ
            pred.next = succ;
            succ.prev = pred;
        }
 
        size += numNew;   //改变长度
        modCount++;
        return true;
    }

Deque接口的添加操作

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;
        if (f == null)   //判断是否为空
            last = newNode;    //头结点为空，新结点为尾结点
        else
            f.prev = newNode;  //新结点作为首结点的前缀结点
        size++;
        modCount++;
    }

从上面代码看到，实现就是在头结点插入一个结点使新节点称为新节点，但是和linkLast一样需要注意当链表为空时，对last结点的设置。

addLast(E e)方法

addLast()方法用于将元素添加到链表尾部。

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

offer(E e)方法

offer()方法用于将数据添加到链表尾部，其内部调用了add(E e)方法

public boolean offer(E e) {
        return add(e);
    }

offerFirst(E e)方法

offerFirst()方法将数据插入到链表头部，与addFirst的区别在于该方法可以返回特点的返回值，而addFirst的返回值为void

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

获取任意位置的get(int index)方法

    public E get(int index) {
        checkElementIndex(index);   //检查是否越界
        return node(index).item;   //返回结点的数据
    }

获取位置为0的头结点位置

LinkedList中有多种方法可以获得头结点的数据,实现大同小异,区别在于对链表为空时的处理，是抛出异常还是返回null。主要方法有getFirst()、element()、peek()、peekFirst()。

    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;
     }
 public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

根据对象得到索引

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

检查链表是否包含某对象

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

删除指定对象

public boolean remove(Object o) {
        //如果删除对象为null
        if (o == null) {
            //从前往后遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);   //调用unlink方法
                    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) {
        // 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;
    }

删除任意位置的对象

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

删除头结点对象

public E remove(){
   return removeFirst(); 
}
 
public E pop(){
   return removeFirst();
}
 
public E removeFirst(){
   final Node<E> f = first;
   if(f == null)
      throws new NoSuchElementException();
   return unlinkFirst(f);
}
 
public E poll(){
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
 
public E pollFirst(){
   final Node<E> f = first;
   return (f == null) ? null : unlinkFirst(f);
}

删除尾结点对象

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

总结：

LinkedList是基于双链表的List，其内部的实现源于对链表的操作，所以适用于频繁增加，删除的清理；另外，由于LinkedList实现了Queue接口，所以不只有队列的接口，还有栈的接口，还可以使用它作为队列和栈的实现。