Linkedlist

简介

本节来介绍LinkedList ,他也是List 接口下最常用的用来存储数据的工具类之一。仍然从基础的数据结构，整个类的继承和实现的体系来了解。Linkedlist可以做那些事情，在哪些的应用场景下更适合应用。

1.首先LinkedList是基于双向链表。意味着增删比较快，但是查找相对于ArrayList会比较慢。（常见面试题之一，ArrayList与LinkedList的区别），本质上来讲，就是二者的数据结构不同，稍后可以说明。

2.实现了 Deque 接口，意味着可以进行队列操作。

3.实现了Cloneable接口，即覆盖了函数clone()，可以被克隆。

4.实现了 Serializable 接口，意味着LinkedList支持序列化，能通过序列化去传输。

5.LinkedList和Arraylist一样，都是线程不安全的。

结构图

image.png

构造函数

Linkedlist共有两个构造函数。分别为：

1.无参构造，直接创建LinkedList对象。

 /**
 * 构造一个空列表
 */
 public LinkedList() {
 }      

image.png

2.参数需要一个Collection集合，作为参数，构造一个新的集合。

 /**
 * 构造包含指定元素的列表集合，按照集合返回的顺序迭代器
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

image.png

    这里就是，接收一个集合，作为参数，然后调用 addAll() 方法，来初始化LinkedList()。

接下来分析，addAll()方法做了哪些事情。

这里调用了 public 权限的 addAll() 方法。说明，我们可以将任意一个集合添加到 LinkedList 中。
这里有一点要注意：默认的size就是当前的链表长度，默认在当前链表后面添加参数的集合。

 /**
 * 将指定集合中的所有元素追加到末尾这个列表，按照指定的返回顺序集合的迭代器。
 * 如果没有定义此操作的行为在操作中修改指定的集合进步。(注意，如果指定的集合是，就会发     * 生这种情况*这个列表，它不是空的。
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

Alt text

addAll()

这里要对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;
    }
}  



/**
*将指定集合中的所有元素插入其中列表，从指定位置开始。变化的元素
 *目前处于该位置(如果有的话)和任何后续元素
 *右边(增加他们的指数)。新的元素将会出现
 *在列表中，以它们被返回的顺序指定集合的迭代器。
 */
public boolean addAll(int index, Collection<? extends E> c) {
      //检查索引是否合法
    checkPositionIndex(index);
      //将添加的集合先转成Object数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //如果数组的长度为0，返回false不做任何操作
    if (numNew == 0)
        return false;
        
     //定义一个节点
    Node<E> pred, succ;
    //当向链表最后面插入时。
    if (c == size) {                
        succ = null;
        //将链表最后一个节点，赋值给当前定义节点的上一个节点。
        pred = last;
    } else {
          //这里查找原来index位置的Node，做为后置节点。
        succ = node(index);
        //前置节点为index节点的前一个节点。
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //构造一个新的节点，pred原来index位置的上一个节点。e当前节点
        Node<E> newNode = new Node<>(pred, e, null);
        //如果pred为空,说明原来的链表是空的，那么新增的节点为链表的第一个节点。
        if (pred == null)
            first = newNode;
        else
        //这里是当链表不是初始化时候，替换链表内指定的node
            pred.next = newNode;
        pred = newNode;
    }
        //如果succ为空，说明在链表的末尾，（或者是链表刚刚初始化，也为null）
    if (succ == null) {
        last = pred;
    } else {
      //链表中间添加情况，更新前置节点 后置节点。
        pred.next = succ;
        succ.prev = pred;
    }
        //修改size
    size += numNew;
    //修改modCount（这里后续解释作用是什么）
    modCount++;
    return true;
}

add()添加一个元素到链表内

/**
 * 添加一个元素到链链表中，默认追加到链表的末尾‘
 * 这里调用了public权限的add方法。’
 */
public boolean add(E e) {
//调用linkLast
    linkLast(e);
    return true;
}

linkLast追加到链表末尾

/**
  *添加到链表末尾
 */
void linkLast(E e) {
      //保存原有链表的最后一个节点。
    final Node<E> l = last;
    //构造当前节点，并且原来的最后一个节点最为当前节点的上一个节点
    final Node<E> newNode = new Node<>(l, e, null);
    //当前节点作为原有链表的最后一个节点
    last = newNode;
    //如果原有的最后一个节点为null，说明链表为null（刚刚初始化）
    if (l == null)
          //当前节点作为第一个节点。
        first = newNode;
    else
          //将当前节点赋值给原来最后一个节点的下一个节点。
        l.next = newNode;
    size++;
    modCount++;
}

remove删除元素

 /**
 *删除指定元素 
 */
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) {
                //如果去除指定元素，则直接equals寻找要删除的元素。
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

unlink删除元素

 /**
 * 删除指定的元素
 */
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 {
          //原有节点上一个节点，对应的下一个节点为next。有点绕口。。。
        prev.next = next;
        //将当前节点的 前置节点置空
        x.prev = null;
    }
    //如果后置节点为空（说明当前节点原本是尾节点）
    if (next == null) {
          //则尾节点为前置节点
        last = prev;
    } else {
        //将当前节点的 后置节点置空
        next.prev = prev;
        x.next = null;
    }
      //当前元素置为null
    x.item = null;
    //链表数量-1
    size--;
    //修改modCount
    modCount++;
    //返回删除的元素
    return element;
}

push&pop

注意：链表中也存在push，pop操作，说明可以作为一个栈来操作。面试也很常见实现一个自己的栈或者队列。这里看一下，push和pop操作，用来了解一下栈是如何实现的。

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

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

调用的方法分别为addFirst，removeFirst。

/**
 * 直接追加到链表最前面
 */
public void addFirst(E e) {
    linkFirst(e);
}

pop也是一样的道理，直接操作首节点

/**
 *删除首节点
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

总结

1.上文说明了LinkedList是基于双向链表，在实际的代码中看到，当增加或者删除一个元素，在原有的链表中直接寻找并且unlink即可。

2.删除和增加都涉及到modCount操作，这点要注意（后续解释，或者可以自行百度）。

3.其实增加和删除或者其他操作，都围绕着一个核心，就是处理链表。这里如果把链表的结构自己理解的足够好，可以尝试自己写一个自己的链表。

4.jdk中每一个类，方法都拆分的足够细致，得以最大化的复用。这也是是学习的目的之一，将自己的代码做到尽可能细致的拆分，每一个方法具体用来做什么。