本文共 6537 字，大约阅读时间需要 21 分钟。

LinkedList源码解读

• 实现了List,Deque,Cloneable,Serialzable接口
• 特点
  • 插入删除高效，查找比较慢
  • 线程不安全
• 构造方法

transient int size = 0;// 链表长度transient Node
   
     first;// 头节点transient Node
    
      last; //尾节点# 可以看出这是一个双向链表//构造函数public LinkedList(Collection
      c) {        this();        addAll(c);    }public boolean addAll(Collection
      c) {        return addAll(size, c);    }// 以size为下标 从尾部追加public boolean addAll(int index, Collection
      c) {        checkPositionIndex(index);// 越界校验        Object[] a = c.toArray(); //集合转为数组        int numNew = a.length;        if (numNew == 0)            return false;// 空 返回false        Node
     
       pred, succ;// index的前置 后置节点        if (index == size) {
  // 在size尾部追加节点            succ = null;            pred = last;        } else {            succ = node(index); //取index为后置节点            pred = succ.prev;        }        for (Object o : a) {            @SuppressWarnings("unchecked") E e = (E) o;            Node
      
        newNode = new Node<>(pred, e, null);            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;        // 修改次数+1        modCount++;        return true;    }// 二分思想 Node
       
         node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node
        
          x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node
         
           x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
         
        
       
      
     
    
   

• 小结

  • 追加集合时 遍历查找到链表后添加。arrayList 采取底层数组copyArray方法
  • 根据index获取node节点 采取二分思想

• Node节点类

private static class Node
   
     {        E item;// 元素值        Node
    
      next;// 后置节点        Node
     
       prev;// 前驱节点        Node(Node
      
        prev, E element, Node
       
         next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }
       
      
     
    
   

• 添加节点
  • add(e)
  • add(index,e)
  • addFirst(e)
  • addLast(e)

// 从尾部添加public boolean add(E e) {        linkLast(e);        return true;    }void linkLast(E e) {        final Node
   
     l = last;// l为尾节点引用        final Node
    
      newNode = new Node<>(l, e, null); //构造新节点        last = newNode;//新节点置为尾节点        if (l == null) //空链表             first = newNode; //置为头节点        else            l.next = newNode; //原尾节点l的后置变成当前节点        size++;        modCount++;    }
    
   

//指定index 插入元素public void add(int index, E element) {        checkPositionIndex(index);// 校验是否越界        if (index == size)//若index等于链表长度 追加至尾节点            linkLast(element);        else            linkBefore(element, node(index));    }succ节点前插入新节点void linkBefore(E e, Node
   
     succ) {        // assert succ != null;        //保存后置节点的前置节点        final Node
    
      pred = succ.prev;        // 构造新节点        final Node
     
       newNode = new Node<>(pred, e, succ);        // succ的前置节点为新节点        succ.prev = newNode;        if (pred == null)// 空链表 新节点置为头节点            first = newNode;        else            pred.next = newNode;//前置节点的后置为新接单        size++;        modCount++;// 修改modCount    }
     
    
   

// 插入头节点public void addFirst(E e) {        linkFirst(e);    }private void linkFirst(E e) {        final Node
   
     f = first;//保存原头节点        final Node
    
      newNode = new Node<>(null, e, f);// 构造新节点        first = newNode;/新节点单置为头节点        if (f == null)            last = newNode;// 链表空 头尾同节点        else            f.prev = newNode;// 原头节点的前置变为当前节点        size++;        modCount++;    }
    
   

• 移除
  • remove()
  • remove(index)
  • remove(object)

// 移除头节点public E remove() {        return removeFirst();    }public E removeFirst() {        final Node
   
     f = first;        if (f == null)            throw new NoSuchElementException();        return unlinkFirst(f);    }private E unlinkFirst(Node
    
      f) {        // assert f == first && f != null;        final E element = f.item; 保存头节点的值        final Node
     
       next = f.next;//获取头节点的后置        f.item = null;        f.next = null; // help GC 去掉引用        first = next; //后置next置为头节点        if (next == null)            last = null;//只有一个头节点 尾节点置空        else            next.prev = null; //next节点的前置置空        size--;        modCount++;        return element;    }
     
    
   

public E remove(int index) {        checkElementIndex(index);// 越界校验        return unlink(node(index));    }E unlink(Node
   
     x) {        // assert x != null;        final E element = x.item;        final Node
    
      next = x.next;        final Node
     
       prev = x.prev;        if (prev == null) {
  // 前置为空             first = next; //next为头节点        } else {            prev.next = next;// 断开前置与x的关联            x.prev = null; //x的前置引用断开        }        if (next == null) { //后置节点为空 当前节点为尾节点            last = prev;         } else {            next.prev = prev;//后置的前置引用指向x的前置            x.next = null; //断开后置的引用        }        x.item = null; //当前元素置空        size--; //修改size        modCount++; //修改modCount        return element;    }
     
    
   

// 移除指定节点public boolean remove(Object o) {        if (o == null) { //允许元素为null            for (Node
   
     x = first; x != null; x = x.next) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            for (Node
    
      x = first; x != null; x = x.next) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }
    
   

• 改 set

public E set(int index, E element) {        checkElementIndex(index);// 越界校验        Node
   
     x = node(index);        E oldVal = x.item; //将原元素的值替换为新元素        x.item = element;        return oldVal;    }
   

• 查 get

public E get(int index) {        checkElementIndex(index); //判断越界        return node(index).item; //根据index获取值    }

• toArray

public Object[] toArray() {        Object[] result = new Object[size]; //构造一个size大小的数组        int i = 0;        for (Node
   
     x = first; x != null; x = x.next)            result[i++] = x.item; //遍历每个元素放到数组中        return result;    }
   

• 其他

public boolean offer(E e) { //布尔返回值 添加成功true        return add(e);    }

• 总结
  • 可以当做队列往前后插入或取值
  • 查询主要是根据index查找node,二分思想 折半
  • 添加 删除 会修改modCount,查找与修改不会

转载地址：http://uhiii.baihongyu.com/